n度あることはn+1度ある

書きたいことを書く 統一性はない

ABC071 D - Coloring Dominoes

リハビリがてら解いた一問
特別な知識が必要ない問題です。ドミノの置き方のパターンを考えればOKです。
結論を言いますと、一番左のドミノが上下に積まれていれば6倍、一本ならば3倍。
上下にドミノが積まれている場合、左も上下に積まれていれば場合の数は3倍、一本ならば2倍。
ドミノが一本の場合、左が上下に積まれていれば1倍、一本ならば2倍に場合の数が増えていきます。
f:id:benntann:20181113202622p:plain
セルに書かれた番号を乗算したものだけ場合の数が増えます。 上が一番左のドミノが2つのドミノで構成される場合で、下が一番左のドミノが1つのドミノで構成される場合です。
一番左以降のパターンはどちらの状況で始まっても同じだけ場合の数が増加します。
最初のドミノの積み方の場合の数を考えます。 一番左のドミノが別々の場合、上のドミノは一番最初のドミノなので何色を選んでも自由です。そのため3つの選択肢があります。下のドミノは、上のドミノが選んだ色以外の色を選択しなくてはなりません。そのため、場合の数は2倍されます。
一方、一番左のドミノが1つだけで始まる場合は、何の縛りがないため3つの選択肢があります。
次に最初のドミノ以外の場合の数を考えます。
上の図の場合、左から二番目のドミノは上下に積まれています。この場合、上のドミノは左のドミノの色のみに縛られますので、場合の数は二倍されます。次にその下のドミノは、上のドミノと左のドミノに色を縛られます。上と左のドミノの色が異なる場合は、選択肢が1つになりますが、同じ場合は選択肢が2つになります。この場合の場合の数は、一番左上の色が赤(R)だとすると、その右と下のドミノは(G,B)、(B,G)、(G,G)、(B,B)の4パターンで、このうち選択肢が二つになるものは(G,G)と(B,B)です。合計6パターンに増加しているため、6/4=3/2のため場合の数は3/2倍になります。
よって一番左のドミノ以外のドミノで、上下に積み重なっているドミノがあり、その左側も上下に積み重なっていれば、上のドミノで2倍、下のドミノで3/2倍になるため、場合の数は3倍になります。一方で下の図の左から二番目のように、左側が1つのドミノであれば、下のドミノが隣接するドミノが同じ色になることはないため、場合の数は、上のドミノで2倍、下のドミノで1倍となります。
上の図の左から三番目のようにドミノが1本の場合を考えます。上の図の左から三番目の場合は、左の2つのドミノに色が縛られます。そのため、場合の数は1倍になります。一方その隣のように、左のドミノも1本であれば、1つのドミノにのみ色が縛られるため、場合の数は2倍になります。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; cin>>n;
    string s1,s2; cin>>s1>>s2;
    int i=1;
    long sum=3;
    if(s1[0]!=s2[0]){
        i++;
        sum*=2;
    }
    while(i<n){
        bool jud=(s1[i-1]==s2[i-1]);
        if(s1[i]==s2[i]){
            if(jud)
                sum*=2;
            i++;
        }
        else{
            if(jud)
                sum*=2;
            else
                sum*=3;
            i+=2;
        }
        sum%=(int)(1e9+7);
    }
    cout<<sum;
}

このコードだと、sumintにした場合、途中でオーバーフローしました。このような問題はやはりlongを使うと安全だと思います。