AtCoder Regular Contest 046 B: 石取り大作戦

デジャヴを感じたので。

問題概要

原文 → B: 石取り大作戦 - AtCoder Regular Contest 046 | AtCoder

高橋くんと青木くんは $N$ 個の石の山から交互に石を取るゲームを行う。交互に1個以上の石を山から取っていき、最後の石をとったプレイヤーが勝者となる。先手の高橋くんは一度に最大 $A$ 個まで、後手の青木くんは一度に最大 $B$ 個までの石を取ることができる。両者が最善を尽くした場合、勝利するのはどちらか判定せよ。

(部分点)

$A = B$ を満たすデータセットに正解した場合は40点が与えられる。
$A \neq B$ を満たすデータセットに正解した場合は60点が与えられる。
上記の2つのデータセット両方に正解した場合は100点が与えられる。

解説

前回書いたTopCoder SRM701 Div2 Hardの類題です。
記事はこちら → TopCoder SRM 701 Div 2 - hogecoder

前回と違う点は、ビットが立っている云々の制限がないのと、プレイヤーが一度に取れる石の数の最大値が同じでない場合があることですね。

ぶっちゃけいうとこれらの条件が揃っているのでTopCoderの問題よりも簡単になっています。が、やはりやりかたがわからないと解きにくいと思うので頑張って書いてみます。

まず $N \leqq A$ の場合は、自明に高橋くんが勝利します。これ以降は $N > A$ の場合について解説するものとします。

$A = B$ のとき

これは前回の記事と同様に、「山に $A+1$ 個 $(= B+1個)$ の石があったら消費するのに必ず2ターンかかる」ことを利用します。 $N$ を $(A+1)$ で割り、余りが0であれば後手(青木くん)が、0でなければ先手(高橋くん)が勝利します。

なぜそれが言えるか簡単に述べます。 $N \div (A+1)$ の商を $p$ 、余りを $q$ と置くと、 $N = p(A+1) + q$ です。先ほど述べたように、 $(A+1)$ 個の山を消費するために必要なターンは2ターンなので、 $p(A+1)$ 個の石を消費するためには $2p$ ターン必要です。余りが0の場合は $q = 0$ であるために偶数回のターンで終了し、青木くんの勝利になります。余りが0でない場合は、 $q \leqq A$ より $q$ 個消費するのに1ターンしかかからないため必ず奇数回で終了し、高橋くんの勝利になります。

$A \neq B$ のとき

この場合は、実は $A=B$ のときよりも簡単です。結論から言うと大きいほうが勝ちます。なぜこれが言えるのでしょうか。2つのパターンで考えてみましょう。

$A > B$ のとき

先手が1個の石をとって、後手がどのように取ろうとも再び先手の手番が訪れます。これは $N-1 > A-1 \geqq B$ より $N-1 > B$ が言えるため明らかです。ゲームを繰り返していくと、いずれ $N \leqq A$ の盤面で先手の手番が来るため先手必勝となります。

$B > A$ のとき

先ほどの議論と同じく、先手がどのように取ろうとも再び後手の手番が訪れ、いずれ $N \leqq B$ の盤面で後手の手番が来るため後手必勝となります。

コード

三項演算子は簡潔にかけるから好き。

Submission → Submission #958577 - AtCoder Regular Contest 046 | AtCoder

signed main() {
    int n, a, b; cin >> n >> a >> b;
    int ans;
    if(n <= a) ans = 1;
    else {
        if(a == b) {
            int x = n % (a + 1);
            ans = (x ? 1 : 0);
        }
        else ans = (a > b ? 1 : 0);
    }
    cout << (ans ? "Takahashi" : "Aoki") << endl;
    return 0;
}

山のゲームの問題はちょっと慣れた気がするけど、もうちょっと類題を知りたいなあ・・・。Typical DP ContestのB問題みたいに山が2つになったらまた難しくなるしなあ(あれは類題と言えるかどうか怪しいけど)。