ABC243 D - Moves on Binary Tree (400)
現在地を愚直に記録しようとすると最悪の場合$ 2^{\frac{n}{2}}まで大きくなるため不可能
最終的な値がlong longに収まるのでそれを越える部分は何回越えた状態かのみカウントする(OCとする)
それぞれの操作は以下のようになる
上に行く場合
OCがあれば1減らす
そうでなければ現在の値を2で割る
左に行く場合
OCがあるか移動した結果$ 10^{18}を越えるならOCを1増やす
そうでなければ現在地を二倍する
右に行く場合
OCがあるか移動した結果$ 10^{18}を越えるならOCを1増やす
そうでないばら現在地を2倍して1足す
明らかに$ \mathcal{O}(N)