AtCoder Grand Contest 037 A - Dividing a String
お題箱より。
貪欲とDPどちらを書こうか迷いましたが、貪欲解法のほうで書きたいと思います。
問題概要
文字列 が与えられる。この
をできるだけ多くの部分文字列に分割したい。ただし、隣り合う2つの部分文字列が一致してはならない。
最大でいくつの部分文字列に分割できるか答えよ。
※以降の解説では文字列 の長さを
と表記します。
解法
貪欲法、つまり前からできるだけ短い文字列で切っていくという手順で解く方法を試してみましょう。
- ルール1：前から文字列を見て、なるべく1文字ずつ切っていく。ただし「直前に1文字で切っていて、かつ今から見る文字がその文字と同じ」という時だけ2文字で切る。
このルールで入力例2の aaaccacabaababc を切ると以下のようになります。数えると出力例と同じ12分割です。
ただしこれだけのルールだと、入力例1の aabbaa や aaaaa などのケースで困ります。
このように最後に残った2文字が同じ場合、貪欲に1文字で切ると最後に残った1文字と等しくなってアウトです。このようなケースのために、末尾2文字を見る時だけ次のルールを課します。
- ルール2：最後に2文字残り、それらが同じである場合、その2文字をそのまま採用する。もしその2文字も直前に切った2文字の文字列と一致してしまう場合、その4文字を3+1文字と割り振る。
3+1文字になるのは以下の図のような場合です。
結論を言ってしまうとこれで最適な分割方法を実現できるので、前からシミュレーションすると正解を求めることができます。
ただ貪欲法にありがちなこととして、このような貪欲で解けると仮説を思いつくことよりも、その正しさを証明することのほうが難しいです。証明しましょう。
証明
先ほどの貪欲ルールで2文字または3文字になってしまったところには、それぞれ原因となった「同じ文字が隣接している箇所（以下、原因箇所）」が存在します。貪欲ルールで得られた分割数が である場合、全部1文字で切れた場合と比べて損をした
と同じ数だけこの原因箇所が存在します。
ルール2で3+1になっている場合は以下のように考えると原因箇所が2つあります。
このように入力が aaaaa... と最も厳しい場合でも、貪欲ルールでは1+2+1+2+...のような切り方ができるので、この原因箇所は少なくとも1文字の間を空けて並んでいるはずです。
どのような切り方であっても、この原因箇所を挟んでいる2文字を両方とも1文字で切ることは条件違反なのでできません。また、2文字の文字列を1つ作ることで2箇所の原因箇所を潰すこともできません。原因箇所を潰すためには、原因箇所1つにつき2文字以上の文字列を1つ作るか、複数の原因箇所を潰すために長い文字列を作る必要があります。つまり原因箇所1つにつき少なくとも1文字ぶん損をする必要があります。
ここで貪欲ルールは「原因箇所1つにつきちょうど1文字ぶんだけ損をしている」切り方になっていました。これは実現できるギリギリの損の数です。よって、貪欲ルールによる分割数は最適であるということが示されました。
ACコード
Submission #12541470 - AtCoder Grand Contest 037
「直前が1文字であるかどうか」のフラグを持ってシミュレーションします。最後にルール2に引っかかる場合は、どちらのケースであっても「最後の2文字を使って分割個数が1増える」と見なすことができるので、実装上は区別する必要ないです。
おまけ：DPの場合
DPのほうが正当性を証明するのは楽なのですが、DPそのものへの慣れが必要なので今回の記事では見送りました。
DPの場合でも全くの無考察で解けるわけではなく、計算量を削減するためには「最適解に登場する部分文字列の長さは長くならない」という考察をする必要があります。またこれを文字数だけで容易に証明できるのは「最適解に登場する部分文字列は4文字以下である」というところまでで、公式解説や多くのDP解法記事で書かれている「2文字以下」というところまで示すには結局さっきの貪欲法と同じようなことを考える必要があります。なので、証明の理解まで含んだ時に最も易しい解法は「4文字以下まで絞ってDP」だと思います。
証明も書いておきます。ある分割方法に5文字の部分文字列が存在すると仮定します。5文字の部分文字列をさらに、文字数の異なる2つの部分文字列に分割することを考えます。この方法は1+4, 2+3, 3+2, 4+1の4通りあって、そのうち前とも後ろとも隣接する部分文字列の文字数が一致しないものが少なくとも2通り存在します。つまり、この分割方法はさらに分割数を増やすことができるので最適ではありません。
6文字以上の部分文字列を含む分割方法も、同様の手順で最適ではないことを示せます。よって「最適解に登場する文字列は4文字以下である」ことが示されました。
