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; }