C++で2行×n列のグリッド上のボードを3色で塗り分ける組み合わせ数を求める方法

ここでは、2行 × n列のグリッドが与えられているとします。このグリッドは、n枚のボードで互いに重ならないように完全に覆われている必要があります。

各ボードは赤・青・緑のいずれか1色で塗ります。ただし、隣接する2枚のボードに同じ色を使うことはできません。また、必要がなければ、3色すべてを使う必要もありません。

グリッドの構成は配列 grid として与えられ、同じボードは同じ英字で、異なるボードは異なる英字で表現されます。私たちの目的は、条件を満たすボードの塗り方の総数を求めることです。

例えば、入力が n = 4、grid = {"abbd", "accd"} の場合、出力は 6 になります。つまり、与えられた条件を満たす塗り方が6通り存在します。

考え方

グリッドの各列は、縦1マス分のボード(縦向き)か、横2マスにまたがるボード(横向きペア)のいずれかで構成されています。

• 縦向きのボード(幅1):1枚だけで塗り方は 3通り(赤・青・緑のどれか)
• 横向きのボードのペア(幅2):上下で色が異なる必要があるため、塗り方は 6通り(3 × 2)

隣接する領域との関係から、遷移時の掛け算の係数が決まります。

• 幅2 → 幅2:× 3
• 幅2 → 幅1:× 1
• 幅1 → 幅2:× 2
• 幅1 → 幅1:× 2

これらを掛け合わせていくことで、全体の塗り方の数を効率的に計算できます。答えが大きくなる可能性があるため、10⁹ + 7 で剰余を取ります。

解法の手順

この問題を解くために、以下の手順に従います。

MODVAL := 10^9 + 7
配列 s を定義
i := 0 から i < n の間、繰り返し:
   もし grid[0][i] == grid[1][i] ならば:
      s の末尾に 1 を挿入
      i を 1 増やす
   そうでなければ:
      s の末尾に 2 を挿入
      i := i + 2
配列 tvec を定義
もし s[0] == 1 ならば:
   tvec[0] := 3
そうでなければ:
   tvec[0] := 6
i := 1 から i < s のサイズ の間、繰り返し:
   もし s[i-1] == 2 かつ s[i] == 2 ならば:
      tvec[i] := tvec[i-1] * 3 mod MODVAL
   もし s[i-1] == 2 かつ s[i] == 1 ならば:
      tvec[i] := tvec[i-1]
   もし s[i-1] == 1 かつ s[i] == 2 ならば:
      tvec[i] := tvec[i-1] * 2 mod MODVAL
   もし s[i-1] == 1 かつ s[i] == 1 ならば:
      tvec[i] := tvec[i-1] * 2 mod MODVAL
tvec[s のサイズ - 1] を返す

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int solve(int n, vector<string> grid){
    int MODVAL = 1e9 + 7;
    vector<int> s;
    for (int i = 0; i < n;) {
        if (grid[0][i] == grid[1][i]) {
            s.push_back(1);
            i++;
        } else {
            s.push_back(2);
            i += 2;
        }
    }
    vector<int> tvec(s.size());
    if (s[0] == 1)
        tvec[0] = 3;
    else
        tvec[0] = 6;
    for (int i = 1; i < (int)s.size(); i++) {
        if (s[i - 1] == 2 && s[i] == 2)
            tvec[i] = tvec[i - 1] * 3 % MODVAL;
        if (s[i - 1] == 2 && s[i] == 1)
            tvec[i] = tvec[i - 1];
        if (s[i - 1] == 1 && s[i] == 2)
            tvec[i] = tvec[i - 1] * 2 % MODVAL;
        if (s[i - 1] == 1 && s[i] == 1)
            tvec[i] = tvec[i - 1] * 2 % MODVAL;
    }
    return tvec[s.size() - 1];
}
int main() {
    int n = 4;
    vector<string> grid = {"abbd", "accd"};
    cout<< solve(n, grid);
    return 0;
}

入力

4, {"abbd", "accd"}

出力

6

計算量

このアルゴリズムはグリッドを一度走査するだけなので、時間計算量は O(n)、追加で使用する記憶域も O(n) です。n が大きい場合でも高速に動作します。