AtCoder BC 071 D: Coloring Dominoes

AtCoder

問題

https://beta.atcoder.jp/contests/abc071/tasks/arc081_b

解法

左から順にドミノの並びを見ていく場合、並び方は

・縦に1つ置く ・横に2つ重ねる

の2パターンです。

そこで、直前の並びに対する次の並びでの塗り方のパターンを考えます。

・「縦に1つ」→ 「縦に1つ」 　直前の色以外の2色が選べる ＝ 2通り

・「縦に1つ」→ 「横に2つ」 　直前の色以外の2色について、どちらかを上、どちらかを下にする　＝　2通り

・「横に2つ」→ 「縦に1つ」 　必ず直前の色以外の1色を選ぶことになる ＝ 1通り

・「横に2つ」→ 「横に2つ」 　上に直前の上下の2色以外を選ぶ場合、下は必ず直前の上の色になる ＝ 1通り 　上に直前の下の色を選ぶ場合、下は残りの2色を選べる ＝ 2通り 　合わせて3通りとなる

また、一番左側のドミノについては、

・「縦に1つ」＝ 3通り ・「横に2つ」＝ 3 x 2 = 6通り

となる。

よって、左側から順番にドミノの並びを検査していき、上記のパターンをかけていくと解ける。（毎回MODをとることを忘れない）

実装

#include<iostream>
#include<algorithm>
#include<string>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;
 
typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    int N;
    cin >> N;

    string s1, s2;

    cin >> s1 >> s2;

    int i = 0;

    ll ans = 0;
    int flag;
    if(s1[i] == s2[i]){
        ans = 3;
        i += 1;
        flag = 1;
    }else{
        ans = 6;
        i += 2;
        flag = 2;
    }

    while(i < N){
        if(s1[i] == s2[i]){
            if(flag == 1){
                ans *= 2;
                ans %= MOD;
            }
            i += 1;
            flag = 1;
        }else{
            if(flag == 1){
                ans *= 2;
                ans %= MOD;
            }else{
                ans *= 3;
                ans %= MOD;
            }
            i += 2;
            flag = 2;
        }
    }

    cout << ans << endl;
}