東京大学プログラミングコンテスト2011: C. [[iwi]]

,

solution

全ての部分列について試す。$O(N2^N)$。

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
using namespace std;
template <class T> inline void chmax(T & a, T const & b) { a = max(a, b); }

bool pred(string const & t) {
    int n = t.length();
    if (n % 2 == 0) return false;
    if (n < 3) return false;
    if (t[n / 2 - 1] != 'i') return false;
    if (t[n / 2    ] != 'w') return false;
    if (t[n / 2 + 1] != 'i') return false;
    REP (i, n / 2 - 1) {
        char c;
        switch (t[i]) {
            case '(': c = ')'; break;
            case ')': c = '('; break;
            case '[': c = ']'; break;
            case ']': c = '['; break;
            case '{': c = '}'; break;
            case '}': c = '{'; break;
            default: return false;
        }
        if (c != t[n - i - 1]) return false;
    }
    return true;
}

int main() {
    string s; cin >> s;
    int result = 0;
    REP (x, 1 << s.length()) {
        string t;
        REP (i, s.length()) if (x & (1 << i)) {
            t += s[i];
        }
        if (pred(t)) {
            chmax<int>(result, t.length());
        }
    }
    cout << result << endl;
    return 0;
}