問題概要
英小文字からなる文字列 が与えられる。この
に以下の操作を繰り返して空文字列にしたい。
の連続する部分文字列であって、どの隣り合う文字も等しくないものを1箇所選ぶ。それを除去し、残った部分を結合する。
その最小の操作回数を求めて、各操作において実際に操作するインデックス区間の一例を出力せよ。
制約
- マルチテストケースであり、全テストケースにおける
の合計は
以下
解法
の中で、同じ文字が隣り合っている区切り位置を抽出します。目的を達成するための手順は、まず操作によってこのような区切り位置を減らし、区切り位置が0個になったら最後に文字列全体を選ぶというものになります。
隣り合って各区切り位置を挟んでいる文字を、単にその区切り位置の文字と呼ぶことにします。区切り位置が減らないような操作は無駄であり、区切り位置を減らすための操作として以下のものが考えられます。
- 区切り位置を2個減らす操作：隣り合う2つの区切り位置であって文字が異なるものを選び、その間を除去する。
- 区切り位置を1個減らす操作：色々ある。例えば、文字列の左端から最初の区切り位置までの間を除去する。
1回の操作で区切り位置を3個以上減らすことはできません。また、区切り位置の文字を変更するような操作もできません。そのため区切り位置を2個減らす操作をする回数を最大化することが目的になります。
そのための方法は言葉で書くだけならシンプルで、
- 区切り位置の文字として最も多いアルファベット
を1つ選び、文字が
という操作を、区切り位置の文字が1種類以下になるまで行うことです。この手順によって、
- もし最初の時点で区切り位置の過半数を占めるアルファベットが存在すれば、それ以外の区切り位置の個数だけペアを作ることができる
- そうでなければ、偶奇に応じて区切り位置が0個または1個になるまでペアを作り続けることができる
ことになります。これは最適な回数を実現します。
というわけでこの問題が解けました…と言いたいところですが、実装がしんどいです。幸いアルファベットが26種類しかないので、各アルファベットごとに生きている区切り位置をsetなどで持っておいて、例えば以下のような手順を取ることでペアを作る操作をシミュレートできます。
- 区切り位置が最も多いアルファベット
- 以下のどちらかの方法で、
- それぞれの区切り位置の、現在の文字列でのインデックスを、BITなどで各区間に残っている文字数を管理することで求める。
詳しくは下記ACコードを参照してください。少し多めにコメントを付けました。