AtCoder BC 071 D: Coloring Dominoes

問題

D - Coloring Dominoes
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

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

・縦に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;
}

コメント

タイトルとURLをコピーしました