Codeforces Round #472 div2-A Tritonic Iridescence

問題概要

長さnのsegmentがあり、C,Y,Mで彩色する。
既に色が決定しているsegmentはs[i]='C'などと入力され、未決定のsegmentはs[i]='?'となっている。
連続する2つのsegmentが同じ色にならないように彩色する方法が2通り以上あるかを調べよ。

解法

場合分けでも出来るが、DPで解いてみる。
a[i][0]:= s[i]='C'のときの0~iまでの彩色の仕方の場合の数とすると、a[i][0] = a[i - 1][1] + a[i - 1][2] であり、
同様にs[i][1]はs[i]='M'のとき,s[i][2]はs[i]='Y'のときの0~iまでの彩色の数とすれば
0~iまでの彩色の仕方はs[i][0]+s[i][1]+s[i][2]通りとなる。
場合の数は高々3^n通りあって簡単にオーバーフローしてしまうが、s[i][j]が2以上のときは2とすることで回避している。

ll ret;
ll a[110][3];
int n;
string s;
int main() {
    cin >> n >> s;
    if (s[0] == 'C')a[0][0] += 1;
    if (s[0] == 'M')a[0][1] += 1;
    if (s[0] == 'Y')a[0][2] += 1;
    if (s[0] == '?') {
        a[0][0] += 1;
        a[0][1] += 1;
        a[0][2] += 1;
    }
    FOR(i, 1, n) {
        if (s[i] == 'C')a[i][0] += a[i - 1][1] + a[i - 1][2];
        if (s[i] == 'M')a[i][1] += a[i - 1][2] + a[i - 1][0];
        if (s[i] == 'Y')a[i][2] += a[i - 1][0] + a[i - 1][1];
        if (s[i] == '?') {
            a[i][0] += a[i - 1][1] + a[i - 1][2];
            a[i][1] += a[i - 1][2] + a[i - 1][0];
            a[i][2] += a[i - 1][0] + a[i - 1][1];
        }
        rep(j, 3)chmin(a[i][j], 2);
    }
    rep(j, 3)ret += a[n - 1][j];
    cout << (ret >= 2 ? "yes" : "no") << endl;
}