問題へのリンク https://atcoder.jp/contests/abc307/tasks/abc307_d
問題概要
アルファベットと"("、")"から成るN文字の文字列Sが与えられる。 先頭が"("、最後が")"で囲まれ、中に"("、")"を含まない文字列を削除する動作を繰り返す。
例(入力例1)
N=8, S=a(b(d))c
a(b(d))c
→ a(b)c
→ ac
解き方
与えられた処理を愚直に実装していくと、最高2×105の長さのSを何回も先頭から順に見ていき、途中の文字列を削除する必要があるので、間に合う見込みがない。
手順1 ペアを探す
最初に、削除されるときのかっこのペアを考える。 例えば、入力例1 a(b(d))c では、先頭を0文字目とすると
a(b(d))c
1文字目の"("と6文字目の")"、3文字目の"("と5文字目の")"がそれぞれペアになっている。1文字目から6文字目を削除すれば3文字目から5文字目も削除されるから、削除する文字列は中にかっこのペアのみを含む文字列でもよいことがわかる。
しかし、文字列Sによっては必ずしもペアが存在するとは限らない。例えば、S=)(() のとき、0文字目の"("はペアを作らず、1文字目と2文字目の"("と")"がペアになる。
どのようにかっこのペアを見つければよいだろうか。"("の右側にあって、最も近い")"がペアとは限らない。これはその間にほかの"("が含まれている可能性があるからで、先ほどの例 S=(()では、0文字目と2文字目がかっこのペアであることになってしまう。では、")"に注目してみるとどうだろう。")"の左側にあって、最も近く、かつ未だペアになっていない"("とはペアになりそうだ。 例えば S = (a))では、2文字目の")"は、左側にあって最も近い0文字目の"("とペアになる。3文字目の")"は、左側に未だペアになっていない"("が1つも存在しないのでペアを作らない。
そのため、次のような手順でかっこのペアを求められる。
- 左のまだペアになっていない(を入れる配列[リスト]left, ペアを記録するpair_listを用意する
- [iを0~Nまで1ずつ増やしていく]
- もし、Sのi文字目が"("なら、leftにi["("のindex]を追加する。
- もし、Sのi文字目が")"で、leftが空でないならば、配列の一番後ろの値[すなわち、")"の左にあって一番近いもの]とiがペアになる。→leftの一番後ろの値を取り出してpとし、leftからは削除する。pair_listに[p,i]を入れる。
このようにして、すべてのかっこのペアを求められる。 例えば入力例1だとこのようになる。
S = a(b(d))c
最初.left = [], pair_list = []
i=0: S[i] == "a" (アルファベットの時は何も起こらない)
i=1: S[i] == "(" → leftに1(i)を追加 left = [1]
i=2: S[i] == "b"
i=3: S[i] == "(" → leftに3(i)を追加 left = [1,3]
i=4: S[i] == "d"
i=5: S[i] == ")" → leftの末尾3と5(i)がペア pair_list = [[3,5]] leftから3を消去 left = [1]
i=6: S[i] == ")" → leftの末尾1と6(i)がペア pair_list = [[3,5],[1,6]] leftから1を消去 left = []
i=7: S[i] == "c"
結果: pair_list = [[3,5],[1,6]]
手順2 削除される文字とされない文字を判断する
手順1で、全てのかっこのペアを求め、削除されるかっこのペアを求められた。あとはpair_listの要素[l,r]それぞれについて範囲を合わせればよい。ただ、ここが少し難しい。
まず、実際に削除するわけにはいかないので、Sのi文字目は削除されているかを示す長さNのリスト「isdeleted」(初期値は全てfalse)を作って、先ほどのかっこのペアのリストの各要素について、[3,5]で3～5をTrueに、[1,6]なら1~6をTrueに…としていくのだが、これだと"("が105個続き、")"が105個続くSでは[0,199999],[1,199998],[2,199997]…と続いてしまうので計算回数が200000+199998+199996…+2 ≒ 1010となり厳しそうだ。(基本間に合うラインは108くらい)
そこで、無駄なかっこのペアを見ないように工夫する。実は、かっこのペア同士は範囲が一部分だけ重なっているということはない。例えば、[0,2]、[1,3]となることはなく、これは0,2の間に"("のみ含まれていることになるが、かっこのペアの中に含められるかっこはペアのみであるから矛盾が生じる。
そのため、もし[1,3]をチェックしたときに既にisdeletedの1がTrueになっていたら、既に1~3全体はより広い範囲のかっこのペアによってチェックされているので確認の必要がないということだ。だから、pair_listを[")"のindex-(のindex]が広い順にソートして、もし(の位置が確認されていなければ全体をチェック、確認されていれば次のペア、という感じで、少ない計算回数で確認が可能になる。
ちなみに、ソートに関してはlambda式を用いている。関数を作るより短くかけて楽。 Python,C++ともにr-lの大きさで判断している。Pythonでは-をかけて昇順に、C++では不等号の向きで降順(大きい順)にソートしている。
コード(Python, C++)
Python
N = int(input()) S = list(input()) left = [] pair_list = [] for i in range(N): if S[i] == "(": left.append(i) # leftにiを追加 elif S[i]==")": if not left: continue # leftが空ならば何もしない pair_list.append((left.pop(), i)) #leftから末尾の要素をpopし、pair_listに追加 pair_list.sort(key=lambda x: -(x[1]-x[0])) #r-lの差が大きい順にソート is_deleted = [False] * N #is_deletedを用意 for l, r in pair_list: if is_deleted[l]:continue # 削除済みなら処理しない for i in range(l, r+1): is_deleted[i] = True # l以上r以下について、is_deleted[i]をTrueに更新 for i in range(N): if not is_deleted[i]: print(S[i], end = " ") # もしS[i]が削除されていなければ出力 print() # 改行
C++
#include <bits/stdc++.h> using namespace std; int main(){ int N; string S; cin >> N; cin >> S; vector<int> left; vector<pair<int, int>> pair_list; for (int i=0;i<N;i++){ if (S[i]=='(') left.push_back(i); // leftにiを追加 else if (S[i] == ')'){ if (left.empty()) continue; // 空なら何もしない else{ int p = left.back(); left.pop_back(); // leftの末尾を取得し削除 pair_list.push_back({p, i}); // {p,i}をpair_listに追加 } } } // lambda式を用いたソート sort(pair_list.begin(), pair_list.end(), [](pair<int,int> &a, pair<int,int> &b){ return (a.first-a.second) < (b.first-b.second); }); vector<bool> is_deleted(N, false); for (pair<int,int> &p: pair_list){ // 範囲for int l,r; tie(l, r) = p; if (is_deleted[l]) continue; // チェック済みなら何もしない for (int j=l; j<r+1; j++){ is_deleted[j] = true; // l以上r以下について、is_deleted[i]をtrueに } } for (int i=0; i<N; i++){ if (!is_deleted[i]){ cout << S[i]; // もし削除されていないのならS[i]を出力 } } cout << endl; // 改行 }
