ARC081 D : Coloring Dominoes(400)
作成日：2017.08.24
最終更新日：2017.08.24
問題概要
$2 \times N$のマス目に$1 \times 2$(向きは任意)のドミノを$N$個重ならないように敷き詰めたものが与えられる。
辺で接しているものは異なる色となるようにドミノを3色で塗り分ける時の塗り方が何通りあるかを$mod \: 10^9 + 7$で求めよ。
制約
$1 \leq N \leq 52$
$|S_1| = |S_2| = N$
$S_1 , S_2$は英小文字または英大文字
$S_i$の$j$文字目は上から$i$番目、左から$j$番目のマスを表し、同じ文字のマスには同じドミノがある。
考え方
左の列から順に色を塗っていくことを考える。
マス目は2行しかないので、ある列においては1つのドミノが占める(壱)か2つのドミノが占める(弐)かのいずれかである。
また色の塗り方は直前の列にのみ依存するから、一番左の列を除くと$4$通りだけ考えれば良い。
すべての場合を列挙するなどすると以下のことが分かる。
一番左の列の塗り方は、壱の時は$3$通り、弐の時は$6$通りである。
直前の列が壱の時の塗り方は、壱の時も弐の時も$2$通りである。
直前の列が弐の時の塗り方は、壱の時は$1$通り、弐の時は直前の列と同じドミノなら$1$通りでそうでなければ$3$通りである。
以上を順に$mod \: 10^9 + 7$でかけ合わせていけば答えが求まる。
ソースコード
マクロ等はこちら
const LL mod = 1e9 + 7;
int N;
char S1[55],S2[55];
LL ans = 1;
int main(){
scanf("%d" , &N);
scanf(" %s" , S1);
scanf(" %s" , S2);
int pre = 0; //直前の列のドミノの状態を表す
repp(i,0,N){
if(S1[i] == S2[i]){
if(pre == 0){
(ans *= 3) %= mod;
} else if(pre == 1){
(ans *= 2) %= mod;
}
pre = 1;
} else {
if(pre == 0){
(ans *= 6) %= mod;
} else if(pre == 1){
(ans *= 2) %= mod;
} else {
(ans *= 3) %= mod;
}
pre = 2;
++i;
}
}
printf("%lld\n" , ans);
return 0;
}解法まとめ
左の列から色を塗っていくことを考え、考察で述べた各列の塗り方を$mod \: 10^9 + 7$でかけ合わせていく。(10-30行)