TTPC2015 G titech分離

2015/09/28 (Mon) AtCoder TTPC 文字列 DP

問題

日本語

方針

下のようなオートマトンを $|S|/6$ 個考える．

“$dp[t_1][i][t_2][e][c][h][pos] = $ $S[pos]$ まで見たときにそれぞれの状態にあるオートマトンの数としてありえるか？” とおいてメモ化再帰で埋める． $pos = |S|$ のときに全て受理状態になっていれば OK．

図は http://madebyevan.com/fsm/ で描きました．

実装

int n;
string s;

char dp[18][18][18][18][18][18];

bool rec(int t1, int i, int t2, int e, int c, int h, int pos){
    char & res = dp[t1][i][t2][e][c][h];
    if(res != -1){
        return res;
    } else if(pos == n){
        return (res = t1 + i + t2 + e + c + h == 0);
    } else if(s[pos] == 't'){
        return (res = (t1 != 0 && rec(t1-1,i+1,t2,e,c,h,pos+1)) || (t2 != 0 && rec(t1,i,t2-1,e+1,c,h,pos+1)));
    } else if(s[pos] == 'i'){
        return (res = i != 0 && rec(t1, i-1, t2+1, e, c, h, pos+1));
    } else if(s[pos] == 'e'){
        return (res = e != 0 && rec(t1, i, t2, e-1, c+1, h, pos+1));
    } else if(s[pos] == 'c'){
        return (res = c != 0 && rec(t1, i, t2, e, c-1, h+1, pos+1));
    } else if(s[pos] == 'h'){
        return (res = h != 0 && rec(t1, i, t2, e, c, h-1, pos+1));
    }
    return -10;
}

bool solve(){
    n = s.size();
    if(n%6 != 0) return false;
    map<char,int> cnt;
    for(char c : s) cnt[c]++;
    if(cnt['t'] != n/6*2) return false;
    if(cnt['i'] != n/6) return false;
    if(cnt['e'] != n/6) return false;
    if(cnt['c'] != n/6) return false;
    if(cnt['h'] != n/6) return false;
    mems(dp,-1);
    return rec(n/6,0,0,0,0,0,0);
}

signed main(){
    while(cin >> s) puts(solve() ? "Yes" : "No");
}

こういう系の問題はコンテスト中に解けた試しがない．