ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Grand Contest 037 A - Dividing a String

お題箱より。

A - Dividing a String

貪欲とDPどちらを書こうか迷いましたが、貪欲解法のほうで書きたいと思います。

問題概要

文字列  S が与えられる。この  S をできるだけ多くの部分文字列に分割したい。ただし、隣り合う2つの部分文字列が一致してはならない。

最大でいくつの部分文字列に分割できるか答えよ。

※以降の解説では文字列  S の長さを  N と表記します。

解法

貪欲法、つまり前からできるだけ短い文字列で切っていくという手順で解く方法を試してみましょう。

  • ルール1:前から文字列を見て、なるべく1文字ずつ切っていく。ただし「直前に1文字で切っていて、かつ今から見る文字がその文字と同じ」という時だけ2文字で切る。

このルールで入力例2の aaaccacabaababc を切ると以下のようになります。数えると出力例と同じ12分割です。

f:id:betrue12:20200501194723p:plain

ただしこれだけのルールだと、入力例1の aabbaaaaaaa などのケースで困ります。

f:id:betrue12:20200501195034p:plain

このように最後に残った2文字が同じ場合、貪欲に1文字で切ると最後に残った1文字と等しくなってアウトです。このようなケースのために、末尾2文字を見る時だけ次のルールを課します。

  • ルール2:最後に2文字残り、それらが同じである場合、その2文字をそのまま採用する。もしその2文字も直前に切った2文字の文字列と一致してしまう場合、その4文字を3+1文字と割り振る。

3+1文字になるのは以下の図のような場合です。

f:id:betrue12:20200501195303p:plain

結論を言ってしまうとこれで最適な分割方法を実現できるので、前からシミュレーションすると正解を求めることができます。

ただ貪欲法にありがちなこととして、このような貪欲で解けると仮説を思いつくことよりも、その正しさを証明することのほうが難しいです。証明しましょう。

証明

先ほどの貪欲ルールで2文字または3文字になってしまったところには、それぞれ原因となった「同じ文字が隣接している箇所(以下、原因箇所)」が存在します。貪欲ルールで得られた分割数が  a である場合、全部1文字で切れた場合と比べて損をした  N-a と同じ数だけこの原因箇所が存在します。

f:id:betrue12:20200501195837p:plain

ルール2で3+1になっている場合は以下のように考えると原因箇所が2つあります。

f:id:betrue12:20200501200317p:plain

このように入力が aaaaa... と最も厳しい場合でも、貪欲ルールでは1+2+1+2+...のような切り方ができるので、この原因箇所は少なくとも1文字の間を空けて並んでいるはずです。

どのような切り方であっても、この原因箇所を挟んでいる2文字を両方とも1文字で切ることは条件違反なのでできません。また、2文字の文字列を1つ作ることで2箇所の原因箇所を潰すこともできません。つまり、この原因箇所1つにつき必ず1つは2文字以上の文字列を作り、少なくとも1文字ぶん損をする必要があります。

ここで貪欲ルールは「原因箇所1つにつきちょうど1文字ぶんだけ損をしている」切り方になっていました。これは実現できるギリギリの損の数です。よって、貪欲ルールによる分割数は最適であるということが示されました。

ACコード

Submission #12541470 - AtCoder Grand Contest 037

「直前が1文字であるかどうか」のフラグを持ってシミュレーションします。最後にルール2に引っかかる場合は、どちらのケースであっても「最後の2文字を使って分割個数が1増える」と見なすことができるので、実装上は区別する必要ないです。

おまけ:DPの場合

DPのほうが正当性を証明するのは楽なのですが、DPそのものへの慣れが必要なので今回の記事では見送りました。

DPの場合でも全くの無考察で解けるわけではなく、計算量を削減するためには「最適解に登場する文字列の長さは長くならない」という考察をする必要があります。またこれを文字数だけで容易に証明できるのは「最適解に登場する文字列は4文字以下である」というところまでで、公式解説や多くのDP解法記事で書かれている「2文字以下」というところまで示すには結局さっきの貪欲法と同じようなことを考える必要があります。

なので、証明の理解まで含んだ時に最も易しい解法は「4文字以下まで絞ってDP」だと思います。私が書こうと思っていたDP解法がほぼそのままこの記事で説明されているので、こちらを参考にしてください。

AtCoder Grand Contest 037 - Unhappy Go Lucky!