2001/Contest/函館大会

Problem G : Nim

問題概要

妙に複雑化された石とりゲーム.

解法

flag[s,i] なる表を作って順番に埋めていく(動的計画法).ここに flag[s,i] は,石が s 個のときに,プレイヤー i がどのような手を打っても自分のチームが負かされるときに偽,それ以外のときに真をとる 2 値変数.更新規則は次にしたがう(M[i] はプレイヤー i がとることのできる最大の石数).

flag[1,i] = false
flag[s,i] = true iff ∃1≦k≦M[i] s.t. flag[s-k,i+1] = false

別解

DFS + キャッシュでも構わない.[18 Dec 2004,泉]

議論・その他


ファイルを添付する

filenim.out.txt 594件 [詳細] filenim.txt 606件 [詳細] filetadokoro_WA_nim.cc 622件 [詳細] filehirano_nim.cpp 667件 [詳細] filetaniguchi_nim.cpp 616件 [詳細] fileizumi_G.cpp 632件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: filenim.out.txt 594件 [詳細] filenim.txt 606件 [詳細] filetadokoro_WA_nim.cc 622件 [詳細] filehirano_nim.cpp 667件 [詳細] filetaniguchi_nim.cpp 616件 [詳細] fileizumi_G.cpp 632件 [詳細]

Last-modified: 2009-11-06 (金) 13:26:51 (3153d)