bouzuya.hatenablog.com

ぼうずやのにっき

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(N2) になってしまう。そこで最後に探した 1 の位置を保持しておくことで O を下げている。確かに間に合う。

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

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

今日のコミット。