道路の両側に建物を建設する方法の総数を求めるアルゴリズム

道路に沿って n 個の区画が与えられ、各区画では道路の両側に建物を建設できるものとします。ただし、隣り合う建物同士の間には最低でも1つの空きスペースが必要です。この条件を満たすとき、建物を建設する方法は全部で何通りあるかを求めるのが本記事のテーマです。

建物の建設パターン

各区画において、建物の建設には次の4つの選択肢があります。

• 道路の片側だけに建設する
• 道路の反対側だけに建設する
• 建物を一切建設しない
• 道路の両側に建設する

入力と出力

Input:
区画の数を入力します。ここでは 3 とします。
Output:
Enter Number of sections: 3
Buildings can be constructed in 25 different ways.

アルゴリズムの考え方

この問題は動的計画法(DP)を使うことで効率よく解けます。まず道路の片側について、次の2つのカウンタを管理します。

• countEnd:最後の区画に建物が建っている状態の組み合わせ数
• countEndSpace:最後の区画が空きスペースになっている状態の組み合わせ数

隣接する区画には建物を連続して建てられないため、次の漸化式が成り立ちます。

countEndSpace := countEnd + prevCountEndSpace
countEnd := prevCountEndSpace

この漸化式はフィボナッチ数列と同じ構造を持っており、片側あたりの組み合わせ数は区画数 n に対して Fib(n+2) 通りとなります。そして道路の両側は互いに独立しているため、最終的な答えは「片側の組み合わせ数の2乗」になります。

アルゴリズム

constructionWays(n)

入力: 区画の数 n
出力: 建設可能な方法の総数

Begin
    if n = 1, then
        return 4
    countEnd := 1
    countEndSpace := 1

    for i := 2 to n, do
        prevCountEnd := countEnd
        prevCountEndSpace := countEndSpace
        countEndSpace := countEnd + prevCountEndSpace
        countEnd := prevCountEndSpace
    done

    answer := countEndSpace + countEnd
    return answer^2
End

C++による実装例

#include<iostream>
using namespace std;

int constructionWays(int n) {
    if (n == 1)         // 区画が1つの場合
        return 4;       // その区画には4通りの建設方法がある

    // 端に建物がある場合と空きスペースで終わる場合のカウント値を初期化
    int countEnd=1, countEndSpace=1, prevCountEnd, prevCountEndSpace;

    for (int i=2; i<=n; i++) {   // 2番目の区画からn番目まで処理
        prevCountEnd = countEnd;
        prevCountEndSpace = countEndSpace;

        countEndSpace = countEnd + prevCountEndSpace;
        countEnd = prevCountEndSpace;
    }

    // 空きスペースで終わる場合と建物で終わる場合の合計
    int answer = countEndSpace + countEnd;

    return (answer*answer);      // 道路は両側あるので答えを2乗する
}

int main() {
    int n;
    cout << "Enter Number of sections: ";
    cin >> n;
    cout << "Buildings can be constructed in " << constructionWays(n) <<" different ways.";
}

実行結果

Enter Number of sections: 3
Buildings can be constructed in 25 different ways.

区画数が3の場合、片側あたりの組み合わせ数は5通りとなり、両側は独立しているため 5 × 5 = 25通り という結果が得られます。このように、フィボナッチ数列の性質を利用することで、区画数が増えても線形時間 O(n) で効率的に答えを計算できます。