目標値xにちょうど到達するサイコロの投げ回数を求めるC++コード

問題の概要

整数 x が与えられているとします。手元にあるのは、各面に 2 から 7 までの数字が書かれた 6 面体サイコロです。目標は、サイコロを振って出た目の合計をちょうど x にすることです。

ここでポイントになるのは、振る回数は自由という点です。合計がちょうど x になるような投擲回数が 1 つ分かれば十分で、その結果が出る確率が 0 でない限り、幸運にも実際にその通りの出目を得られるものとします。つまり、条件を満たす任意の回数を 1 つ答えればよいのです。

考え方

この問題を解くカギは、サイコロの最小の出目が 2 であることに着目することです。

• x が偶数の場合： 毎回 2 を出せばよく、必要な回数は x / 2 回です。
• x が奇数の場合： 1 回だけ 3 を出し、残りはすべて 2 にすれば、⌊x / 2⌋ 回で合計がちょうど x になります。

どちらの場合も答えは「x を 2 で割った値の小数点以下を切り捨てたもの」、すなわち ⌊x / 2⌋ となります。

具体例

入力が x = 100 の場合を考えてみましょう。たとえば「2 を 11 回、3 を 6 回、6 を 10 回」と出せば合計は 22 + 18 + 60 = 100 となり、27 回の投擲で目標を達成できます。ただしこれは一例にすぎず、正解となる回数は複数存在します。最もシンプルなのが毎回 2 を出す方法で、本記事で紹介する解法はこの発想に基づいて ⌊x / 2⌋ = 50 を出力します。

解法の手順

この問題は、次のわずか 1 ステップで解けます。

return floor of (x / 2)

C++ 実装例

理解を深めるために、実際のコードを見てみましょう。C++ では int 型同士の除算で小数点以下が自動的に切り捨てられるため、単に x / 2 を返すだけで ⌊x / 2⌋ が得られます。

#include<bits/stdc++.h>
using namespace std;
int solve(int x){
    return x/2;
}
int main(){
    int x = 100;
    cout << solve(x) << endl;
}

入力

100

出力

50

出力の 50 は「毎回 2 を出したときの投擲回数」です。2 × 50 = 100 となり、ちょうど目標に到達できることが確認できます。

まとめ

最小の出目が 2 であることを利用すれば、答えが ⌊x / 2⌋ に一致することを示せました。計算量は O(1) と非常に効率的で、x が偶数ならすべて 2、奇数なら 1 回だけ 3 を出すことで必ず達成できます。