Codeforces Round #590 (Div. 3) - F. Yet Another Substring Reverse - Senの競技プログラミング備忘録

概要

長さが100万以下の文字列Sが1つあたえられる。構成されてる文字は、アルファベットの最初の20文字、すなわち'a' ~ 't'である。これの連続部分文字列を1つ選んで、1回だけ反転してよい。(しなくてもよい)
操作を終えた時、文字列Sの連続部分文字列の中で、次の条件を満たすものの最長の長さを答えよ。

同じアルファベットが使われてるのがたかだか1回までである。

ACするまで

1. 1回まで部分文字列を反転できるということは、よく考えると「任意の2か所の連続部分文字列をつなげて考えられる」と同じ。
2. 20種類しか文字はないので、bitDPのようにやってみると考える。
3. dp[i][bit][state] := i文字目まで見て、1つ目or2つ目の文字列を選んでる状態で(state)、出てくる文字の状態がbitの時の最長の長さ
でやろうとするも、これは計算量では10^12オーダーになり、明らかにTLEしてしまう。
4. 本質的には、2つのお互い同じ文字を持たない連続部分文字列を選ぶこと。こればかりは総当たり的な方法(DPとか、全探索とか)でやるしかなさそう。
5. 片方を固定した時、相方候補を探すことを考える。これでは相方が非常に多い。
6. こういうシチュエーションに非常に有効な高速ゼータ変換という集合論の操作を使用しよう！->AC!

考察

1回までひっくり返すことができるので、2つの離れてる連続部分文字列は、
ひっくり返す部分を「1つ目の部分文字列の最後尾の1つ後ろ」から「2つ目の連続部分文字列の最後尾」
とすることで、2つの連続部分文字列をくっつけることができる。
というわけで、これはつぎのような問題に言い換えられる。

文字列Sの、
お互いに重ならず、片方の使われてる文字はもう片方には必ず含まれない
2つの連続部分文字列を選び、その長さの最大値を求める。

使われてる文字は、順番を問わないので、「長さ」と「使われてる種類」で部分文字列を分類できる。その分類は最大で何通り存在してるかというと、 $2^{20}-1$ 通り存在している。

もちろん、長さも最長は20までなので、
文字列のそれぞれの場所を始点として、どの文字も1回しか出現しないように連続部分文字列を作ってみる(原理的に最大でも20文字までしか伸びない)
ことで、全部洗い出すことができる。洗い出して、分類ごとに最長の長さを持ってく。
ちなみに、この操作にかかる計算量は、 $20 \times 2^{20}$ であり、これは2000万程度なので間に合う。

さて、これで分類ごとの最長がわかるのだが、どうやって最大の長さを持つ2つのをマッチングできるだろうか？

ひとまず、1つ固定してみる。
固定する部分文字列の使われてる文字の集合を $T$ とする。 $T$ に対して、相手になることできるのは、 $\overline{T}$ の部分集合である。このうちの最長の長さを持つものを知りたい。
ちなみに、固定した方と選ばれる方は被ってはいけない、というルールが存在するが、被る＝いくつかのアルファベットをどっちでも使用するなので、補集合ならば、必ず被ることはない。

さて、 $\overline{T}$ の部分集合を愚直に求めるともちろんTLEするわけで、これを効率よく求めなければ、この解法は成立しない。

これを効率的に求めるには、高速ゼータ変換というアルゴリズムを使用する。
以下の記事の高速ゼータ変換の2つ目に相当するものが、今回使用するものである。この記事は非常に詳しいので、おすすめである。
naoyat.hatenablog.jp

実装は上の記事ではもらうDP形式で書いてるが、僕のソースコードでは配るDP形式で書いてた。xorはここでは、集合の引き算に相当し、orは足し算に相当する。

for (int i = 0; i < (1 << N); i++) {
	for (int j = 0; j < N; j++) {
		if (!((i >> j) & 1))dp[i | (1 << j)] = max(dp[i | (1 << j)], dp[i]);
	}
}

高速ゼータ変換を使うと、 $\overline{T}$ の部分集合のうちの、長さの最大値を効率よく求めることができる。( $O(N2^{N})$ )
よって、高速ゼータ変換を施したのち、すべての集合に対する相方を見て、その中での最大値を答えればよい。

ACソースコード：
Submission #74426814 - Codeforces

一言

勉強になった。ちゃんとやらないといけない。

Special Thanks

公式解法(なぜかリンクがはられていない)
以下の方のブログは大変参考になった。非常感谢你的平易近人的讲解！
blog.csdn.net