配列を並べ替えて二重和の式がmと一致するか判定するC++プログラム

n 個の要素を持つ配列 A と、ある整数 m が与えられます。次の式が成立するような配列の並べ替えが存在するかどうかを判定してください。

$$\mathrm{\sum_{i=1}^{n} \sum_{j=1}^{n}\frac{A[j]}{j} = m}$$

なお、A[j]/j の計算では丸め処理（切り捨て）は行われません。

例として、入力が A = [2, 5, 1]、m = 8 の場合を考えてみましょう。このとき出力は True になります。配列を [1, 2, 5] と並べ替えると、(1/1 + 2/2 + 5/3) + (2/2 + 5/3) + (5/3) = 8 となるためです。

解法のポイント

一見すると複雑な二重和に見えますが、重要な性質があります。式を展開すると、各要素 A[j]/j は外側のループによってちょうど j 回加算されることになります。つまり、

j × (A[j]/j) = A[j]

となり、割り算と掛け算が相殺されます。その結果、二重和全体は「配列の全要素の単純な合計」と完全に一致します。この値は並べ替えの順序に依存しないため、実際に必要な処理は「配列の総和が m と等しいかどうかを確認する」だけです。

アルゴリズムの手順

以下の手順で問題を解くことができます。

sum := 0
n := A のサイズ
i := 0 で初期化し、i < n の間、i を 1 ずつ増やしながら繰り返す：
　　sum := sum + A[i]
sum が m と等しい場合：
　　true を返す
そうでない場合：
　　false を返す

C++による実装例

理解を深めるために、以下の実装を見てみましょう。総和を保持する変数には long 型を使用し、大きな値でもオーバーフローしないよう配慮しています。

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

bool solve(vector<int> A, int m) {
    long sum = 0;
    int n = A.size();
    for (int i = 0; i < n; ++i) {
        sum += A[i];
    }
    if (sum == m)
        return true;
    else
        return false;
}

int main() {
    vector<int> A = { 2, 5, 1 };
    int m = 8;
    cout << solve(A, m) << endl;
}

入力

{ 2, 5, 1 }, 8

出力

1

計算量

このアルゴリズムは配列を一度走査するだけなので、時間計算量は O(n)、追加の記憶領域も不要で空間計算量は O(1) となります。非常に効率的な解法と言えるでしょう。