AGC022 E Median Replace

 AGCお疲れ様でした。EのMedian Replace(E: Median Replace - AtCoder Grand Contest 022 | AtCoder)の解法です。公式の解説が天才すぎたのですけど別の方法で解けたので書きます。

 場合の数をいきなり考えるのは難しいのでとりあえず判定問題を考えます。

 まずいろいろと実験してみると最初の2文字が11だとそれ以降の並びによらず美しい文字列なことがわかります。また、左から順番に見ていったときに、1はなるべく最後まで残すべき(111→1とか110→1とかの操作は極力しない)なことや、0が2つ以上連続していたらそこはさっさと潰して0が1つだけの状態にしてしまったほうがいいということが(直感的にですが)わかります。

 以上をまとめると文字列abcde...が与えられたときにとるべき戦略は

  1. 01cde...のとき:前の01は残しておいたほうがいいのでcde…以下で1をつくれる、つまりcde...が美しい文字列ならよいです。
  2. 00cde...のとき:前の00cは潰して0にするしかないので、0de...が美しい文字列ならよいです。
  3. 11cde...のとき:cde...以下によらず美しい文字列です。
  4. 101de...のとき:前の10は残しておいたほうがいいので、1de...以下が美しい文字列ならよいです。
  5. 100de...のとき:00dの部分を潰して0にしてしまうのが最適で、残る10e...が美しい文字列ならよいです。

 これで、与えられた文字列に対して1回の操作ごとに最低でも長さが2縮まるDPを書けてO(N)で判定することができます。

 数え上げも本質的には同じで、dp[n][a][b]で「n文字の文字列でabで始まるもののうち美しい文字列の個数」とすれば上記と同じ遷移が書けます。?がでてきたときは1と見たときと0と見たときの場合の数を足せばよいです。

 2と5のパターンはそれぞれc、dが?のときは2倍しなきゃいけないみたいな罠があったりするのですがこれでO(N)で解くことができました。

 https://beta.atcoder.jp/contests/agc022/submissions/2289522

 一応コードも貼っておきましたが可読性が死んでます。

 

 ところでこれを通せたのがコンテスト終わってから15分後くらいっていう、、、。

 コンテスト中に通せなかったのは一か所1にしなきゃいけないところが?も許容しちゃってたからなんですけどコンテスト中は気づけないもんですね。Atcoder苦手すぎてつらい。

 しばらくAGCも多いのでどこかで結果が出せたらいいなぁと思います。では。