C++でバッテリーの組み合わせ数を求めるアルゴリズム

最大5回まで使用できるバッテリーがn本あるとします。ここで、3本のバッテリーを必要とするデバイスがあり、デバイスを使用するたびにバッテリーの使用回数が1ずつ増加します。デバイスをk回使用したい場合、それらを動かすために何通りのバッテリーの組み合わせを作れるかを求める必要があります。ただし、1本のバッテリーを複数のデバイスで同時に使用することはできず、すでに5回使用されたバッテリーは組み合わせに含められません。各バッテリーの現在の使用回数は配列battとして与えられます。

例えば、入力が n = 6、k = 2、batt = {2, 4, 4, 2, 1, 3} の場合、出力は 1 になります。これは、k回分のデバイス稼働に対応できるバッテリーの組み合わせが1通りしか作れないことを意味します。

解法の考え方

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

• 答えを格納する変数 ans を0で初期化します。
• すべてのバッテリーについて、「現在の使用回数 + k」が5以下になるかどうか、つまりあとk回使用しても上限に達しないかを確認します。
• 条件を満たすバッテリーの本数をカウントします。
• 最後に、カウントした本数を3で割った値(整数除算)を返します。1台のデバイスに3本のバッテリーが必要だからです。

ans := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
    if batt[i] + k <= 5, then:
        (increase ans by 1)
return ans / 3

C++による実装例

理解を深めるために、実際のC++コードでの実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
#define N 100
int solve(int n, int k, int batt[]) {
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(batt[i] + k <= 5)
            ans++;
    }
    return ans / 3;
}
int main() {
    int n = 6, k = 2, batt[] = {2, 4, 4, 2, 1, 3};
    cout<< solve(n, k, batt);
    return 0;
}

入力

6, 2, {2, 4, 4, 2, 1, 3}

出力

1

動作の解説

この例では、各バッテリーの使用回数にk=2を加えると {4, 6, 6, 4, 3, 5} となります。このうち「5以下」という条件を満たすのは 4, 4, 3, 5 の4本です。4本を3で割ると1になるため、作成できる組み合わせは1通りという結果になります。