私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「マイナー・ゲーム」（CodeIQ）を参照してください。
n 人のプレイヤーで「少数決」というゲームを行います。
ゲームは次の手順で進みます。
- 各プレイヤーは、投票用紙にＡまたはＢの文字を記し投票します。投票は記名式です。他のプレイヤーの投票内容は分かりません。
- 全員が投票し終わったら開票します。その結果、少数派になる回答をした者が勝者となります。例えばＡが 3 票、Ｂが 4 票の場合は、Ａを投票した 3 名が勝者です。ＡとＢが同数の場合や、全員がＡの場合、全員がＢの場合は、全員が勝者です。
- 勝者はそのまま勝ち残り次の投票に進めますが、敗者はそこで脱落します。
- 以上が 1 回の「ターン」です。この要領でターンを繰り返し、勝ち残りが 1 人か 2 人になるまでゲームを続けます。
各プレイヤーはＡまたはＢをランダムに選んで投票します。
このとき、n 人のプレイヤーから始めてゲームが終了するまでのターンの回数の期待値を F(n) と定義しましょう。
例えば F(3) ＝ 4/3 です。3 人の投票の仕方は計 23＝ 8 通りあります。このうち全員がＡまたは全員がＢの場合（2 通り）は 3 人ともが勝者となりますが、それ以外の場合（6 通り）は 1 名の勝者が決まりゲーム終了します。
1 回目のターンでゲームが終了する確率は 6/8 ＝ 3/4 です。
2 回目のターンでゲームが終了する確率は (1/4)×(3/4) です（1 回目で終了せずかつ 2 回目に終了する確率）。
3 回目のターンでゲームが終了する確率は (1/4)2×(3/4) です（1, 2 回目で終了せずかつ 3 回目に終了する確率）。
…
したがって期待値は 1×(3/4)＋2×(1/4)×(3/4)＋3×(1/4)2×(3/4)＋… ＝ 4/3 となります。
同様に、F(4) ＝ 2，F(5) ＝ 16/15，F(7) ＝ 1.7566137…，F(8) ＝ 2.2028985… となることが確かめられます。
標準入力から、自然数 n（3 ≦ n ≦ 100）が与えられます。
標準出力に、F(n) を 106 倍した値の整数部分を出力するプログラムを書いてください。
Rubyで解答しています。
#!/usr/bin/ruby
$RoundRest = []
$CombinMemo = {}
$CalcedMemo = {}
$Even = {}
$Finished = {}
# 組み合わせを計算する
# 一度計算した値は$CombinMemoに保持する
# $CombinMemoに値があった場合はそれを返す
def C(n,r)
if n == 0 then return 1 end
memo = $CombinMemo[[n,r]]
if memo != nil then return memo end
a = ((n-r+1)..n).reduce(1, :*)
b = (1..r).reduce(1, :*)
memo = a/b
$CombinMemo[[n,r]] = memo
return memo
end
# $RoundRestを初期化する
def init(n)
$RoundRest << {n => 1.0}
end
# 終了になる確率を計算する
# 一度計算した値は$Finishedに保持する
# $Finishedに値があった場合はそれを返す
def calcFinished(n)
if $Finished[n] != nil then return $Finished[n] end
if n == 1 || n == 2 then
$Finished[n] = 1.0
elsif n == 3 || n == 4 then
$Finished[n] = 2.0 * C(n,1) / (2**n)
else
$Finished[n] = 2.0 * (C(n,1) + C(n,2)) / (2**n)
end
return $Finished[n]
end
# n回目の再勝負の係数を計算する
# 計算結果は$CalcedMemoに保持する
# $CalcedMemoに値がある場合はそれを返す
def getCalcedMemo(n, i)
if $CalcedMemo[[n,i]] != nil then return $CalcedMemo[[n,i]] end
$CalcedMemo[[n,i]] = 2.0*C(n,i)/2**n
return $CalcedMemo[[n,i]]
end
# 引き分けの確率を計算する
def calcEven(n)
if $Even[n] != nil then return $Even[n] end
even = 2.0 + (n%2 == 0 ? C(n, n/2) : 0) # 引き分けの組み合わせ数
$Even[n] = even/(2**n)
end
# i回目の投票を行い、その回の期待値を計算する
def vote(i)
ret = 0
rest = Hash.new(0)
$RoundRest[i].each{|n, a|
ret += a * calcFinished(n)
v = rest[n]
rest[n] = v + a*calcEven(n)
h = (n.to_f / 2).ceil - 1 # nの半分より小さい最大の整数
for j in 3..h
v = rest[j]
rest[j] = v + a*getCalcedMemo(n,j)
end
}
# p rest
$RoundRest << rest
return ret
end
# 問題を解く
def solve()
ret = 0
for i in 0...100
ret += (i+1) * vote(i)
end
ret += 0.00000000000001
return ret
end
# main
while line = gets
line.strip!
if line.empty? then next end
N = line.to_i
end
init(N)
ret = solve()
p (ret * 1000000).floor
★★★の問題ですがかなり難しいです。数学的な一般解をある程度まで求めていないと解けないと思います。加えて計算量を減らす工夫が必要です。
数学的に解を考える必要があります。でないとコードに落とし込めません。
そして、N=3の場合が例示されていますが、N≧7以上で考える必要があります。
まず、投票が終わる確率です。
投票が終わるのは1人か2人が投票した場合です。
Aに1人か2人が投票する組み合わせはnC1+nC2です。
投票が終わるのはBに投票した場合もあるので2*(nC1+nC2)です。
全ての投票パターンは2nなので、投票が終わる確率は
2*(nC1+nC2)/2n・・・(A)
になります。
次に再投票の場合ですがこれには2パターンあります。
一つは、全員勝者（全員が同じ方に投票した場合とABが同数だった場合）です。
全員が同じ方に投票する組み合わせはnCn=1でABの2パターンがあるので2です。
ABが同数になるのはnCn/2（ただし、nは偶数）です。
よって再度同じ人数で投票することになる確率は
(2+nCn/2)/2n ・・・(B)
です。
よって全員勝ちの場合で2回目以降に勝負が決まる確率は
(B)i*(A)（iは試行回数）
で、これに試行回数をかけて、
i*(B)i*(A)（iは試行回数）・・・(D)
がこのパターンの期待値になります。
もう一つは人数を減らして再試行する場合です。
これはN=7以上を検討しないと出現しません。N=7の場合4:3にわかれた時、3人で再度投票しなければなりません。
まず、人数を減らして再投票になる確率は、
nCh/2n・・・(C)（hは3からh
これに対して2回目で勝負が決まる可能性が全てのhに対して(C)*(A)あり、3回目以降は(C)のn=hとして再帰的に
(Cn1)*(Cn2)…(Cnx)*(A)
で勝負が決まります。
そして、これに試行回数をかけて
i*(Cn1)*(Cn2)…(Cni)*(A)・・・(E)
がこのパターンの期待値になります。
また、人数を減らしてから全員勝者に成るとか全員勝者から人数を減らして繰り返しになる場合もあり、それら全てのi回目に決着がつく場合の確率に試行回数をかけたものの合計が答えになります。
そして、問題の仕様を満たすためには有効桁数小数点以下6桁の精度を満たすまで前述の計算を繰り返さなければなりません。
問題を解くプログラムですが本体はこの中で呼んでいるvote()です。
solve()は精度が十分になるまでvote()を繰り返し呼び出しているだけです。私のプログラムは100回も計算すれば十分な精度に達しているということで計算回数を適当に決めています（やってみたらN=100の時に100回でも200回でも同じ値になったので100にしました）。
結果を返す前に0.00000000000001を加えているのはN=4の時のように無限に計算しないと精度が不十分な場合に対する対策で、10-6より十分に小さい値を加えることで1.99999…のような値を丸めるためです。
引数i回目の投票結果を計算し、終了する場合の確率を返します。
また、次に試行するパターンの確率とその場合の人数の組みを$RoundRestに記録します。
処理は次の手順を繰り返します。
$RoundRestの最後の要素を順次取り出します。
$RoundRestの要素は人数をキー、前回その人数が再試行対象になった確率が値になっているので人数をn、確率をaに保持します。
73行目でそのn,aで終了する確率を計算し、retに加算します。その試行回数で終了する確率は$RoundRestの全要素で終了する場合の確率の合計なのでループの間結果を加算しなければなりません。
次に全員勝者で次回の確率を計算します（76行目）。
そして現在の人数を減らして次回の確率を計算します（79〜82行目）。
全ての要素を処理し終わったら$RoundRestに次回計算する確率と人数の組みをセットし、retをリターンします。
次回計算する確率と人数の組みは人数をキー、確率を値とするHashになっています。
同じ人数が残る場合の確率はすべて加算してしまいます。
これが高速化のための最大の工夫で、これによって次回計算すべき要素の数の増え方を抑制できます。例えばN=100の場合、次回計算すべき人数のパターンは100、49〜3の48パターンに収束することができます。
これを同じ人数でまとめず、[人数,確率]の組みのリストなどとすると膨大な数になってしまい、制限時間内にはとても終わらなくなってしまいます。
この関数は1回の試行で決着がつく確率を返します。
n=1,2の場合は必ず決着するので1を返します。
n>4の場合は「基本的な考え方」に書いた通り2*(nC1+nC2)で決着します。
n=3,4（実際は4ということはない）の場合は特殊で1人と2人にわかれますが2人が負け側になるので2*nC1だけが決着するパターンになります。
計算量を減らすため一度計算したパターンは$Finishedに記録し、記録済みのnに対しては計算せずに結果を返します。
引き分けの確率を計算して返します。
計算量を減らすため一度計算したパターンは$Evenに記録し、記録済みのnに対しては計算せずに結果を返します。
人数を減らして再勝負になる場合、次がi人になる時の確率を計算して返します。
計算量を減らすため一度計算したパターンは$CalcedMemoに記録し、記録済みのnに対しては計算せずに結果を返します。
組み合わせを計算します。
計算量を減らすため一度計算したパターンは$CombinMemoに記録し、記録済みのnに対しては計算せずに結果を返します。
calcFinished()、calcEven()、getCalcedMemo()はいずれも計算結果をメモして計算量を減らしています。実際のところ効果は微妙なのですが、この問題はN=100が最大で組み合わせ（階乗）の計算を何度もしなければならないなど多倍長精度の演算を何度もしなければなりません。
多倍長精度の計算は遅いので何度も計算すると性能に影響するのでメモを使って高速化しています。
この問題はとりあえずプログラムを書き始めて、部分を解決して行けば良いという問題ではなく、数式を導いて、それをコードに直す必要があり、高校レベルですがそれなりの数学能力を要求されます（その上ややこしい）。
結局、1日くらいかかったと思います。