UTPC2011 C: iwi

解法

全探索すればよい。計算量O(n*2^n)。括弧の対応と出力の条件(iwiを含む)をチェックし忘れてWA連発。

#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool check(string str){
	vector<int> is, ws;
	int n = str.length();
	for(int i=0; i<n; i++){
		if(str[i]=='i') is.push_back(i);
		if(str[i]=='w') ws.push_back(i);
	}
	if((int)is.size()!=2 || (int)ws.size()!=1) return false;
	return (is[0]==ws[0]-1 && is[0]==is[1]-2);
}

bool isPalin(string str){
	int n = str.length();
	for(int i=0; i<n; i++){
		if(str[i]=='(' && str[n-1-i]!=')') return false;
		if(str[i]=='{' && str[n-1-i]!='}') return false;
		if(str[i]=='[' && str[n-1-i]!=']') return false;
		if(str[i]=='i' && str[n-1-i]!='i') return false;
		if(str[i]=='w' && str[n-1-i]!='w') return false;
		if(str[i]==')' && str[n-1-i]!='(') return false;
		if(str[i]=='}' && str[n-1-i]!='{') return false;
		if(str[i]==']' && str[n-1-i]!='[') return false;
	}
	return true;
}

int main(){
	char buf[20];
	int ret = 0;
	scanf("%s", buf);
	int n = strlen(buf);
	for(int m=0; m<(1<<n); m++){
		string s = "";
		for(int i=0; i<n; i++)if((m>>i)&1){
			s += buf[i];
		}
		if(check(s) && isPalin(s)){
			ret = max(ret, (int)s.length());
		}
	}

	printf("%d\n",ret);
	return 0;
}