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，泉］

議論・その他 †

ファイルを添付する †

nim.out.txt

nim.txt

tadokoro_WA_nim.cc

hirano_nim.cpp

taniguchi_nim.cpp

izumi_G.cpp