kojingharangの日記

Codeforces Div2 C - Bracket Sequence

00:37 |

• [ ] ( ) からなる文字列 S が与えられる。
• カッコの対応がとれている部分文字列のうち [ の個数が最も多いものについてその数と部分文字列を出力する
• |S| ≦ 100000

• これはスタックでしょう
• できそうでできない
• ..........
• おわり

（あとで）

• 今回はロシアの grey_wind さんの解答を参考に。
• カッコの対応がとれている範囲 [NL, NR] をどうにかして探してその範囲内の [ の数を数えて最大のものを出力する。

• [NL, NR] の探し方は
• 文字列を先頭から見ていって、開きカッコなら文字とその出現位置を push
• 閉じカッコなら top が対応する開きカッコかどうか調べる
• 対応してない場合、現時点で開いているカッコはすべて対応しないことになるのでスタックをクリア
• 対応してる場合、開きカッコの出現位置から現在位置までがカッコに対応したことになる
• ところがこの問題の場合、「NL=今閉じたカッコに対応する開きカッコの位置」ではなく「NL=兄弟の先頭」にしないといけない（例: [ ] [ ] [ ] ）
• 兄弟の先頭は親の開きカッコの次の文字 or 親カッコがない場合は矛盾してない最初の文字 (start)

• 範囲内の [ は累積和を計算しておくと O(1) で求まる。

• うーむ賢い..

↓実装練習 (accepted in practice)

int cum[100010]; // i is # of '[' in S[k] for k in [0, i)

int count(int L, int R) {
	return cum[R+1]-cum[L];
}

int main() {
	//ios::sync_with_stdio(false);
	string S;
	while(cin>>S) {
		cum[0] = 0;
		REP(i, S.size()) {
			cum[i+1] = cum[i] + (S[i]=='[');
		}
		deque<pair<char, int> > mo;
		int N=S.size();
		int L=-1, R=-1;
		int co = 0;
		int start = 0;
		REP(i, N) {
			char op = S[i]==']' ? '[' : '(';
			if(S[i]=='[' || S[i]=='(') {
				mo.PB(MP(S[i], i));
			} else {
				if(mo.size() && mo.back().first==op) {
					mo.pop_back();
					int NL = start;
					if(mo.size()) NL = mo.back().second + 1;
					int NR = i;
					int nco = count(NL, NR);
					if( co < nco ) {
						co = nco;
						L=NL;
						R=NR;
					}
				} else {
					mo.clear();
					start = i+1;
				}
			}
		}
		cout<<co<<endl;
		if(co>0) cout<<S.substr(L, R-L+1)<<endl;
	}
	
	return 0;
}

ツイートする