*[[Problem 481:http://projecteuler.net/problem=481]] 「シェフの決戦」 [#m79d36a4]
シェフのグループ (#1,#2 と番号付けされている) がターン制の料理競技会に参加している.
それぞれのシェフの出番になると, シェフはベストを尽くして料理を作り, 味の審査のため個別の審査団に料理を提供する. #'''k''' のシェフの技術レベル (あきらかにはなっていない) を S('''k''') で表すとしよう.
具体的に言うと, S('''k''') とは #'''k''' のシェフの料理が (どのターンにおいても) 審査団によって高評価される可能性である.
もしシェフが高評価を受けると, そのシェフは競技会からふるい落とされる別のシェフを選ばなければならない.
最後に残ったシェフが勝者となる.
競技会は #1 のシェフから開始され, 競技の順番は他の勝ち残ったシェフに順次適用される.
そしてこの一連のサイクルは一番番号の小さいシェフから繰り返される.
全てのシェフは, 他のシェフたちが同様に振る舞うと仮定して, 決められたルール内で勝つチャンスを最適化することを目標としている.
あるシェフが同様に最適となるひとつ以上のふるい落とそうとする選択肢を持つ場合には, 選択されるシェフは最も直前に出番となるシェフとなると仮定する.
'''n''' 人の競技会で #'''k''' のシェフが勝つ可能性を W&sub{n};('''k''') と定義しよう.
もし S(1) = 0.25, S(2) = 0.5, そして S(3) = 1 であれば, W&sub{3};(1) = 0.29375 となる.
すべての 1 ≤ '''k''' ≤ '''n''' に対し S('''k''') = F&sub{'''k'''};/F&sub{n+1}; とする, ここで F&sub{k}; はフィボナッチ数: 初期状態 F&sub{1}; = F&sub{2}; = 1 に対し F&sub{k}; = F&sub{k-1}; + F&sub{k-2};.
例として, '''n''' = 7, つまり7人のシェフによる競技会を考えた時, それぞれを小数点以下8桁となるよう四捨五入すると, W&sub{7};(1) = 0.08965042, W&sub{7};(2) = 0.20775702, W&sub{7};(3) = 0.15291406, W&sub{7};(4) = 0.14554098, W&sub{7};(5) = 0.15905291, W&sub{7};(6) = 0.10261412, W&sub{7};(7) = 0.14247050 となる.
'''n''' 人のシェフによる競技会で作られる料理の期待数を E('''n''') で表すとしよう.
例として, E(7) = 42.28176050.
小数点以下8桁となるよう四捨五入した E(14) を求めよ.
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
