久しぶりのカッコ列の整合判定問題！！！
カッコが binary になっただけ。ただし通常のカッコ列問題は
)(
みたいなやつはダメだけど、今回はこういうのも消せる (解法 1 へ)。
あるいは今回はカッコ列問題だと思わなくても、自然な考察で回答を導くこともできる (解法 2 へ)
問題概要
0 と 1 からなる文字列 が与えられる。以下の操作を好きな回数だけ行える。最大で何回行えるか？
- 連続している 2 文字が "01" または "10" だった場合、そこを消す
制約
解法 1
カッコ列の整合性判定問題の亜種と言える感じ。0 を '('、1 を ')' だと思えばよい。
)(())(()))()))
に対して、"()" なペアを見つけて消す操作が最大で何回行えるかは以下のようにして解くことができる (あるいは簡略化して「 '(' が来たら +1、')' が来たら 1 以上なら -1」でも OK)。
スタック st を用意する
文字を順番に見て
+ '(' ならば st に push する
+ ')' のとき
+ st が空、または st.top が ')' なら push する
+ st.top が ')' なら pop してペアにする
こうして作れるペアの個数が最大
今回の問題も同じようなスタックの使い方で解くことができて、")(" もペアとして認めてあげれば OK。
#include <iostream> #include <string> #include <stack> using namespace std; int main() { string s; cin >> s; int res = 0; stack<char> st; for (int i = 0; i < s.size(); ++i) { if (st.empty() || st.top() == s[i]) st.push(s[i]); else { res += 2; // ペアを足す st.pop(); } } cout << res << endl; }
解法 2
もっとシンプルに考えることができる。今回の問題では、まずはそもそも
- どんなに頑張っても min(0 の個数、1 の個数) 回より多く操作を行うことはできない
ということがすぐにわかる。なぜなら、1 回の操作で必ず 0 と 1 を 1 個ずつ消すからだ。そしてなんと、逆に必ず min(0 の個数、1 の個数) 回の操作を達成できることが示せてしまうのだ。こういう風に「自明な上界として考えた値が実は最適解」というのはよくある。
さて、このような操作を扱う問題では
「操作を行った結果出来上がるものがどんなものか、わかりやすく言い換える」
を考察するのが良さそう。それは 700 点問題とかになっても変わらない。今回はちょっと考えてみると、
限界まで操作を行ったならば、最終結果に 0 と 1 が両方登場することはない
ということが言える。何故なら 0 と 1 が混ざっていたら「0 と 1 との変わり目」が絶対に存在するので、そこを消すことができる。それを繰り返すと結局 min(0 の個数、1 の個数) 回の操作を実施することになる。
よって以上から、min(0 の個数、1 の個数) 回の操作を実際に行えることが示せた。
#include <iostream> #include <string> #include <stack> using namespace std; int main() { string s; cin >> s; int zero = 0, ichi = 0; for (auto c : s) { if (c == '0') ++zero; else ++ichi; } cout << min(zero, ichi) * 2 << endl; }
カッコ列問題の類題
古くからカッコ列問題は題材として使われて来た。以下のような問題がある。
解法 1 のようにカッコ列問題の亜種として解く場合、類題として以下がある。
- AGC 005 A - STring (300 点) (カッコが ST になっただけ)
- 2018 第4回ドワンゴからの挑戦状 予選 B - 2525文字列分解 (300 点)
- AOJ 1173 世界の天秤 (ICPC 2011 国内予選)
- AOJ 2490 (OUPC 2013)
- ABC 064 D - Insertion (400 点) (判定だけでなくいじる)
- 2018 codeFlyer 本選 C - 部分文字列と括弧 (500 点) (整合した部分の数え上げ)
