【C++】強度Pで倒せる最大人数を求めるアルゴリズム

この記事では、与えられた強度Pで倒すことのできる最大人数を求めるアルゴリズムを解説します。

一列に無限の人数が並んでおり、先頭から順に1から始まる番号が割り当てられています。s番目の人の強度は s² で表され、ある人を倒すと、その人の強度sだけ自分の持つ強度も減少します。つまり、消費した強度の累積合計がP以下である限り、順番に人を倒し続けることができます。

それでは、具体例を使って問題の内容を確認していきましょう。

入力

P = 20

出力

3

説明

1番目の人の強度 = 1 * 1 = 1 < 20、よって1番目の人を倒せる
残りの強度 = P - 1 = 20 - 1 = 19
2番目の人の強度 = 2 * 2 = 4 < 19、よって2番目の人を倒せる
残りの強度 = P - 4 = 19 - 4 = 15
3番目の人の強度 = 3 * 3 = 9 < 15、よって3番目の人を倒せる
残りの強度 = P - 9 = 15 - 9 = 6
4番目の人の強度 = 4 * 4 = 16 > 6、よって4番目の人は倒せない
出力 = 3

別の例も見てみましょう。

入力

P = 30

出力

4

アルゴリズムのアプローチ

• main()関数内で、強度を格納するint型変数Pを30として初期化し、Max()関数に渡します。

• Max()関数内では、int型の累積強度を表すsと、答えを格納するansをそれぞれ0で初期化します。

• j = 1 から開始し、「j * j ≤ P」を満たす間ループを繰り返します。

• s に j * j を加算し、s ≤ P であれば ans に1を加算します。条件を満たさなくなった場合は break でループを抜けます。

• 最後に ans を返します。

平方数の累積和は急速に増加するため、この貪欲なアプローチでも十分に効率的です。

コード例

#include <bits/stdc++.h>
using namespace std;
int Max(int P){
    int s = 0, ans = 0;
    for (int j = 1; j * j <= P; j++){
        s = s + (j * j);
        if (s <= P)
            ans++;
        else
            break;
    }
    return ans;
}
//main関数
int main(){
    //強度
    int P = 30;
    cout << "強度Pで倒せる最大人数: " << Max(P);
    return 0;
}

出力

強度Pで倒せる最大人数: 4

計算量

最初のk人の強度の総和は k(k+1)(2k+1)/6 でおよそ k³/3 に相当するため、ループの反復回数はおよそ ∛(3P) 回となります。したがって、時間計算量は O(∛P)、空間計算量は O(1) であり、非常に効率的な解法と言えます。