問題
https://atcoder.jp/contests/arc125/tasks/arc125a
提出
Submission #44600851 - AtCoder Regular Contest 125
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
解けた
以下、解法を書く。
最小の操作回数を考えるとき、シフトの操作の有無で話が変わってくる。
シフトの操作が必要ないとき、単純にM回になる。
シフトの操作が必要ない時とは、$S1$のみで$T$が構成されている時である。
シフトの操作が必要な場合を考えてみる。
まず、1回目のシフトは一番距離が近い$S1$の反転($S1$が0なら1,1なら0)まで動かすのが最小になる。
次に2回目以降のシフトは1回が最小になる。
なぜなら、1回目のシフトを行った時点で、0と1の境界部分まで動かしているから。
コメント