ARC094 F Normalization

　はい。ARC094のF問題(F - Normalization)の解法です。解説(aを0、bを1、cを2だと思うと和のmod3が保たれるとかいうやつ)がド天才だったのですが、もう少し思いつけるかもしれない解法でACしたので投稿します。

　といっても結局mod3を見ることにはなってしまうのでそこに至るまでのステップも書いていこうかと思います。

解法

　まず、操作後の文字列はどこかに同じ文字が連続する部分があるということはすぐに分かるのですが、それだけでは条件が足りなさそうです。また、操作の順番によってできる文字列が変わる(というか操作の順番を変えるとそもそも操作ができなくなることもある)ので左から順番に操作するorしないでDPといったことも出来なさそうです。ということで別の方向で考えてみましょう。

　数列や文字列に対して何らかの操作を施すタイプの問題では、

操作の前後で変化しないものに着目する
という方法が有効なことがあります。また、今回のように操作が3種類ある場合すべての操作に対して共通してなりたつものを見つけるとよいです。具体的に今回の問題の操作での個数の変化を見てみましょう。
  1. ab→cc　　　a：-1、b：-1、c：+2
  2. bc→aa　　　a：+2、b：-1、c：-1
  3. ca→bb　　　a：-1、b：+2、c：-1

「2増える」「1減る」という操作を同一視したいなぁという気持ちになりますね(なって。)。この時点でmod3に気づく人もいるかもしれませんが、さらにこれもよくある手法として、「個数の差(和)はわりといい性質を持ちがち」というのがあります。ということで各操作でのaの個数とb,cの個数の差の変化を見てみましょう。

  1. ab→cc　　　a：-1、b：-1、c：+2　　b-a：±0、c-a：+3
  2. bc→aa　　　a：+2、b：-1、c：-1　　b-a：-3、c-a：-3
  3. ca→bb　　　a：-1、b：+2、c：-1　　b-a：+3、c-a：±0

　「aとbの差」「aとcの差」は操作の前後で「3増える」「変わらない」「3減る」のいずれかです。もうわかりますね。操作の前後で「aとbの差」「aとcの差」を3で割った余りは変化しないということです。なるほどここで3で割った余りがでてくるのか、という感じですね。3で割った余りがカギになることに気が付いてさらに考察を進めると解説の方針になるのかなぁ。

　とはいえこれで操作後の文字列に対する重要な性質がわかりました。

  1. どこかに 連続している部分がある

  2. 「aとbの差」「aとcの差」を3でわった余りは最初の文字列と同じ。

この性質をみたす文字列は本当に全部つくれるのかという問題はあるのですが、実は|S|≠3のときはできるらしいです。(証明は帰納法でできるらしい。解説に書いてた。)ということで|S|=3のときだけ全探索することにして、他は上の条件をみたすようなものを数えるためのDPをします。

　具体的には、dp[文字数][最後の文字][(b-a)を3で割った余り][(c-a)を3で割った余り] のようなdpテーブルを2つもって、1つで「2の条件をみたすもの全部」、1つで「2の条件を満たすが連続する箇所は1つも持たないもの」を計算して差をとるのが楽な気がします。

　ということでこれでこの問題をO(27*|S|)くらいで解くことができました。最初の文字列が連続箇所を持たない場合は答えに1足すのも忘れずに。一応自分のACコードのリンクを貼っておきます。

Submission #2374335 - AtCoder Regular Contest 094

 

※追記

　少し考察すると「aとbの差」のmod3が保たれるなら「aとcの差」のmod3も自動的に保たれることがわかるため、dpテーブルは、dp[文字数][最後の文字][(b-a)を3で割った余り]と1つ項を減らして計算しても大丈夫なようです。(Submission #2374698 - AtCoder Regular Contest 094)

感想

　本番中にこの性質に気づけていながら手計算の実験部分を間違えていて解けなかったのはちょっと悔しい。|S|=3の場合だけ無理というのも罠でした。短すぎる文字列なら例外がおこりうることには思い至るべきだったなぁ。700点はさすがに嘘な気がするけどとても面白い問題だと思います。

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も多いのでどこかで結果が出せたらいいなぁと思います。では。