【C言語】k人の学生に均等に配布できるチョコレートの最大数を求めるアルゴリズム

本記事では、連続した箱に入ったチョコレートの数が配列として与えられ、それらを k 人の学生に均等に配布する問題を C 言語で解く方法を解説します。

問題の概要

配列の各要素は「連続した箱の中のチョコレートの数」を表し、整数 k はチョコレートを受け取る学生の人数です。求めるべきは、合計が k で割り切れるような連続した箱（部分配列）を選び、その中で合計が最大となるものです。

解き方の基本方針はシンプルです。配列を左から右へ走査しながらチョコレートの数を加算し、その合計を k で割ります。余りが 0（割り切れる）であれば、その合計を変数に保存します。走査を進めながらこの処理を繰り返すことで、条件を満たす最大の合計が得られます。

つまりこの問題は、「k で割り切れる最大部分配列和を求める」問題として定式化できます。

入出力例

例 1

Choco[] = { 1, 2, 4, 5, 2, 8, 3, 5 }  k = 3

出力： k 人の学生に均等に配布できるチョコレートの最大数 − 5

説明： 最大の部分配列は { 5, 2, 8 } で、合計は 15 になります。これを 3 人で均等に分けると、1 人あたり最大 5 個のチョコレートを受け取れます。
※箱は連続しており、インデックスは { 3, 4, 5 } です。

例 2

Choco[] = { 2, 3, 7, 5, 4, 8, 2, 6 }  k = 5

出力： k 人の学生に均等に配布できるチョコレートの最大数 − 7

説明： 最大の部分配列は { 3, 7, 5, 4, 8, 2, 6 } で、合計は 35 になります。これを 5 人で均等に分けると、1 人あたり最大 7 個のチョコレートを受け取れます。

アルゴリズムの手順

以下のプログラムで採用しているアプローチは次のとおりです。

• 連続した容器に入っているチョコレートの数を含む整数配列 arr[] を用意します。

• 要素数 n は箱の個数を表します。

• 学生の人数 k を入力として受け取ります。

• 関数 maxChocolate(int arr[], int n, int k) は、配列・そのサイズ・学生数 k の 3 つの引数を受け取ります。

• for ループを使い、arr[] の先頭から走査を開始します。

• 2 つの変数 sum と maxSum を用意します。sum は部分配列の連続する要素の合計を格納します。

• maxSum は、それまでに発見した最大の合計を保持するために使います。

• ネストされた for ループの中で要素を加算し続け、sum % k の余りが 0 かどうかを判定します。

  同時に、その合計が maxSum より大きければ maxSum を更新します。

• 最終的に maxSum には、k 人の学生に均等に分割できるチョコレートの総数の最大値が入ります。

• 結果として maxSum / k を返します。これが各学生が受け取るチョコレートの個数です。

C 言語による実装例

#include <stdio.h>
// k 人の学生に均等に配布できる
// チョコレートの最大数を求める関数
int maxChocolates(int arr[], int n, int k){
    int sum;
    int maxSum = 0;
    for(int i=0;i<n;i++){
        sum=0;
        for(int j=i;j<n;j++){
            sum+=arr[j];
            if(sum%k==0 && sum>maxSum)
                maxSum=sum;
        }
    }
    // 'k' 人の学生に均等に配布
    return (maxSum / k);
}
int main(){
    int arr[] = { 2, 7, 6, 1, 4, 5 ,5, 3 };
    int n =8;
    int k =3;
    printf("Maximum number of chocolates to be distributed equally among k students: %d   ",maxChocolates(arr, n, k));
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Maximum number of chocolates to be distributed equally among k students − 11

この例では、配列 { 2, 7, 6, 1, 4, 5, 5, 3 } から合計が 33（k = 3 で割り切れる最大値）となる部分配列が見つかり、1 人あたり 11 個のチョコレートが配布できることがわかります。