AtCoder Beginner Contest 027 C 倍々ゲーム - kamojirobrothersのブログ

ABC027のCが面白かったので。

問題概要

A, Bがゲームをする。正整数Nが与えられる。
$x=1$ で初期化する。

$x$ を $2$ 倍するか、 $2$ 倍した後、 $1$ を加算する

Aさんから行い、 $N$ を超える操作を行った方が負け。

解説

操作を言い換えると、次のようになります。

$x \mapsto x<<1$
$x \mapsto (x<<1) + 1$

ここから、 $n \, (n \geq 0)$ 回目の操作の後の $x$ は以下を満たすことがわかります。

$100\ldots 000 = 2^n \leq x < f^n(1) = 111\ldots 111 = 2^{n+1}-1$

ここで、 $f(x) = 2x+1$ とします。

$x = N$ のときの、 $n$ を固定します。

つまり、このゲームの決着がつくのは、 $n$ 回目か、 $n+1$ 回目ということになります。

$n$ 番目の人は、 $x$ の範囲は変えられませんが、 $x$ が $N$ を超えなければ勝てます。

従って、 $n$ 番目の人は $x$ の値ができるだけ小さくなる操作( $x \mapsto 2x$ )を、
そうでない人は、 $x$ の値ができるだけ大きくなるような操作( $x \mapsto 2x+1$ )を行うことが最適となります。

解答

from math import log2
def main():
    N = int( input())
    M = int( log2(N))
    x = 1
    for i in range(M):
        if M%2 == 0:
            if i%2 == 1:
                x = 2*x
            else:
                x = 2*x+1
        else:
            if i%2 == 0:
                x = 2*x
            else:
                x = 2*x+1
    if M%2 == 0:
        if x <= N:
            print("Aoki")
        else:
            print("Takahashi")
    else:
        if x <= N:
            print("Takahashi")
        else:
            print("Aoki")
        
if __name__ == '__main__':
    main()