C++で隣接する要素が互いに割り切れる配列の個数を求める方法

問題の概要

2つの整数 one(配列の長さ)と another(要素の最大値)が与えられます。求めたいのは、次の条件をすべて満たす配列の個数です。

• 配列の各要素は、1以上「another」以下の範囲に収まる。

• 隣接するどの2要素についても、一方が他方を割り切る(arr[i] が arr[i+1] を割り切る、またはその逆)。

• 配列の長さはちょうど「one」である。

入力例 1

one = 3, another = 2

出力例 1

Count of arrays in which all adjacent elements are such that one of them divide the another are: 8

説明

1と2は互いに割り切れる関係(1は2を割り切る)にあるため、長さ3のすべての組み合わせが条件を満たします。該当する配列は次の8通りです。

[1,1,1], [1,1,2], [1,2,1], [1,2,2], [2,1,1], [2,1,2], [2,2,1], [2,2,2]

入力例 2

one = 2, another = 3

出力例 2

Count of arrays in which all adjacent elements are such that one of them divide the another are: 7

説明

条件を満たす配列は次の7通りです。

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

アプローチ:動的計画法(DP)

各配列の先頭要素は [1, another] の範囲から自由に選べます。2つ目以降の要素は、「直前の要素の倍数」または「直前の要素の約数」であり、かつ another 以下である必要があります。同じ部分問題が何度も現れるため、動的計画法で計算結果を保存して効率化します。

2次元配列 arr[][] を使い、arr[1][j] = 1(長さ1の配列は各値につき1通り)から始めて、次の遷移式で更新していきます。

arr[i][j] = Σ arr[i-1][k](k は j 自身、j の約数、または j の倍数で another 以下のもの)

アルゴリズムの手順

1. 整数 one と another を入力として受け取る。

2. 関数 adjacent_elements(first, second) が、条件を満たす配列の個数を返す。

3. カウント変数を 0 で初期化し、2次元配列 arr[size][size] を宣言する。

4. memset を使って arr の全要素を 0 で初期化する。

5. 約数を格納するベクター vec と、倍数を格納するベクター vec_2 を用意する。

6. i を 1 から second まで、j を 2*i から second まで i ずつ増やしながら二重ループで走査する。

7. i を vec[j] に、j を vec_2[i] に追加する。内側のループ終了後、自分自身 i も vec[i] に追加する。

8. for ループで arr[1][i] を 1 に設定する。

9. 配列を再び走査し、vec と vec_2 の内容をもとに、約数・倍数に対応する値を arr[i][j] に加算する。

10. 最後にすべての arr[first][i] を count に加算し、vec[i] と vec_2[i] をクリアする。

11. count を結果として返す。

C++ 実装例

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

int adjacent_elements(int first, int second){
    int count = 0;
    int arr[size][size];
    memset(arr, 0, sizeof arr);
    vector<int> vec[size], vec_2[size];

    // 約数と倍数を事前に列挙
    for (int i = 1; i <= second; i++){
        for (int j = 2 * i; j <= second; j += i){
            vec[j].push_back(i);      // i は j の約数
            vec_2[i].push_back(j);    // j は i の倍数
        }
        vec[i].push_back(i);          // 自分自身も約数として扱う
    }

    // 長さ1の配列は各値につき1通り
    for (int i = 1; i <= second; i++){
        arr[1][i] = 1;
    }

    // DPによる遷移
    for (int i = 2; i <= first; i++){
        for (int j = 1; j <= second; j++){
            arr[i][j] = 0;
            for (auto it : vec[j]){       // 直前の要素が j の約数
                arr[i][j] += arr[i - 1][it];
            }
            for (auto it : vec_2[j]){     // 直前の要素が j の倍数
                arr[i][j] += arr[i - 1][it];
            }
        }
    }

    // 長さ first の配列の総数を集計
    for (int i = 1; i <= second; i++){
        count += arr[first][i];
        vec[i].clear();
        vec_2[i].clear();
    }
    return count;
}

int main(){
    int one = 2, another = 2;
    cout << "Count of arrays in which all adjacent elements are such that one of them divide the another are: " << adjacent_elements(one, another);
    return 0;
}

出力

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

Count of arrays in which all adjacent elements are such that one of them divide the another are: 4

計算量の目安

約数・倍数の事前計算には O(N log N)(N = another)、DP本体は配列の長さ L = one に対しておよそ O(L × N × d)(d は各値の約数・倍数の平均個数)となります。全ての配列を素朴に列挙する方法(最大 N^L 通り)と比べ、大幅に高速に答えを求められるのがこの手法の大きな利点です。