こういうのちゃんと解き切れるようになりたい...
なんだろ、「'a' と 'b' の個数が等しくなるような区間ごとに分割する」という発想がちゃんと出て来るようにするためには、どういう流れの考察をすればよいのだろう...
問題概要
N 個の 'a' と N 個の 'b' からなる長さ 2N の文字列 S が与えられる。 {0, 1, ..., N-1} の部分集合 V であって、
- V に含まれる各 i について、S の中で i 番目の a と i 番目の b を抜き取ってくる
- それらを S 中で登場する順に concat する
という操作で得られる文字列が辞書順最大となるものを求めよ。
制約
- 1 <= N <= 3000
考えたこと
i = 0, 1, 2, ..., N-1 に対して、i 番目の 'a', 'b' の index を p_i, q_i とすると
- p_i > q_i
- p_i < q_i
のどちらかになる。まずはこのどちらかしか登場しないパターンを解いてみる。
すべてが p_i > q_i ('a' が先んじる) のとき
最初の 1 文字目はどんなに頑張っても 'a' になる。その次に 'a' が来るのは損なので最初に選んだ 'a' のペア 'b' が登場するまで 'a' を全部飛ばして、'b' を回収する。
そして、その 'b' の後ろにある 'a' をまたどれか選んで、そのペア 'b' を回収して... を繰り返す感じになる。
最終結果は "abababababab" という感じになる。この長さが長ければ長いほどよい。よって、毎回の 'a' の選び方は Greedy に一番前からとっていけばよい。
すべてが p_i < q_i ('b' が先んじる) のとき
最初はとにかく 'b' をたくさん並べたい気持ちになる。だから、'b' から見て相方の 'a' がなるべく遠くにあるやつを選んで...でも tie があったら...とか考えて迷宮入りしてしまった。
まず、i 番目の 'b' () を選んだとして
の登場の仕方が 2 パターンあることに注目する:
<
のとき: 問答無用で i+1 番目の 'b' も回収するのがいい
この状況から以下のような発想ができるかどうか... (ここがまだ自分には厳しい)
>
になるときというのは、i 番目の 'a' の地点で一旦
- 'b' と 'a' の個数が一緒になる
という状況になる。そこで文字列全体を「'b' と 'a' の個数が等しい」ような区間ごとに分割して考える。
各区間については、
- ある地点での 'b' を回収したならば、そこから先の 'b' はすべて回収した方がよい (どの 'b' についてもそのペアとなる 'a' を回収する前にその先の 'b' を回収できるため)
ということが言える。このことを利用すれば、各区間についての辞書順最大の文字列は、'b' 回収の開始時点を全探索すれば求められる。これにはナイーブには でできる。Suffix Array を用いれば
でもできそう。
そうして各区間についての辞書順最大の文字列を求めておいて、区間全体の辞書順最大を求めるためには DP をすればよい。
DP
文字列を値にもつ辞書順最大 or 最小を求める DP では、後ろからやるのが定石ではある。なぜなら S, T, add を文字列として
- max(S + add, T + add) = max(S, T) + add
は文字列の concat については必ずしも成り立つとは限らないが、
- max(add + S, add + T) = add + max(S, T)
は成立する。各区間について辞書順最大の文字列が
S1, S2, ..., Sk
と求められているとき、各文字列を採用するかどうかを後ろから DP しながら求めていけばよい。なお、各区間からとってくる文字列として「その区間の辞書順最大」と「空文字列」のみを考えればよいことは、以下の性質を用いて示せる (beet さんの記事参照):
文字列 X と Y が互いに prefix の関係にないとする。このとき任意の文字列を T として
X < Y ならば X+T < Y+T
が成立する
なお、この DP は文字列比較を含むために であるが、以下のような Greedy でもよくて、Suffix Array を組み合わせれば
でもできる。
- pair(Si, -i) が最大のものをまず選ぶ
- i より大きい範囲の j について pair(Sj, -j) が最大のものを選ぶ。以後これを繰り返す
全体
ここまで来れば大体もう解けている。
index を後ろから見ていったときに、「p_i < q_i ('b' が先んじる)」型の i が一度でも登場したら、それより前の index の「p_i > q_i ('a' が先んじる)」型はすべて無視してよい (使うと辞書順が下がってしまうため)。
よって、無視作業を含めると
- 前半は「p_i < q_i」型のみ
- 後半は「p_i > q_i」型のみ
という風にになる。前半と後半それぞれ辞書順最大を持って来て concat すればよい (それでよいことは比較的容易に示せる)
#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; int N; string S; string subSolve(const string &s) { if (s[0] == 'a') { string res = ""; int prev_a = -1; int a_num = 0, b_num = 0; bool search_a = true; for (int i = 0; i < s.size(); ++i) { if (s[i] == 'a') { if (search_a) { res += "a"; prev_a = a_num; search_a = false; } ++a_num; } else { if (!search_a) { if (b_num == prev_a) { res += "b"; search_a = true; } } ++b_num; } } return res; } else { string res = ""; for (int i = 0; i*2 < s.size(); ++i) { string tmp = ""; int a_num = 0, b_num = 0; for (int j = 0; j < s.size(); ++j) { if (s[j] == 'a') { if (a_num >= i) tmp += s[j]; ++a_num; } else { if (b_num >= i) tmp += s[j]; ++b_num; } } res = max(res, tmp); } return res; } } int main() { cin >> N >> S; int iter = 0; vector<string> vec; string tmp = ""; bool exist = false; for (int i = (int)S.size()-1; i >= 0; --i) { tmp += S[i]; if (S[i] == 'a') ++iter; else --iter; if (iter == 0) { reverse(tmp.begin(), tmp.end()); if (tmp[0] == 'a' && exist) { tmp = ""; continue; } if (tmp[0] == 'b') exist = true; string ma = subSolve(tmp); vec.push_back(ma); tmp = ""; } } vector<string> dp; dp.assign(N+1, ""); for (int i = 0; i < vec.size(); ++i) { dp[i+1] = max(dp[i+1], dp[i]); dp[i+1] = max(dp[i+1], vec[i] +dp[i]); } cout << dp[vec.size()] << endl; }
