C++でi×arr[i]の合計を最大化する配列の並べ替えアルゴリズム

この記事では、n個の数値からなる配列を並べ替える問題について解説します。配列から要素を選択していく際、各要素を選ぶたびに「現在の要素の値 × それまでに選択した要素の個数」で計算されるポイントを獲得できます。このとき、獲得できるポイントの合計が最大になるように要素を選択するのが目的です。

問題の例

入力 : arr[ ] = { 3, 1, 5, 6, 3 }

配列が与えられた順番のまま要素を選択した場合、ポイントは
　= 3 × 0 + 1 × 1 + 5 × 2 + 6 × 3 + 3 × 4
　= 41

ポイントを最大化するには、{ 1, 3, 3, 5, 6 } の順に要素を選択します
　= 1 × 0 + 3 × 1 + 3 × 2 + 5 × 3 + 6 × 4
　= 48(最大値)

出力 : 48

入力 : arr[ ] = { 2, 4, 7, 1, 8 }
出力 : 63

解決のためのアプローチ

上記の例から、ポイントを最大化するためには要素を小さい順から大きい順に選択すればよいことが分かります。これは貪欲法(グリーディ法)に基づく考え方で、値の大きい要素ほど後の選択(係数が大きい位置)に置いた方が合計が大きくなるためです。解決の手順は以下の通りです。

• 与えられた配列を昇順にソートします。
• インデックス0から順番に要素を選択していきます。
• 各要素を選択することで得られるポイントを計算し、合計を求めます。

C++での実装例

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

int main () {
    int arr[] = { 2, 4, 7, 1, 8 };
    int n = sizeof (arr) / sizeof (arr[0]);
    // 配列をソートする
    sort (arr, arr + n);

    int points = 0;
    // 配列を走査してポイントを計算する
    for (int i = 0; i < n; i++) {
        points += arr[i] * i;
    }
    cout << "Maximum points: " << points;
    return 0;
}

実行結果

Maximum points: 63

コードの解説

このC++コードは非常にシンプルで理解しやすい構成です。まずsort関数を使って配列を昇順にソートし、その後forループで配列を先頭から末尾まで走査しながら、各要素にそのインデックスを掛けた値を累積していきます。これにより、小さい要素には小さい係数、大きい要素には大きい係数が割り当てられ、合計ポイントが最大になります。

なお、このアルゴリズムの計算量はソート処理が支配的となるため、O(n log n)となります。要素数が多い配列でも効率的に処理できるのが特徴です。

まとめ

この記事では、i × arr[i]で計算されるポイントを最大化するように配列の要素を選択・並べ替える問題を取り上げました。貪欲法を用いることで、配列を昇順にソートして順に選択するだけで最大ポイントを求められることを確認しました。C++での実装例を紹介しましたが、同じロジックはC、Java、Pythonなど他の言語でも簡単に実装できます。皆さんの競技プログラミングやアルゴリズム学習の一助となれば幸いです。