第4回 ドワンゴからの挑戦状 予選: B - 2525文字列分解
問題
解説
validな部分列の分解を行うためには、少なくとも2と5との間で出現順序が保たれる必要がある。これはvalidな括弧列を作ることと同じである。 問題は「における相対的な出現順序が守られるように分解する」とあるが、各部分列は同じ括弧の深さであれば同じ部分列内に含めることができる。
具体的には、括弧の深度が上昇すると、それぞれの括弧のペアは別々の部分列に含める必要がある。 であれば、それぞれ同じ部分列に含められないため、 の3つの部分列は確定する。 しかし、深さが同じ者同士は同一の部分列に含めることができる。
であれば、深さ1が1つ、深さ2が3つであり、 と分解できる。 であれば、深さ1が3つ、深さ2が2つ、深さ3が1つであり と分解できる。
よって、括弧の深度の最大値が答えとなる。
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); } void ng() { cout << "-1\n"; exit(0); } int main() { string s; cin >> s; int par = 0, cnt = 0; rep(i, s.size()) { if (s[i] == '2') par++, maximize(cnt, par); if (s[i] == '5') par--; if (par < 0) ng(); } if (par != 0) ng(); else cout << cnt << "\n"; }