Problem 391 のバックアップ(No.1)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• Problem 391 へ行く。
  • 1 (2012-07-01 (日) 10:41:08)

Problem 391 「ホッピングゲーム」 †

0 から k までの数を2進法で書き下したときの 1 の個数を sk としよう.
例えば, 0 から 5 までを2進法で書くと, 0, 1, 10, 11, 100, 101 となる. 7つの 1 があるので, s5 = 7 となる.
数列 S = {sk : k 0} は {0, 1, 2, 4, 5, 7, 9, 12, ...} で始まる数列となる.

2人で行うゲームがある. ゲーム開始前に, ある数 n を選んでおく. カウンタ c があって, それは 0 から始まる. それぞれの局面で, 対局者は 1 から n (nを含む) までのある数を選び, その数だけ c を増やす. その結果得られる c の値は数列 S の要素でなければならない. もしそのような有効な指し手を打てない場合, 対局者は負けとなる.

例を示そう :
n = 5 とし, c は 0 から始まる.
先手は 4 を選び, c は 0 + 4 = 4 となる.
後手は 5 を選び, c は 4 + 5 = 9 となる.
先手は 3 を選び, c は 9 + 3 = 12 となる.
以下同様.
留意すべき点として, c は常に S に属していなければならない, そしてそれぞれの対局者はたかだか n までの数で c を増加させていくことができる.

先手必勝となるように先手が最初の局面で選べる一番大きい数字を M(n) とし, そしてそのような指し手がない場合は M(n) = 0 としよう. 例えば, M(2) = 2, M(7) = 1, M(20) = 4 となる.

1 ≤ n ≤ 20 のとき Σ(M(n))&sup{3}; = 8150 がすでに与えられている.

1 ≤ n ≤ 1000 のときの Σ(M(n))&sup{3}; を求めよ.