Codeforces Round 760 (Div. 3) F – Reverse を解いた記録
問題の概要
正の整数\(x, y\)が与えられる．\(x\)に対して次の操作を0回以上行うことで\(x\)を\(y\)と一致させられるか否かを答えよ．
- 2進表記に直した\(x\)の右側に1または0を付け加え，\(x\)を反転させて leading zero を取り除く．その後，\(x\)を10進表記に直す．
制約
- \(1 \leq x, y \leq 10^{18}\)
- 入力はすべて整数
解法
実際にやってみるとわかるのですが，\(x\)から件の操作を行うことで作り出せる数（ただし\(10^{18}\)以下）はそれほど多くありません．
幅優先探索などで\(x\)から作り出せる数を全列挙し，\(x\)から作り出せる数の中に\(y\)があるかを調べれば良いです．
お気持ち
- 0を右に付け加えても反転＆ leading zero 削除により消し飛ぶので，元の数より大きい数を作りたければ「右に1を付け加える」1択
- \(x\)から作れる数は，2進表記に直すと先頭と末尾が必ず「1」になる…先頭と末尾の0は leading zero 削除で飛んでしまうため
- 初手を除けば元の数より桁数が少ない数は作れない…\(x\)から作れる数は，2進表記に直すと先頭と末尾が必ず「1」になるから
以上を踏まえると\(x\)から作り出せる数の個数はそこまで多くはなさそうな気分になります．
実装例