C++で隣接する要素がすべて異なる値となる配列の個数を求める方法

3つの変数 size(要素数)、max_val(最大値)、last_element(末尾の要素) が入力として与えられます。この記事の目的は、次の条件をすべて満たす配列が何通り作れるかを求めることです。

• 配列はちょうど size 個の要素を持つ
• 各要素の値は 1 以上 max_val 以下の整数である
• 先頭の要素は必ず 1、末尾の要素は必ず last_element である
• 隣り合う2つの要素は同じ値にならない

例で理解しよう

例1

入力: size = 5, max_val = 3, last_element = 3

出力: 隣接する要素が異なる値を持つ配列の数:5

説明: 条件を満たす配列は次の5通りです。

[1, 2, 3, 1, 3]、[1, 2, 3, 2, 3]、[1, 2, 1, 2, 3]、[1, 3, 1, 2, 3]、[1, 3, 2, 1, 3]

例2

入力: size = 3, max_val = 2, last_element = 2

出力: 隣接する要素が異なる値を持つ配列の数:0

説明: 3要素で [1, _, 2] という形の配列は作れません。真ん中の要素に入れられるのは 1 か 2 だけであり、どちらを選んでも隣接する要素が同じ値になってしまうためです。

解き方のアプローチ

この問題では動的計画法(DP)と組み合わせ論を組み合わせて、条件を満たす配列の個数を効率よく求めます。

• 先頭と末尾の要素はそれぞれ 1 と last_element に固定されるため、自由に埋められるのは残りの size-2 個の要素だけです。
• 1 から max_val までの値を size-2 か所に埋める方法の総数は、ways(max_val) = ways(size) / (max_val - 1) と表せます。
• 一般に、1 から i までの範囲については ways(i) = ways(size) / (max_val - 1) となります。ここで ways(size) は、末尾の要素を 2 から max_val までの数字で埋める方法の総数です。
• last_element が 1 の場合、末尾は 1 に固定されるため、方法の数は ways(size-1) になります。
• 後ろから2番目の要素は、常に 1 から max_val の間の任意の値を取ることができます。
• 後ろから2番目の要素が 1 でない場合、arr[i] は 1 にも直前の arr[i-1] にもできないため、方法の数は (max_val - 2) × ways(i-1) です。
• 後ろから2番目の要素が 1 の場合、arr[i-1] が 1 であり arr[i-2] は 1 ではないため、方法の数は (max_val - 1) × ways(i-2) です。
• 以上をまとめると、漸化式は次のようになります。
  ways(i) = (max_val - 2) × ways(i-1) + (max_val - 1) × ways(i-2)

アルゴリズム

1. 変数 size、max_val、last_element を入力として受け取ります。
2. 関数 diff_val(int size, int max_val, int last_element) がすべての入力を受け取り、隣接する要素が異なる値となる配列の個数を返します。
3. カウント用の変数 count を 0 で初期化します。
4. 配列の埋め方の数を格納する配列 arr[Max_N] = {0} を用意し、arr[0] を 0、arr[1] を 1 で初期化します。
5. i = 2 から i < size までループします。
6. temp_1 = (max_val - 2) × arr[i-1]、temp_2 = (max_val - 1) × arr[i-2] を計算します。
7. arr[i] = temp_1 + temp_2 とします。
8. last_element == 1 の場合は count = (max_val - 1) × arr[size-2] とします。
9. それ以外の場合は arr[size-1] を返します。
10. 最後に count を結果として返します。

C++での実装例

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

int diff_val(int size, int max_val, int last_element) {
    int count = 0;
    int arr[Max_N] = {
        0
    };
    arr[0] = 0;
    arr[1] = 1;
    for (int i = 2; i < size; i++) {
        int temp_1 = (max_val - 2) * arr[i - 1];
        int temp_2 = (max_val - 1) * arr[i - 2];
        arr[i] = temp_1 + temp_2;
    }
    if (last_element == 1) {
        count = (max_val - 1) * arr[size - 2];
    } else {
        return arr[size - 1];
    }
    return count;
}
int main() {
    int size = 5;
    int max_val = 3;
    int last_element = 3;
    cout << "Count of arrays having consecutive element with different values are: " << diff_val(size, max_val, last_element);
    return 0;
}

上記のコードを実行すると、次の出力が得られます。

出力

Count of arrays having consecutive element with different values are: 5

結果は「5」となり、手作業で列挙した5通りの配列と一致しています。このように漸化式を用いた動的計画法により、全列挙を行わずに効率的に配列の個数を求めることができます。