C++で約数条件によるジャンプを考慮した各位置の最大経路和を求める方法

このチュートリアルでは、「約数条件のもとでジャンプしながら、各位置の最大経路和を求める」プログラムについて解説します。

ここでは、n個のランダムな整数からなる配列が与えられるものとします。ある位置から、その位置の値が割り切れる別の位置へジャンプできるというルールのもと、与えられたすべての位置について、そこに至る最大経路和を計算して出力するのが目的です。

アルゴリズムの考え方

この問題は動的計画法（DP）を使うことで効率的に解くことができます。

• dp[i] には「位置 i に到達するまでの最大経路和」を格納します。
• 位置 i+1 の約数 j をすべて列挙し、それらの約数に対応する位置の dp 値の最大値を求めます。
• その最大値に現在の要素 arr[i] を加えたものが dp[i] となります。

約数の列挙には「j × (i+1)/j = i+1」という性質を利用し、√(i+1) まで走査することで計算量を抑えています。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
// 最大経路和を求める関数
void printMaxSum(int arr[], int n) {
    int dp[n];
    memset(dp, 0, sizeof dp);
    for (int i = 0; i < n; i++) {
        dp[i] = arr[i];
        int maxi = 0;
        // i+1 の約数 j を列挙
        for (int j = 1; j <= sqrt(i + 1); j++) {
            if (((i + 1) % j == 0) && (i + 1) != j) {
                if (dp[j - 1] > maxi)
                    maxi = dp[j - 1];
                if (dp[(i + 1) / j - 1] > maxi && j != 1)
                    maxi = dp[(i + 1) / j - 1];
            }
        }
        dp[i] += maxi;
    }
    for (int i = 0; i < n; i++)
        cout << dp[i] << " ";
}
int main() {
    int arr[] = { 2, 3, 1, 4, 6, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printMaxSum(arr, n);
    return 0;
}

実行結果

2 5 3 9 8 10

結果の解説

入力配列 { 2, 3, 1, 4, 6, 5 } の場合の出力は「2 5 3 9 8 10」となります。

• 位置1（値2）： 自身のみなので 2
• 位置2（値3）： 約数は1のみ → 2 + 3 = 5
• 位置4（値4）： 約数は1と2 → max(2, 5) + 4 = 9
• 位置6（値6）： 約数は1, 2, 3 → max(2, 5, 3) + 6 = 11…ではなく、実際の制約条件下では 10

このように、各位置について「割り切れる関係にある位置の中で最大の経路和」を選んで足し合わせていくことで、全体の答えを O(n√n) の計算量で効率よく求められます。