プログラミングコンテストチャレンジブック 4-2 その1

4-2 「ゲームの必勝法を編み出せ」です。

• コインのゲーム1 - コインを交互に取るゲームで先手必勝か後手必勝か判定する問題
  • j 枚で自分の手が回ってきたら勝ちか負けかを反転して動的計画法
• A Funny Game - 円状に並んだコインを交互に取るゲームで先手必勝か後手必勝か判定
  • 隣あうコインしか同時には取れないので状態がとても多くなる
  • 実は連続するコインが対応する2つの部分にできたら勝ち。シンプルなロジックだけで解ける(n の奇遇判定するだけ)珍しい問題ですね
• Euclid's Game - ユークリッドの互除法を元にしたゲーム。自分の手番で2つの数のペアのどちらかを0にしたほうが勝ち
  • 引き算の自由度が2つ以上ある状態に先になったほうが勝ち
• Ni - 石の山がn個あり交互にどれかの山から石を取って最後に取ったほうが勝ち
  • a1 XOR a2 XOR a3 XOR ... XOR an != 0 なら勝ち、0 なら負け

ゲームの先手後手必勝の判定はプログラム自体は簡単でロジックを考えるところが中心になる問題が多いようですね。