Problem 477 「数列ゲーム」

数列ゲームは一列に書かれた N 個の数からなる数列 S から始まる.

2人のプレーヤーが交互にターンを交代する. ターンが来ると, プレーヤーは数列に存在する先頭か末尾の数のどちらかを選択し取り除く.

プレーヤーの得点は取り除いた全ての数の合計となる. それぞれのプレーヤーは自身の得点の合計を最大化するよう努める.

N = 4, そして S = {1, 2, 10, 3} のとき, 以下のようにそれぞれのプレーヤーは自身の得点を最大にしていく:

プレーヤー 1 の得点は 1 + 10 = 11 となる.

下記のように定義された数列 S = {s&sub{1};, s&sub{2};, ..., s&sub{N};} においてプレーヤー双方が最適な戦略に従った時のプレーヤー 1 の得点を F(N) としよう:

この数列は S = {0, 45, 2070, 4284945, 753524550, 478107844, 894218625, ...} から始まる.

F(2) = 45, F(4) = 4284990, F(100) = 26365463243, F(10&sup{4};) = 2495838522951 が与えられている.

F(10&sup{8};) を求めよ.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2014-08-24 (日) 00:42:39