読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

N言っちゃダメゲームの判定式

以下の2問のおかげでやっと「N言っちゃダメゲーム」の一般的な判定式を理解することができたので、考え方とともにメモしておく。

No.8 N言っちゃダメゲーム - yukicoder

No.249 N言っちゃダメゲーム (2) - yukicoder

「N言っちゃダメゲーム」とは

  1. まず先攻のプレイヤーは 0 が与えられる。
  2. そこから N 以上を宣言しないように(宣言したら負けになる)与えられた整数に 1~K のどれかの整数を加算したものを宣言し相手プレイヤーに渡す。
  3. 勝負がつくまで代わり代わりに 2. を繰り返す。

(引用:No.249 N言っちゃダメゲーム (2) - yukicoder)

判定式

(N-1) % (K+1) != 0 のとき先手必勝。他のとき後手必勝

(図を入れる予定)