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行)

ARC081の他の問題 C E F

ARC081 D : Coloring Dominoes(400)

問題概要

考え方

ソースコード

解法まとめ

自己紹介

プライバシーポリシー

お問い合わせ

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

寄付モドキ