Problem 477 「数列ゲーム」

数列ゲームは一列に書かれた N 個の要素を持つ数列 S から始まる.

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

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

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

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

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

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

F(2) = 45, F(4) = 4284990, F(100) = 26365463243, F(104) = 2495838522951 が与えられている.

F(108) を求めよ.


トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS