*[[Problem 459:http://projecteuler.net/problem=459]] 「どんでん返しゲーム」 [#b3009e88]

どんでん返しゲームとは N x N マスの盤面でプレイする二人用のゲームである.~
それぞれのマスには片面が白,もう片面が黒のコマが置かれている.~
ゲームはすべてのコマの白い面が見える状態からスタートする.

対局では、以下の性質を持つ長方形の中のすべてのコマを裏返す:
対局では, 以下の性質を持つ長方形の中のすべてのコマを裏返す:

- 長方形の一番右上のマスは白のコマ
- 長方形の幅は完全平方数 (1, 4, 9, 16, ...)
- 長方形の高さは三角数 (1, 3, 6, 10, ...)

#ref(p459-flipping-game-0.png,center,nolink)

対局者は交互に上記の作業を行う. すべてのマスを黒に変えたものが勝者となる.

すべてが白いコマの状態になっている N x N の盤面で, 完璧な対局を行うと仮定した時, 先手必勝となる手 (相手がどんな手を差しても勝つことができる最初の手) の数を W(N) としよう.~
W(1) = 1, W(2) = 0, W(5) = 8, そして W(10&sup{2};) = 31395.

N=5 の場合, 8つの先手必勝の手がある:

#ref(p459-flipping-game-1.png,center,nolink)
&br;
#ref(p459-flipping-game-2.png,center,nolink)

W(10&sup{6};) を求めよ.

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS