解法
できる操作が、
1をひとつ左に動かす連続する
1を消す
のどちらかとなっています。
また、右側にある 1 が、一つ左側の 1 を追い越すことはできません(そもそも、追い越したいのであれば、左側の 1 を動かせばよいです)。
そのため、元々で与えられた
1 の順序は変化しないまま、左に移動するか、消えるか、その位置のままか、のパターンしかありえないことがわかります。
が
1 のときに左に移動させる(もしくは据え置き)パターンは、それより左側に、まだ位置を確定させていない 1が存在しないが、が
1 となっているものが存在するパターンです。が最小となっている箇所に優先的に移動させないといけないため、
回の操作が必要になります。
が
1 のときに消すパターンは、上記のようなが存在しないときです。どこへ移動させても
と一致することがないので、
が
1 となっている最小のを見つけ、その
1 と合わせて打ち消します。これにはコストがかかります。
以上のことをシミュレートし、最終的にと
が一致すればよいです。
queueを2つ使い、と
でまだ消すべきなのに消してない/
1にすべきなのにが
1になっていない位置をメモし、消すべき1から優先的に上記の処理を行います。
