Coloring Dominoes [AtCoder Regular Contest 081 D]

http://arc081.contest.atcoder.jp/tasks/arc081_b

解法

http://arc081.contest.atcoder.jp/submissions/1523704

左から順に塗っていくことを考える。
正しいドミノの敷き詰め方がされているので、左から見ると、

#
#
か
##
**

が連続して並んでいることが分かる。
上をパターン0, 下をパターン1とすると、塗り方は以下のようになる。
　
パターン0で…

• 最初なら3通り
• 左がパターン0なら2通り
• 左がパターン1なら1通り

の塗り方がある
　
パターン1で…

• 最初なら6通り
• 左がパターン0なら2通り
• 左がパターン1なら3通り

の塗り方がある
　
よって、これを順番に掛け合わせていけば答えが得られる。

int N; string S[2];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S[0] >> S[1];
 
    mint ans = 1;
    int x = 0;
    int pre = -1;
    while (x < N) {
        if (S[0][x] == S[1][x]) {
            if (pre < 0) ans = 3;
            else if (pre == 0) ans *= 2;
            else ans *= 1;
            x++; pre = 0;
        } else {
            if (pre < 0) ans = 6;
            else if (pre == 0) ans *= 2;
            else ans *= 3;
            x += 2; pre = 1;
        }
    }
 
    cout << ans << endl;
}