C++で解くドミノとトロミノを使ったタイル敷き詰め問題（2×Nボード）

問題の概要

本記事では、「ドミノ」と「トロミノ」という2種類の形状を使ったタイル敷き詰め（タイリング）問題をC++で解く方法を解説します。これらのピースは、以下のように回転させて使用することができます。

タイリングでは、盤面上のすべてのマスを必ずタイルで覆わなければなりません。また、2つのタイリング方法は、盤上の4方向に隣接する2つのセルにおいて、片方のタイリングだけがその両方のマスを同じタイルで占有している場合に限り「異なる」とみなされます。

入力と出力の例

整数Nが与えられたとき、2×Nのボードを敷き詰める方法が何通りあるかを求めます。例えば、入力が3の場合、出力は5となります。敷き詰め方は以下の通りです（異なる文字は異なるタイルを表します）。

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

解法のアプローチ

この問題は動的計画法（DP）を用いることで効率的に解くことができます。手順は以下の通りです。

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

この漸化式の考え方は、新しい列を追加する際に「縦長ドミノ1枚」「横並びドミノ2枚」などのパターンと、突起を持つ不完全な状態からの遷移を組み合わせることで、全ての敷き詰め方を数え上げることができるというものです。

C++による実装例

それでは、実際のコードを見ていきましょう。答えが非常に大きくなる可能性があるため、10⁹+7で割った余りを計算しています。

#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 numTilings(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];
    }
};
main(){
    Solution ob;
    cout << (ob.numTilings(3));
}

実行結果

入力

3

出力

5

まとめ

このように、ドミノとトロミノによる2×Nボードの敷き詰め問題は、漸化式 dp[i] = 2×dp[i−1] + dp[i−3] を用いた動的計画法によってO(N)の計算量で解くことができます。初期条件 dp[1]=1、dp[2]=2、dp[3]=5 を正しく設定することが重要なポイントです。