C++でN×3グリッドの塗り分け方法の数を求めるアルゴリズム

問題概要

n × 3 のサイズのグリッドを考えます。各セルは赤・黄・緑の3色のうち、ちょうど1色で塗る必要があります。ただし、「隣接するセル同士は同じ色にできない」という制約があります。ここで言う隣接とは、上下または左右で直接接触しているセルのことです。

グリッドの行数 n が与えられるので、このグリッドを条件を満たすように塗り分ける方法が全部で何通りあるかを求めます。答えは非常に大きな値になる可能性があるため、10⁹ + 7 で割った余りを返してください。

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

解法のポイント：行のパターンを2種類に分類する

この問題を効率的に解く鍵は、1行ごとの塗り方を次の2つのパターンに分類することです。

• ABC型（a123）：行内の3つのセルがすべて異なる色（例：赤・黄・緑）。1行あたり 3 × 2 × 1 = 6 通り。
• ABA型（a121）：1列目と3列目が同じ色で、2列目だけ異なる色（例：赤・黄・赤）。1行あたり 3 × 2 = 6 通り。

したがって、n = 1 のときは 6 + 6 = 12 通りとなります。n が増えるごとに、前の行のパターンから次の行のパターンへの遷移数は次のようになります。

• 前の行がABA型 → 次の行がABA型になる組み合わせは 3 通り
• 前の行がABC型 → 次の行がABA型になる組み合わせは 2 通り
• 前の行がABA型 → 次の行がABC型になる組み合わせは 2 通り
• 前の行がABC型 → 次の行がABC型になる組み合わせは 2 通り

この遷移規則を使えば、各行の状態を2変数だけで管理できる動的計画法（DP）が成立し、全体の計算量は O(n) に抑えられます。

アルゴリズムの手順

• 法として m = 10⁹ + 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) を返します。

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 の場合、計算の流れは以下のようになります。

• 初期状態：a121 = 6、a123 = 6
• 2行目：b121 = 3×6 + 2×6 = 30、b123 = 2×6 + 2×6 = 24
• 3行目：b121 = 3×30 + 2×24 = 138、b123 = 2×30 + 2×24 = 108

最終的な答えは 138 + 108 = 246 となり、プログラムの出力と一致します。このように、状態を2つに絞った動的計画法により、大きな n に対しても高速に答えを求められます。