F - Beautiful String Editorial
by 
maspy
ヒント → https://atcoder.jp/contests/agc066/editorial/9634
[0] 注意
簡単のため，文字列の長さはすべて \(3\) 以上であることを仮定します．
この解説では証明の細部を厳密に記述するとかなりの長文になってしまうため，私の他の解説と比べると細部を省略して解説しています．
[1] 差分による文字列表現
文字列 \((S_1, \ldots, S_N)\) の代わりに，列 \((S_1, S_2-S_1, S_3-S_2,\ldots,S_N-S_{N-1})\) を考えることにします．ただし引き算は，文字 A, B, C を \(0,1,2\) に対応させ，\(\mod 3\) で行います．
美しい文字列では \(S_{i+1}-S_i \equiv \pm 1\pmod{3}\) となるので，\(S_{i+1}-S_i\) の部分を +, - で表すことにします．例えば次のようになります：ABACBCAC → A+---++-
以下では，先頭の文字が A, B, C のいずれかであり，残りの文字が +, - のどちらかであるような文字列をA+-文字列と呼ぶことにします．
このようにA+-文字列への変換を行った上で問題の操作を言い換えると，行える操作は次のようなものだと分かります．スワップ位置が prefix, suffix の 2 文字であるか否かによって 3 種に分類しています．
- 操作 (1)
+++を---に変化させる．---を+++に変化させる．
- 操作 (2)
A++をB--に変化させる．B++をC--に変化させる．C++をA--に変化させる．A--をC++に変化させる．B--をA++に変化させる．C--をB++に変化させる．
- 操作 (3)
- 末尾 2 文字について，
++を--に変化させる． - 末尾 2 文字について，
--を++に変化させる．
- 末尾 2 文字について，
なお，長さ \(2\) の文字列も考えると A+ → B- というこれらの操作に当てはまらない操作が生じてしまいますが，冒頭に注意したように本解説ではそのような場合の扱いは省略しています．
[2] 操作 (1) のみを考慮する場合
\(2\) つの文字列が操作 (1)の繰り返しによりうつり合うのはどういうときかを考えます．
次の操作を導入します．
- 操作 (1’)
+++を削除する．---を削除する．
操作 (1’)は文字列長を減らす操作なので，同じ文字列に対して有限回しか行えません．A+-文字列 \(S\) に対して，操作 (1’) を可能な限り繰り返して得られる文字列を \(f(S)\) と書くことにします（これは一意に定まります）．次が成り立ちます：
【命題 1】 同じ長さのA+-文字列 \(S_1\), \(S_2\) に対して次は同値である．
(a) \(S_1\) と \(S_2\) は操作 (1) の繰り返しにより互いにうつり合う．
(b) \(f(S_1)=f(S_2)\) が成り立つ．
証明は省略しますが，本質的には
https://atcoder.jp/contests/agc050/tasks/agc050_b
の公式解説冒頭の議論と同じなので，必要があれば参照してください．
[3] すべての操作を考慮する場合
[2] の内容を，操作 (2), (3) も使える場合に適用できるように修正しましょう．さらに次の操作を導入します．
- 操作 (2’)
A++-をBに変化させる．B++-をCに変化させる．C++-をAに変化させる．A--+をCに変化させる．B--+をAに変化させる．C--+をBに変化させる．
- 操作 (3’)
- 末尾の
-++を削除する． - 末尾の
+--を削除する．
- 末尾の
操作 (2’)，(3’) は，それぞれ操作 (2)，(3) と操作 (1’) を組み合わせたものです．
操作 (1’), (2’), (3’) は文字列長を減らす操作なので，これらは同じ文字列に対して有限回しか行えません．そこで，A+-文字列 \(S\) に対して操作 (1’), (2’), (3’) を可能な限り繰り返して得られる文字列として \(g(S)\) を定義することを考えます．
この結果は一般には一意ではないので，適切に写像を定義するために便宜上，操作手順を一意に定める次の定義を採用します．
【定義】 \(S\) に対して次のアルゴリズムの出力を \(g(S)\) と定める．
- 操作 (1’) を適用できるならば，そのうち最も左に適用し，1. に戻る．適用できないならば，2. に進む．
- 操作 (2’) を適用できるならば適用し，1. に戻る．適用できないならば，3. に進む．
- 操作 (3’) を適用できるならば適用し，1. に戻る．適用できないならば，その時点の \(S\) を出力とし，アルゴリズムを終了する．
このとき，次が成り立ちます．
【命題 2】 同じ長さのA+-文字列 \(S_1\), \(S_2\) に対して次は同値である．
(a) \(S_1\) と \(S_2\) は操作 (1), (2), (3) の繰り返しにより互いにうつり合う．
(b) 次のいずれかが成り立つ：
- (b1) \(g(S_1) = g(S_2)\)
- (b2-1) \(g(S_1), g(S_2)\) はともに
A+,B-のいずれか．- (b2-2) \(g(S_1), g(S_2)\) はともに
B+,C-のいずれか．- (b2-3) \(g(S_1), g(S_2)\) はともに
C+,A-のいずれか．- (b3) \(g(S_1), g(S_2)\) はともに
A++,A--,B++,B--,C++,C--のいずれか．
簡単に証明の方針のみ述べます．
(a) を仮定して (b) を導くには，\(S_1, S_2\) が \(1\) 回の操作 (1), (2), (3) でうつりあう場合に示せばよく，帰納法により証明できます．詳細は省略しますが，難しくはないと思います．
(b) を仮定して (a) を導くことを考えます．簡単のため (b1) の場合について述べます．まず，操作 (1’), (2’), (3’) は文字列長を減らしますが，代わりに文字列長を保つ操作として，操作 (1’), (2’), (3’) を行ったあと末尾に +++ を補う操作を定義します．この操作が操作 (1), (2), (3) の合成で書けることを示しましょう．この際【命題 1】が役に立ちます．
次に，\(h(S)\) を，\(g(S)\) の末尾に + を適切な個数追加して \(S\) と同じ長さにしたものとして定めます．上で述べたことより \(S\) から \(h(S)\) に操作 (1),(2),(3) の合成でうつせることが分かります．\(g(S_1) = g(S_2)\) ならば \(h(S_1)=h(S_2)\) ですが，このとき \(S_1, S_2\) から共通の文字列に操作 (1),(2),(3) の合成でうつせるため，\(S_1\) から \(S_2\) に操作 (1),(2),(3) の合成でうつせることが分かります．
(b2-1) を示すには，上の議論に加えて，「A+, B- の末尾に + を \(3n\) 個追加したA+-文字列同士が操作 (1),(2),(3) の合成でうつせることを確かめればよいです．本解説で文字列長が \(2\) 以上であることを仮定していることに注意して，操作 (2),(3) を 1 回ずつと操作 (1) を \(n-1\) 回行うことを考えれば示せます．
(b3) も同様なので省略します．
以上で，本問題の操作でどのような \(2\) つの文字列がうつりあうのかが理解できました．
なおこれらの証明をよく観察すれば，\(g(S)\) を定めるアルゴリズムにおける操作手順が重要でないことも分かります．実際操作 (1’), (2’), (3’) を任意の順序で行った結果を \(g(S)\) と定めようとすると，\(g(S)\) の定義に A+ と B- のどちらが得られるかといった不定性が残るものの【命題2】に相当する主張は成り立ちます．
[4] 辞書順最小化
【命題2】により，次の問題が解ければよいです：
A+-文字列 \(T\) が与えられる．\(g(S)=T\) となる \(S\) のうちで辞書順最小のものを求めよ．
操作 (1’), (2’), (3’) を逆にたどることを考えれば，\(S\) は \(T\) に対して
- 操作 (1”)
+++を追加する．---を追加する．
- 操作 (2”)
AをB--+またはC++-に変化させる．BをC--+またはA++-に変化させる．CをA--+またはB++-に変化させる．
- 操作 (3”)
- 末尾に
-++を追加する． - 末尾に
+--を追加する．
- 末尾に
を繰り返し行うことで得られるものです．
辞書順最小化に際しては，先頭部分になるべく長い ABABAB... という並び（A+-文字列の言葉でいえば A+-+-+-... という並び）を作ることを考えます．すると操作 (2”), (3”) の回数を固定すれば，最適な操作 (1”) の方法は容易に決まります．
基本的には操作 (2”), (3”) の回数が大きくなると，作れる A+-+-... 部分の長さが小さくなるという関係があるため，操作 (2”), (3”) の回数を適当な範囲で全探索してしまうというのが簡潔な実装方法だと思います．
以上により本問題は \(O(|S|)\) 時間で解くことができます．
posted:
last update: