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

hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

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

AtCoder ゲーム問題

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

問題概要

原文 → 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;
}

前にこのブログで紹介したゲームの問題の中にも、同じ方針で解けそうなものがありますね。ゲームの問題も奥が深いですね。

※追記: 前に紹介した問題たちは制約が大きいのでそもそもメモ化できないですね。同じような問題ですがこの解法は使えないです。難しいなあ・・・