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点はさすがに嘘な気がするけどとても面白い問題だと思います。