C++でドミノとトロミノを使って2×nのボードを埋める配置の数を数えるプログラム

ここでは、ドミノ(2×1の長方形)とトロミノ(L字型)という2種類のピースを扱います。どちらのピースも、下図のように回転させて使用することができます。

整数 n が与えられたとき、これらのピースを組み合わせて 2×n のボードを余りなく完全に埋める配置が何通りあるかを求めます。タイル張りのルールでは、すべてのマスが必ずいずれかのピースで覆われている必要があります。

例えば入力が 3 の場合、出力は 5 になります。実際の配置例は以下の通りです(異なる文字は異なるピースを表しています)。

• [XYZ XXZ XYY XXY XYY]
• [XYZ YYZ XZZ XYY XXY]

解法のアプローチ:動的計画法

この問題は動的計画法(DP)を使うことで効率的に解けます。手順は以下の通りです。

• サイズ N+5 の配列 dp を用意し、初期値として dp[1] := 1、dp[2] := 2、dp[3] := 5 を設定する。
• i が 4 から N までの範囲で、次の漸化式を順に適用する。
  dp[i] := 2 × dp[i−1] + dp[i−3]
• 最後に dp[N] を答えとして返す。

この漸化式は、「完全に埋まった状態」と「角が1マスだけ欠けた状態」という2種類の局面を組み合わせることで導出できます。直前の状態にドミノを縦置き・横置きで追加するパターンと、3つ前の状態からトロミノ2枚で残りを埋めるパターンを数え上げると、上記の式が自然に得られます。計算量は時間・空間ともに O(N) であり、大きな n に対しても高速に動作します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int add(int a, int b){
   return ((a % MOD) + (b % MOD)) % MOD;
}
class Solution {
   public:
   int solve(int N) {
      vector <int> dp(N + 5);
      dp[1] = 1;
      dp[2] = 2;
      dp[3] = 5;
      for(int i = 4; i <= N; i++){
         dp[i] = add(2 * dp[i - 1], dp[i - 3]);
      }
      return dp[N];
   }
};
int main(){
   Solution ob;
   cout << (ob.solve(3));
}

入力

3

出力

5