C++でクッキーを子どもたちに割り当てる方法（貪欲法の解説）

いくつかのクッキーを子どもたちに配ることを考えてみましょう。ただし、各子どもに渡せるクッキーは最大1個までという制約があります。

ここで、各子ども i は「欲張り度（greed factor）」g[i] を持っています。これは、その子が満足するために必要なクッキーの最小サイズを表します。また、各クッキー j はサイズ s[j] を持ちます。s[j] >= g[i] が成り立つとき、クッキー j を子ども i に割り当てることができ、その子は満足します。

この問題のゴールは、満足した子どもの数を最大化し、その最大数を出力することです。

入力例と出力例

たとえば、入力が [1,2]（子どもの欲張り度）と [1,2,3]（クッキーのサイズ）だった場合、出力は 2 になります。子どもが2人いて、その欲張り度はそれぞれ 1 と 2 です。3つのクッキーはすべての子どもの欲張り度以上の大きさがあるため、全員を満足させることができ、答えは 2 となります。

解法のアプローチ

この問題は貪欲法（グリーディ法）を使うことで効率的に解けます。基本的な考え方は、「最も欲張り度の低い子から順に、対応できる最小のクッキーを割り当てていく」というものです。手順は以下の通りです。

• 配列 g（欲張り度）をソートする
• 配列 s（クッキーサイズ）をソートする
• ポインタ i := 0、j := 0 を初期化する
• i < g のサイズ かつ j < s のサイズ の間、以下を繰り返す
  • g[i] <= s[j] ならば、i を1増やす（子ども i が満足した）
• 毎回 j を1増やす（次のクッキーへ進む）
• 最後に i を返す（満足した子どもの数）

C++での実装例

それでは、実際のコードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int i = 0, j = 0;
        while (i < g.size() && j < s.size()) {
            if (g[i] <= s[j])
                i++;
            j++;
        }
        return i;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2}, v1 = {1,2,3};
    cout << (ob.findContentChildren(v, v1));
}

入力

{1,2}, {1,2,3}

出力

2

計算量について

このアルゴリズムの時間計算量は、両配列のソートが支配的となるため O(n log n + m log m) です（n は子どもの数、m はクッキーの数）。ソート後の処理は両配列を一度走査するだけなので O(n + m) となり、非常に効率的です。空間計算量も O(1)（入力配列をそのまま利用する場合）で済みます。

まとめ

この問題は、貪欲法の典型的な応用例の一つです。両方の配列を昇順にソートして小さい側から対応付けることで、無駄なくクッキーを配分でき、結果として満足できる子どもの数が最大化されます。「小さい要求から順に、ちょうど合う最小のリソースを割り当てる」という発想は、他のマッチング系の問題にも応用できるので、ぜひ覚えておきましょう。