二進表記に対する操作への言い換え

各非負整数を二進表記にし、文字列として扱うことにします。(ただし、\(0\) の二進表記は空文字列とします)

すると、\(2\) 種類の操作は以下のようになります.

• ある \(A\) の非空文字列の末尾の文字を削除
  
• ある \(B\) の非空文字列であって末尾が \(0\) であるようなものの末尾の文字を削除

後者では \(A\) の要素を \(2\) 倍する代わりに(最終的に)対応する \(B\) の要素を \(\frac{1}{2}\) 倍することにしています。

トライ木の利用

文字列の集合を根つき木で扱うデータ構造としてトライ木と呼ばれるものがあります。本問題はこれを考えることで解法を導くことが出来ます。
\(A,B\) の文字列を考えてトライ木を構築します。すると、各操作は文字列を根側に移動させる操作となります。
これを考えると、葉側の頂点から順番に \(A,B\) の文字列が両方存在するなら貪欲にマッチさせて排除、余ったものは根側へ移動( \(B\) の文字列は末尾が \(0\) でないと根側に移動できないのでその場合は -1 と出力して終了)とし、すべてマッチさせることが出来た場合は移動の回数を出力すれば良いです。
トライ木の構築やDFSにかかる \(\mathrm O(N\log A_{max})\) がそのままこの解法の時間計算量となります。
あるいは、map等を用いて大きな値から順に処理をすることでほぼ同じ内容のシミュレーションを実現できます。(この場合は \(\mathrm O(N\log N\log A_{max})\) になります)