C++で解く：N×3グリッドの塗り方の総数を求める動的計画法アルゴリズム

問題概要

サイズが n × 3 のグリッドがあり、すべてのマスを赤・黄・緑の3色のうちちょうど1色で塗ることを考えます。ここで重要な制約として、隣り合うマス（上下・左右）同士は同じ色にできないというルールがあります。行数 n が与えられたとき、この条件を満たしながらグリッド全体を塗る方法が何通りあるかを求めます。答えは非常に大きな値になる可能性があるため、10^9 + 7 で割った余りを返してください。

例えば、入力が 1 の場合、出力は 12 になります。

解法のアプローチ

この問題は、各行の塗り方を状態として管理する動的計画法（DP）で効率的に解けます。手順は以下のとおりです。

• 法 m を 10^9 + 7 と定義します。
• 関数 add() を用意します。引数 a, b を受け取り、「((a mod m) + (b mod m)) mod m」を返します。これによりオーバーフローを防ぎながら加算を行えます。
• メインの処理では、まず a123 := 6、a121 := 6 で初期化します。
• i を 2 から n まで増やしながら、以下の漸化式を繰り返し適用します。
  • b121 := add(3 * a121, 2 * a123)
  • b123 := add(2 * a121, 2 * a123)
  • a121 := b121、a123 := b123
• 最後に add(a123, a121) を返します。

なぜ初期値は6ずつなのか？

1行のみを考えたとき、塗り方は次の2種類に分類できます。

• ABA型：両端が同じ色で中央が異なるパターン（例：赤・黄・赤）。選び方は 3 × 2 = 6 通り。
• ABC型：3つのマスすべてが異なる色のパターン。並べ方は 3! = 6 通り。

そのため初期値はどちらも 6 になります。さらに遷移を丁寧に数え上げると、ABA型の行の次は ABA型が3通り・ABC型が2通り、ABC型の行の次は ABA型が2通り・ABC型が2通り存在することが分かります。これを漸化式として実装したのが上記のアルゴリズムであり、時間計算量 O(n)・空間計算量 O(1) で高速に答えを求められます。

C++による実装例

理解を深めるために、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli mod = 1e9 + 7;
class Solution {
public:
    lli add(lli a, lli b){
        return ((a % mod) + (b % mod)) % mod;
    }
    int numOfWays(int n){
        lli a123 = 6, a121 = 6;
        lli b123, b121;
        for (int i = 2; i <= n; i++) {
            b121 = add(3 * a121, 2 * a123);
            b123 = add(2 * a121, 2 * a123);
            a121 = b121;
            a123 = b123;
        }
        return add(a123, a121);
    }
};
main(){
    Solution ob;
    cout << (ob.numOfWays(3));
}

入力

3

出力

246

まとめ

n × 3 グリッドの塗り分け問題では、行のパターンを「ABA型」と「ABC型」の2種類に分類し、行間の遷移を漸化式で表現することで、全探索せずとも線形時間で解を求められます。剰余演算を毎回の加算・乗算に組み込むことで、大きな n に対してもオーバーフローなしに正確な答えを得られる点もポイントです。