ARC081-D "Coloring Dominoes"

提出コード

考察

以下， $2 \times 1$ のドミノを縦ドミノ， $1 \times 2$ のドミノを横ドミノと呼びます．

問題の性質より，ドミノの並べ方は，縦ドミノそのもの( 以下 $D_{ver}$ )，または横ドミノを縦に並べたもの( 以下 $D_{hor}$ )のいずれかを横に並べていくことになります．

(ちなみに，vertical：垂直，horizontal：水平から名前を付けました)

ドミノの色の塗り方は，基準となるドミノが $D_{ver}$ か $D_{hor}$ か，そしてその左隣が $D_{ver}$ か $D_{hor}$ か，で4通りあります．

以下の場合分けでは，例えばあるドミノが $D_{hor}$ で，左隣が $D_{ver}$ のとき， $D_{ver} \to D_{hor}$ のように書くとします．

(i) $D_{ver} \to D_{ver}$ のとき

$D_{ver}$ が連続しているので，色の塗り方は2通りです．

(左隣の $D_{ver}$ の色以外を選ぶ2通りになります．)

(ii) $D_{ver} \to D_{hor}$ のとき

$D_{ver}$ に対して， $D_{hor}$ の色の塗り方は2通りです．

(左隣の $D_{ver}$ の色以外の2色のうち，どちらを上に塗るかで2!=2通りになります．)

(iii) $D_{hor} \to D_{ver}$ のとき

$D_{hor}$ に対して， $D_{ver}$ の塗り方は1通りです．

(既に左隣で2色使ってしまっているためです．)

(iv) $D_{hor} \to D_{hor}$ のとき

$D_{hor}$ に対して， $D_{hor}$ の塗り方は3通りです．

(これは説明がめんどいので省略...)

また， $0 \leq i \lt N$ に対して $S[ i ] = T[ i ]$ であれば $i$ 番目は $D_{ver}$ で，そうでなければ $i$ 番目から $i+1$ 番目にかけてが $D_{hor}$ であることがわかります．

1つ前のドミノが $D_{ver}$ か $D_{hor}$ かどちらかを持っておき，上の場合分けの数字をかけ算しながらmod $10^{9}+7$ をとっていくことで $O(N)$ で解けます．

久しぶりにこれぐらいのdiff(これは1165)の問題をやりました．

記事の更新も久しぶり．

そこまで難しくないという気持ちがあって，最近のdiffに換算したら700ぐらいな気がします．

一発ACできてよかった．