ABC027 - C - 倍々ゲーム
概要
Nが与えられる。最初がx=1で、高橋君と青木君が交互に次の操作のうちのどれかをする。先手は高橋。
- xを2xにする。
- xを2x+1にする。
自分の番で操作してNを超えたらその人の負け。Nが与えられるので、その時が誰が必勝なのかを答えてください。
制約： 1 <= N <= 10^18
ACするまで
1. 1~15ぐらいの勝敗表を作ってもよくわからない。
2. x->2x or 2x+1 これは、セグ木の子供の番号の遷移だよね！？
3. 1から任意の自然数yへ遷移する道筋は、二分木からわかる通り一意的。
4. 二分木を書いてみて、ボーダーラインを切ってみると、関係性が見えてくる。
解説
https://www.slideshare.net/chokudai/abc027
解説スライドの図が非常にわかりやすい。
今回の場合、x->2x or 2x+1はセグメント木などに代表される完全二分木の頂点番号の割り振り方として知られていて、これは明らかに1から特定の数までの道筋は一意に決まる。
ついでに、二分木を書いてみると、ボーダーの切り方によっては、「高橋が越える」と「青木が越える」はNの二分木での深さによって左右は異なるが、「高橋が越えるが左」＆＆「青木が越えるが右」もしくは、「高橋が越えるが右」＆＆「青木が越えるが左」の2パターンになる。
よって、高橋と青木はそれぞれ逆方向にできるだけ行けばよい。
ACソースコード：
Submission #12553569 - AtCoder Beginner Contest 027
一言
なし
