C言語で購入できるキャンディーの最大数を求めるアルゴリズムを解説

問題の概要

長さ size の整数型配列 candies[] が与えられます。各要素 candies[i] は「タイプ i のキャンディーが何個あるか」を表します。目的は、予算の制限を設けず、与えられたルールを守りながら購入できるキャンディーの総数を最大化することです。

購入時のルールは次のとおりです。タイプ i のキャンディーを X[i] 個(0 ≤ X[i] ≤ candies[i])購入するとき、すべての j(1 ≤ j ≤ i)について、少なくとも次のどちらか一方の条件が成り立っている必要があります。

• X(j) < X(i) … タイプ j で購入した個数が、タイプ i よりも少ない
• X(j) = 0 … タイプ j のキャンディーは1つも購入していない

入出力例

入力: Arr[] = { 1, 3, 5, 2, 6, 7 }

出力: 購入できるキャンディーの最大数 = 16

説明: 各タイプの購入数は { 0, 3, 5, 2, 6, 0 } となります。

入力: Arr[] = { 5, 7, 7, 3, 4 }

出力: 購入できるキャンディーの最大数 = 10

説明: 各タイプの購入数は { 0, 0, 7, 3, 0 } となります。

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

この問題は、配列を後ろから前へ走査する貪欲法で効率的に解くことができます。ポイントは「直前に購入した個数より1個少ない数を上限として、できるだけ多く買う」という発想です。

• 整数型配列 candies[] に、タイプごとのキャンディーの在庫数を格納します。
• 変数 size には配列 candies[] の長さを保持します。
• 関数 maxCandies(int arr[], int n) は、購入可能なキャンディーの総数を返します。
• まず、最後のタイプのキャンディーをすべて買い切ると仮定します(bought = arr[n-1])。
• 後ろから2番目の要素から先頭に向かってループします(for (i = n-2; i >= 0; i--))。
• 変数 x には、現在のタイプで購入できる個数、すなわち arr[i] と bought - 1 のうち小さい方を代入します。
• x が 0 以上であれば、その値を合計 total に加算し、bought を x で更新します。
• ループ終了後、total を結果として返します。

C言語での実装例

#include <stdio.h>

int maxCandies(int arr[], int n){
    int bought = arr[n - 1];
    int total = bought;
    /* 後ろから2番目の要素から処理を開始 */
    for (int i = n - 2; i >= 0; i--) {
        /* 現在のタイプで購入できるキャンディーの数 */
        int x = arr[i] < bought - 1 ? arr[i] : bought - 1;
        if (x >= 0) {
            total += x;
            bought = x;
        }
    }
    return total;
}

int main(){
    int candies[] = { 1, 2, 4, 3, 7 };
    int size = 5;
    printf("Total Candies that can be bought: %d", maxCandies(candies, size));
    return 0;
}

実行結果

上記のコードをコンパイルして実行すると、次の出力が得られます。

Total Candies that can be bought: 13

動作の流れを追ってみる

入力 { 1, 2, 4, 3, 7 } の場合、処理は次のように進みます。

• 初期状態:bought = 7、total = 7(最後のタイプをすべて購入)
• i = 3:x = min(3, 6) = 3 → total = 10、bought = 3
• i = 2:x = min(4, 2) = 2 → total = 12、bought = 2
• i = 1:x = min(2, 1) = 1 → total = 13、bought = 1
• i = 0:x = min(1, 0) = 0 → total = 13、bought = 0

最終的な合計は 13 個となり、これがこの配列で購入できるキャンディーの最大数です。

計算量

このアルゴリズムは配列を1回だけ走査するため、時間計算量は O(n)、追加で必要なメモリは O(1) と非常に効率的です。要素数が大きくなっても高速に動作する点が魅力です。