2022-01-10 AGC049 : AtCoder Grand Contest 049 B - Flip Digits を解いた

AGC049 : AtCoder Grand Contest 049 B - Flip Digits を解いた。 https://atcoder.jp/contests/agc049/tasks/agc049_b

特定の操作を繰り返すことで S を T にできるか。最小回数はいくつか。

考えたこと:

00 のときなにもできない
01 のとき 10 にできる
10 のときなにもできない
11 のとき 00 にできる

これらの操作は↓の操作と解釈できる。

1 を左に動かす (ただし左端からは動かせない)
2 つ連続する 1 を消す

消す操作は 2 個ずつなので偶奇の変化はない。

1 の個数は増やせないので S の 1 の個数が T のそれ未満なら -1 。 1 の個数の偶奇の変化はないので S の 1 の個数と T のそれの偶奇が異なるなら -1 。 1 は左には移動できるが右には移動できないので S の右端の 1 より右側に T の 1 があれば -1 。気持ち的には右から合わせていきたい。左を先に片付けないと右を合わせられない。左から合わせる。

個数を合わせてから移動する？と良さそう。個数を合わせるにはどうすればいいか。右端からの累積和を取って比較し、 T のその位置で多い分を消す。

例 3 だと↓なので……

10111
01010

累積和は↓。

012345 # 位置
433210
221100

これで操作を考えると……

左に動かすと 33 を 32 にできる
2 つを消すと 43 を 22 にできる

……

このあたりまで考えて諦めた。

公式解説: https://atcoder.jp/contests/agc049/editorial/330

よく分からない。

参考: https://zenn.dev/wapa5pow/articles/agc049-b-14e544392d0df7a7f711

なるほど。わかりやすい。 S_i != T_i なら 1 を持ってくることでしか合わせられない。ただ合わせるとそれぞれについて走査する必要があるので O(N^2) になってしまう。そこで最後に探した 1 の位置を保持しておくことで O を下げている。確かに間に合う。

セキュア・バイ・デザインを読み進めている。

上の子のための本やはさみを買った。

今日のコミット。