Ecasdqina's MEMO

Ecasdqina's MEMO.

メモ帳.

ABC071-D Coloring Dominoes 解説

問題

D - Coloring Dominoes

解説

問題をそのまま見るとナイーブな実装が思いつきますが, これはもちろんTLEします.
ここで, 動的計画法のこころを思い出しましょう, つまり左側が既に塗り分けられている状態で右に新しくドミノを置く場合の数です.
まず, 最左の色の組み合わせは次の2パターンが考えられます.
1. 縦のドミノの場合, 3種類の塗り方があります.
2. 横のドミノの場合, 6種類の塗り方があります.

では, 左側が既に塗り分けられているという条件のもとで1つ右の部分の塗り分け方を考えてみましょう.
これは次の4パターンに分けることができます.
縦のドミノを0, 横のドミノを1とします.
1. 00と並んでいる場合, 左のドミノの色を決めると右のドミノは2種類の塗り方があります.
2. 01と並んでいる場合, 左のドミノの色を決めると右のドミノは2種類の塗り方があります.
3. 10と並んでいる場合, 左のドミノの色を決めると右のドミノは1種類の塗り方があります.
4. 11と並んでいる場合, 左のドミノの色を決めると右のドミノは3種類の塗り方があります.

これで全ての状態を列挙することができました! あとはこれにしたがって実装をすれば終了です, MODを取ることに注意しましょう.

コード

Submission #1883157 - AtCoder Beginner Contest 071

感想

動的計画法のこころが分かる問題だと思いました.