読者です 読者をやめる 読者になる 読者になる

「マイナー・ゲーム」問題解答 ( CodeIQ )

はじめに

CodeIQというところでプログラミング問題「マイナー・ゲーム」に解答しましたので、ネタバレです。

codeiq.jp

問題

入力 n ( $3\le n\le 100$ ) に対して、n人から開始して少数決を繰り返す時に、残り1人または2人になって決着するまでの回数の期待値$F(n)$に対して、$F(n)\times 10^6$の整数部分を出力する問題です。

少数決の内容は次の通りです。

  • 1回の少数決で、全員がランダムにAもしくはBを選ぶ
  • A,Bの内、人数が少ない方が残り、3人以上であれば次の少数決に移る
  • A,Bが同数、あるいは全員が同じ方を選んだ場合は、全員残って次の少数決に移る

解説

n人いる場合のA,Bの選び方は全部で $2^n$通りありますが、1巡費やして、次に何人残るか、それで期待値が計算できるはずです。

nが偶数の場合は同数引き分けがあるためちょっと状況が違いますが、全員残ってやり直しも含め、 $$ F(n)=\left\{\begin{array}{ll} 1+\frac{1}{2^n}(2\times{}_nC_0F(n)+2\times{}_nC_1F(1)+2\times{}_nC_2F(2)+\cdots+2\times{}_nC_{\frac{n}{2}-1}F(\frac{n}{2}-1)+2\times{}_nC_{\frac{n}{2}}F(n)) & ( n:even ) \\ 1+\frac{1}{2^n}(2\times{}_nC_0F(n)+2\times{}_nC_1F(1)+2\times{}_nC_2F(2)+\cdots+2\times{}_nC_{\frac{n-1}{2}}F(\frac{n-1}{2})) & ( n:odd ) \\ \end{array}\right. $$ という関係が成立します。ちなみに、$F(1)=F(2)=0$です。

うーん…。このままだと、やり直しにあたる$F(n)$の項の処理が面倒ですが、各${}_nC_i$を合計すれば、全体$2^n$になること、$2{}_nC_i$は${}_nC_i+{}_nC_{n-i}$に等しいことから、$F(n)$の係数は全体から引いていくことで求められると考えると、場合分けが不要になります。すなわち、

$$ F(n)=1+\frac{1}{2^n}\left\{(2\times{}_nC_1F(1)+2\times{}_nC_2F(2)+\cdots+2\times{}_nC_{\lfloor\frac{n-1}{2}\rfloor}F(\lfloor\frac{n-1}{2})\rfloor)+(2^n-2\times{}_nC_1-2\times{}_nC_1\cdots-2\times{}_nC_{\lfloor\frac{n-1}{2}\rfloor})F(n)\right\} $$ 整理すると、 $$ F(n)=\frac{2^{n -1}+\sum_{k=1}^{\lfloor\frac{n-1}{2}\rfloor}{}_nC_kF(k)}{\sum_{k=1}^{\lfloor\frac{n-1}{2}\rfloor}{}_nC_k} $$ ということです。つまり、${}_nC_k$を$k=1$から順に計算していって、分子には$F(k)$をかけて加算、分母はそのまま加算する、ということで再帰的に計算できます。

なので、素直にメモ化再帰で実装したのが提出版のコード Ruby(114)です。なお、関数fは既に$10^6$倍した数値 ( 浮動小数点 ) で計算しておき、最後に整数部分を取り出します。

m=[0]*3
f=->n{
  a,q=1,0
  m[n]||=(1..~-n/2).reduce(2.0**~-n*1e6){|s,k|
    q+=a=a*(n-k+1)/k
    s+a*f[k]
  }/q
}
p f[eval *$<].to_i

終わりに

問題自体、浮動小数点で計算しても精度的に問題ないケースのみとなっていますが…。誤差を気にするなら、Rubyであれば、有理数として計算することもできます。ただ、通分するたびに分母がおそろしいことになっていくので、速度的にはちょっと…。