C++でkを超えずに実行できるコピー操作の最大回数を求める方法

問題概要

n個の要素を持つ配列Aと整数kが与えられます。n個のキャンディの山があり、i番目の山にはA[i]個のキャンディが入っています。ここで、2つの異なるインデックスiとj（i != j）を選んで操作を行うと、A[i]個のキャンディを別の山へ追加できます（コピー元の山は減りません）。この操作は何度でも繰り返せますが、どれか一つの山でもキャンディ数がkを厳密に超えると、それ以上操作は行えません。このとき、操作を実行できる最大回数を求めるのが目的です。

例えば、入力が A = [1, 2, 3]、k = 5 の場合、出力は 5 になります。最小の山（A[0] = 1）をコピー元として使い、j = 1 の山には3回、j = 2 の山には2回キャンディを追加できるため、合計5回となるからです。

解法のアプローチ

この問題は、次の手順で解くことができます。

ans := 0
n := 配列Aのサイズ
配列Aを昇順にソートする
i := 1 から i < n の間、i を 1 ずつ増やしながら繰り返す:
    ans := ans + (k - A[i]) / A[0]
ans を返す

なぜこのアルゴリズムが有効なのか

配列をソートすると、最小値が A[0] に配置されます。コピー元として最も小さい山を選ぶことで、1回の操作あたりに追加されるキャンディの数を最小限に抑えられ、その結果、各山に対して実行できる操作回数が最大化されます。各山 i については、残りの許容量（k − A[i]）を A[0] で割った商（切り捨て除算）の回数だけ、k を超えずに操作を繰り返せます。これをすべての山について合計したものが答えとなります。

実装例

理解を深めるために、以下のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int k){
    int ans = 0;
    int n = A.size();
    sort(A.begin(), A.end());
    for (int i = 1; i < n; i++){
        ans += (k - A[i]) / A[0];
    }
    return ans;
}
int main(){
    vector<int> A = { 1, 2, 3 };
    int k = 5;
    cout << solve(A, k) << endl;
}

入力

{ 1, 2, 3 }, 5

出力

5

計算量

ソートに O(n log n)、その後のループは O(n) であるため、全体の計算量は O(n log n) となり、非常に効率的な解法です。