CODE THANKS FESTIVAL 2014 B日程 G: 石取りゲーム

久しぶりに解説記事。またまたゲームの問題。

問題概要

原文 → G: 石取りゲーム - code thanks festival 2014 B日程 | AtCoder

$N$ 個の石が積まれた山があり、 $2$ 人のプレイヤーが交互に石を何個か取っていき、最後の石を取ったプレイヤーが勝ちとなるゲームを行う。1手で取れる石の個数は、ゲーム開始時に先手が取るときは $1 〜 P$ の範囲、それ以降は $1 〜$ (前のプレイヤーが取った石の個数) $+ 1$ の範囲である。 $N, P$ が与えられるので、両者が最善に行動した時の勝者を出力せよ。

解説

まず、solve(i, j)なる関数を考えます。これは、山に i 個石があり、1 〜 j 個の範囲で石が取れる時の勝者を bool 値で返します。

この問題で重要なことは、i と j が決まれば勝者が決まるということです。solve 関数同士の関係をみていきます。

取れる石の個数の最大値が残りの個数以上である場合、全部取れるため必ず勝てる
取れる個数を全て試して、その中でも一つでも false が返ってくれば勝てる
全て試してもヒットしなければ、勝てるパターンが無いため負け

ということが言えます。2つ目の条件でなぜ false なのかというと、ここで参照しているのは前のターンの出来事であり、先攻と後攻の扱いが逆転しているからです。したがってもう少しシンプルに書くと

i <= j ならば true
i > j のとき、1から j の範囲まで solve を試し、どこか1つでも false ならば true
false が1回も返ってこなければ false

と判定できます。もちろん、メモ化が必須です。

ソースコード

int n, p;
int dp[510][510];

// 勝敗判定
bool solve(int rest, int range) {
    // メモ化 (すでに書いてあったらそれを返す)
    int &res = dp[rest][range];
    if(res != -1) return res;

    // range が rest を覆えるならば勝てる
    if(rest <= range) return res = true;

    bool ok = false;
    // 以下は range が rest を覆えない時の話
    // 範囲の中に一つでも false
    // (つまり前のターンで後手必勝) があるなら true
    // 取る石は 1 個以上 range 以下
    repq(i,1,range) {
        // 石は i 個なくなり、範囲は i+1 になる
        if(!solve(rest-i, i+1)) ok = true;
    }
    return res = ok;
}

signed main() {
    cin >> n >> p;
    memset(dp, -1, sizeof(dp));
    bool ok = solve(n, p);
    cout << (ok ? "first" : "second") << endl;
    return 0;
}