AtCoder Beginner Contest 027 C - 倍々ゲーム

倍々ゲームからバイバイ(激寒)。

問題

C: 倍々ゲーム - AtCoder Beginner Contest 027 | AtCoder

解法

スライドと言っていることは本質的に同じですが, 試行錯誤の仕方は違ったのでそっちを紹介したいと思います。

2 倍とか言っているところがビットっぽいので数字をビットで表してみて,その上で数の変遷を見ていきます。

例えば 3 は 11 ですが, 2 倍すると 110, 2 倍 + 1 すると 111 です。
5 は 2 倍すると 1010, 2 倍 + 1 すると 1011 です。

分かって欲しいのは, 要するに上の 2 つの操作は,「左シフトしつつ一番右端の数は 0 と 1 どっちにもできるよ」っていう操作である,ということです。つまり, 高橋くんと青木くんは, 各ターンごとに 右端の数を 0 にするか 1 にするかを自由に選べるということです。

これを考慮して解法を考えます。

N のビット長さを考えます。この長さを length として,length の偶奇で場合分けします。

length が偶数の場合は, 最初の x のビット列 1 にどんどん 0 か 1 を追加していくと考えると, ビット列の長さが N より大きくなるのは, 高橋くんのターンが終わった後です。
例えば, N = 10 の場合を考えると, 10 のビット列は 1010 なので,

高橋くんが 1 の右に 0 を追加する -> 青木くんが 10 の右に 1 を追加する -> 高橋くんが 101 の右に 0 を追加する -> 青木くんが何かしらの操作をすると青木くんの負け

となり, ビット列の長さが 10 より大きくなるのは高橋くんの操作が終わった後であることがわかります。

この時は, 高橋くんは操作の中で N より大きくならないよう耐え忍べば勝ち, 青木くんはビット列の長さが N のビット列の長さより大きくなる前になんとかして「N とビット列の長さが等しくて N よりも数が大きい数を錬成する」ということをできれば勝ちです。

これを解釈するとスライドの通り, 「高橋くんは常に 0 を, 青木くんは常に 1 を右端のビットに追加する」という作業をやれば良さそうです。ただ下のコードでやっていることは微妙に違っていて,

「ビットが上の方から数字を見ていく。高橋くんが動かせるビットで, N のビットが 1 のものがあればその数字を 0 にすることで『N とビット列の長さが等しくて N よりも数が大きい数を錬成する』ことが不可能になるので高橋くんの勝ち, 青木くんが動かせるビットで, N のビットが 0 のものがあればその数字を 1 にすることで『N とビット列の長さが等しくて N よりも数が大きい数を錬成する』ことが可能になるので青木くんの勝ち」

という若干実装が面倒なことをしています。

length の長さが奇数の場合も同じように考えればいけます。

せっかく const string で定義したのに cout << "Aoki" << endl; とかやってるのが面白い本番コード

ll N;
const string T = "Takahashi", A = "Aoki";

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    int length = 0;
    ll tmp = N;
    while (tmp) {
        length++;
        tmp /= 2;
    }
    if (length % 2 == 0) {
        for (int i = length-2; i >= 0; i--) {
            if ((length-i)%2 == 0) {
                if ((N>>i)&1) {
                    cout << T << endl;
                    return 0;
                }
            } else {
                if (((N>>i)&1) == 0) {
                    cout << A << endl;
                    return 0;
                }
            }
        }
        cout << T << endl;
    } else {
        for (int i = length-2; i >= 0; i--) {
            if ((length-i)%2 == 1) {
                if ((N>>i)&1) {
                    cout << A << endl;
                    return 0;
                }
            } else {
                if (((N>>i)&1) == 0) {
                    cout << T << endl;
                    return 0;
                }
            }
        }
        cout << "Aoki" << endl;
    }
    return 0;
}