Problem 477 「数列ゲーム」

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

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

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

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

  • プレーヤー 1: 先頭の数を取り除く (1)
  • プレーヤー 2: 残りの数列から末尾の数を取り除く (3)
  • プレーヤー 1: 残りの数列から末尾の数を取り除く (10)
  • プレーヤー 2: 残りの数を取り除く (2)

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

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

  • s1 = 0
  • si+1 = (si2 + 45) modulo 1 000 000 007

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

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

F(108) を求めよ.


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