Assign Cookies
それぞれの子ども i には、貪欲度 g[i] があります。これは、その子どもを満足させる最小のクッキーのサイズです。それぞれのクッキー j にはサイズ s[j] があります。子どもは、自分の貪欲度以上のサイズのクッキーを1つもらうと満足します。各子どもがもらえるクッキーは最大1つで、各クッキーを渡せる子どもも最大1人です。満足させられる子どもの最大人数を返してください。
関数
- ginteger-array
- 各子どもの欲求度、その子が受け入れる最小のクッキーサイズ
- sinteger-array
- 各クッキーのサイズ
- 戻り値integer
- それぞれの貪欲度以上の大きさのクッキーを受け取れる子どもの最大数
制約
1 ≤ g.length, s.length ≤ 50001 ≤ g[i], s[j] ≤ 105- 2つの配列の長さは異なる場合があり、どちらもソートされていません。
例
- 入力
- g = [4, 2, 7]s = [3, 5, 1, 2]
- 出力
- 2
- 説明
- 並べ替えると、子どもたちが欲しがっているのは 2、4、7 で、クッキーは 1、2、3、5 です。クッキー 2 は 2 を欲しがっている子どもに、クッキー 5 は 4 を欲しがっている子どもに与えられます。7 に届くものは残っていないので、答えは 2 です。
- 入力
- g = [3, 3, 3]s = [2, 2, 2]
- 出力
- 0
- 説明
- すべての子どもはサイズ3以上のクッキーを欲しがっていますが、すべてのクッキーのサイズは2なので、満足できる子どもはいません。
提出時に隠しテスト+16件
発展問題
それぞれの子どもにも受け取れるクッキーの最大サイズがあるとしたら、クッキーが条件を満たすのは一定の範囲内だけです。その場合、それぞれのクッキーを待っているどの子どもに渡せばよいでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
最も満足させやすい子どもは誰で、その子どもを満足させられる中で最も安いクッキーはどれですか？
子どもに合う最小のクッキーを与えても損はありません。取っておけるもっと大きなクッキーなら、そのクッキーで満たせるのと同じ子どもたちを満たせるからです。ですから、クッキーは小さいものから大きいものへ順に配り、欲の少ない子どもから先に与えましょう。
両方の配列をソートします。クッキーを小さいものから大きいものへと見ていき、まだ待っている子どもの中で最も欲張りではない子どもを指すポインターを保持します。クッキーがその子どもに十分な大きさなら、その子どもにクッキーを与えてポインターを次に進めます。そうでなければ、そのクッキーは待っているどの子どもにとっても小さすぎるため、飛ばします。ポインターの最終位置が答えです。
解説
どの子どもにどのクッキーを渡すべきかが問題です。すべての組み合わせを試すと膨大になりますが、貪欲なルールを1つ使えば解決できます。欲求の少ない子どもから順に対応し、その子に合う最小のクッキーを渡します。両方の配列をソートすれば、このルールは2つのポインターを使った1回の走査になります。
各子どもに合う最小のクッキー
正しいが、最大のテストでは終わらない
考え方
子どもを、欲しがる量が少ない順から多い順に並べます。各子どもについて、まだ使われていないクッキーをすべて調べ、条件を満たす中で最小のものを選びます。合うクッキーがなければ、その子どもはおなかをすかせたままです。最初の例では、子どもたちが欲しがる量は2、4、7です。2を欲しがる子どもはクッキー2を、4を欲しがる子どもはクッキー5をもらい、7を欲しがる子どもには何も残りません。
なぜ条件を満たす中で最小のクッキーを選ぶのでしょうか？大きいクッキーなら、小さいクッキーで満たせる子ども全員を満たせるうえ、さらに多くの子どもにも対応できます。使える中で最小のクッキーを配れば、後から来る、より多くを欲しがる子どもたちのために大きいクッキーを残せるので、食べさせられたはずの子どもを取りこぼすことはありません。
課題となるのは探索です。n人の子どもそれぞれがm個すべてのクッキーを調べるため、n = m = 5000の場合、チェック回数は2500万回になり、最大規模のテストには遅すぎます。
アルゴリズム
- 欲求度を小さい順に並べます。
- 各クッキーについて、使用済みかどうかを示すフラグを保持します。
- 子どもごとにすべてのクッキーを調べ、その子どもの欲求度以上のサイズを持つ未使用のクッキーのうち、最も小さいものを記憶します。
- 見つかった場合は、それを使用済みにして、その子どもを満足したものとして数えます。
- その数を返します。
def findContentChildren(g, s):
used = [False] * len(s)
fed = 0
for need in sorted(g): # least greedy child first
best = -1
for j in range(len(s)):
if not used[j] and s[j] >= need and (best == -1 or s[j] < s[best]):
best = j
if best != -1:
used[best] = True
fed += 1
return fed両方をソートして、2つのポインターを使う
考え方
上の走査では、条件に合う最小のクッキーを何度も探しています。クッキーも並べ替えておけば、その探索は不要になります。クッキーはサイズの小さい順に並ぶので、条件に合う最小のクッキーに最初に出会えます。
クッキーを小さいものから大きいものへと見ていき、まだ待っている中で最も欲張りでない子どもを指すポインター child を1つ保持します。クッキーのサイズが g[child] 以上なら、その子どもにクッキーをあげて、ポインターを次の子どもへ進めます。それより小さい場合、まだ待っているすべての子どもよりも小さいことになります。子どもたちは並べ替えられているためです。そのクッキーは使えないので、次へ進みます。
最初の例では、並べ替えたクッキーは 1、2、3、5、欲しさの値は 2、4、7 です。クッキー 1 は 2 を求める子どもには小さすぎます。クッキー 2 は 2 を求める子どもにあげます。クッキー 3 は 4 を求める子どもには小さすぎます。クッキー 5 は 4 を求める子どもにあげます。ポインターは 2 で止まり、それが答えです。
各ポインターは前に進むだけなので、この走査の計算量は O(n + m) で、支配的なのは2つのソートです。インプレースで並べ替えれば、追加の配列は必要ありません。
アルゴリズム
gとsを昇順に並べ替えます。- まだ待っている、最も欲張りでない子どもを示す
child = 0を設定します。 - クッキーを小さいものから順に見ていきます。
childがまだgの範囲内で、クッキーがg[child]以上なら、childに 1 を加えます。 - 食べ物をもらった子どもの数である
childを返します。
def findContentChildren(g, s):
g.sort()
s.sort()
child = 0 # the least greedy child still waiting
for size in s: # smallest cookie first
if child < len(g) and size >= g[child]:
child += 1
return child
落とし穴と境界ケース
ほとんどの誤答は、順序を間違えて組み合わせるか、誤ったポインターを動かすことが原因です。
- 子どもに必要以上に大きなクッキーを渡すこと。
g = [1, 2]とs = [1, 3]の場合、1を欲しがっている子どもにクッキー3を渡すと、2を欲しがっている子どもがお腹をすかせたままになりますが、正しく組み合わせれば2人とも満足させられます。 - クッキーが小さすぎるときに、子ども側のポインターを進めること。子どもにはまだクッキーが必要です。役に立たないのはクッキーのほうです。
- 子ども側のポインターの範囲チェックを忘れること。すべての子どもにクッキーを配り終えたら、残りのクッキーを処理する際に
gの末尾を越えて読み取らないようにする必要があります。 ≥ではなく>で比較すること。欲求度とちょうど同じ大きさのクッキーで十分です。- 数値を文字列としてソートすること。JavaScriptでは、比較関数を指定せずに
sort()を使うと、10が9より前に並びます。
よくある質問4
「Assign Cookies」の時間計算量は何ですか？
2つの配列をソートするコストは O(n log n + m log m) で、その後の2ポインターによる走査は O(n + m) です。そのため、ソートが支配的です。インプレースでソートすれば、ソート自体が使用する領域を除き、追加の領域を O(1) に保てます。
Assign Cookies では、なぜ貪欲な選択がうまくいくのでしょうか？
貪欲さが最も少ない子どもに合う最小のクッキーをkとします。最善の割り当てで、その子どもに別のクッキーが与えられているとします。入れ替えます。その子どもはkを受け取り、kを持っていた子どもは、k以上の大きさの別のクッキーを受け取るので、引き続き満足できます。満足できる子どもの数は変わらないため、最善の割り当ては常に貪欲な選択から始められます。同じ議論を、残りの子どもとクッキーについて繰り返せます。
最も欲張りな子どもから始めてみませんか？
はい。両方の配列をソートしてから、いちばん大きいクッキーと最も欲張りな子どもから順に見ていきます。残っている最大のクッキーが、残っている最も欲張りな子どもに合えば、両方に与えてポインターを進めます。合わなければ、その子どもはどのクッキーでも満足させられないので、その子どもを飛ばします。同じ時間で同じ人数にクッキーを与えられます。
クッキーの割り当ては動的計画法の問題ですか？
いいえ。交換論法により、貪欲な選択が常に安全であることが示されるため、ソートして一度走査するだけで十分で、計算量は O(n log n + m log m) です。2つのソート済み配列を使った表を最長共通部分列の表と同じように埋めても答えを求められますが、同じ結果を得るのに O(n × m) の時間がかかります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def findContentChildren(g, s):
# ここにコードを書いてくださいケース1
ケース2
入力
g = [4, 2, 7] s = [3, 5, 1, 2]
期待値
2