A - My Last ABC Problem Editorial by evima
単一の文字列 \(S\) について答えを求める方法を考えます。
\(S\) を、循環する文字列とみなします(つまり、最初の文字と最後の文字が隣接しているとします)。すると、操作はこの循環文字列のどの区間にも適用できることに注意します(ある置換をある区間に施すことは、その逆置換を文字列の残りの部分に施すことと同等です)。
隣接する異なる文字のペアの個数を \(k\) とします。最終的に、そのようなペアは消え、\(k\) は \(0\) となります。一方で、一回の操作で \(k\) を \(2\) より多く減らすことはできません。なぜなら、ペアが消える可能性があるのは、ペアの片方の文字のみが操作を適用する区間の内部にあり、もう片方が外部にある場合に限られるからです。よって、答えは \(\lceil \frac{k}{2} \rceil\) 以上です。
実は、この回数以下の操作で必ずすべての文字を同じにできます。\(k \ge 4\) のとき、一回の操作で上記のペアの数を \(2\) 減らすことが必ず可能であることを示しましょう。それら \(k\) 個のペアすべてのうち、含む文字の集合が同じであるような \(2\) 個を適当に選びます(そのような文字の集合は、AB
, BC
, CA
の \(3\) 通りしかありえません)。一般性を失うことなく、文字集合が AB
のペアが \(2\) 個あるとします。そのとき、それらのペアからちょうど一文字ずつを含むような区間を選び、置換 \((X, Y, Z) = \)B
, A
, C
を施すと、それらのペアは消えます。
\(k = 3\) の場合は、同じ要素をすべて削除すると、文字列 ABC
のみが残ります。これは、\(2\) 回の操作で AAA
に変えられます。\(k = 2\) の場合は、AB
のみが残り、\(1\) 回の操作で AA
に変えられます。\(k = 1\) ということはありえません。
posted:
last update: