Chocolate Distribution Problem
チョコレートの小袋がいくつかあり、packets[i] は小袋 i に入っているチョコレートの数です。m 人の生徒はそれぞれ小袋をちょうど1つ受け取るため、異なる小袋が m 個配られます。配られる小袋のうち、最も多いものと最も少ないものの差ができるだけ小さくなるように選んでください。
可能な最小の差を返す、minDifference という名前の関数を書いてください。
関数
- packetsinteger-array
- 各パケットに入っているチョコレートの数
- minteger
- 生徒の人数。それぞれに1つずつパケットを配る
- 戻り値integer
- 配布されたパケット数の最大値と最小値の差として可能な最小値
制約
2 ≤ m ≤ packets.length ≤ 1041 ≤ packets[i] ≤ 105- 2つの袋には、同じ数のチョコレートを入れることができます。
例
- 入力
- packets = [9, 3, 15, 7, 11, 4]m = 3
- 出力
- 4
- 説明
- 並べ替えると、パケットは3、4、7、9、11、15です。3、4、7と7、9、11はどちらも差が
4で、これより近い3つのパケットはありません。
- 入力
- packets = [20, 5, 18, 6, 19]m = 2
- 出力
- 1
- 説明
- 5と6の差は1であり、18と19、19と20も同様です。等しいパケットは2つとないため、どのペアも差を1未満にすることはできません。
- 入力
- packets = [8, 1, 5]m = 3
- 出力
- 7
- 説明
- 生徒が3人いて、パケットが3つあるので、すべてのパケットが配られ、差は
8 - 1 = 7です。
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
配る予定の中で最も小さいパケットがすでにわかっているとします。それと一緒に、ほかにどのパケットを配ればよいでしょうか？
最小のパケットを固定したら、サイズ順でその直後に来る
m-1個のパケットを配ります。それより大きいパケットでは、差が広がるだけです。ソート順では、それらのパケットは隣り合っています。パケットを並べ替えます。隣り合う
m個のまとまりはそれぞれウィンドウで、その差は最後のパケットから最初のパケットを引いた値です。ウィンドウを左から右へスライドさせ、最小の差を保ちます。
解説
m 個のパケットからなるすべてのグループを試すのは、あまりにも時間がかかります。最適な選び方は、パケットを並べ替えたときに隣り合う m 個のパケットを選ぶことです。そこで一度並べ替え、隣り合う m 個からなるすべての区間の差の最小値を、1回の走査で求めます。
最小のパケットを修正する
正しいが、最大のテストでは終わらない
考え方
配る最小のパケットである low を固定します。最大のパケットを小さく保つには、low 以上のパケットのうち小さいものから m-1 個を選びます。このとき差は、low 以上のパケットのうち小さいものから m 番目のパケットから low を引いた値になります。すべてのパケットを low として試し、それ以上のパケットが m 個未満の場合は飛ばして、最小の差を記録します。
n 通りの選択それぞれで、最大 n 個のパケットを絞り込んでソートします。計算量は O(n² log n) です。サイズの異なるパケットが n = 10^4 個ある場合、ソートだけで約 6 × 10^8 回の比較が必要です。
アルゴリズム
bestを、どの答えも超えられない値に設定します。- 各パケット
lowについて、low個以上のチョコレートが入っているパケットをすべて集めて、並べ替えます。 - それらが少なくとも
m個ある場合、m番目に小さい値からlowを引いた値が候補になります。 - 最小の候補を
bestに保持し、それを返します。
def minDifference(packets, m):
best = max(packets) - min(packets) # no gap can be wider than this
for low in packets:
# The packets that could go out alongside low, smallest first (low is one of them).
bigger = sorted(x for x in packets if x >= low)
if len(bigger) >= m:
best = min(best, bigger[m - 1] - low)
return bestm 個のパケットを並べ替えてウィンドウをスライドする
考え方
昇順に並べると、ウィンドウ sizes[i..i+m-1] では最小のパケットが先頭、最大のパケットが末尾になるため、その差は sizes[i+m-1] - sizes[i] です。
最適な選び方は常にウィンドウとして表せます。最小のパケットと最大のパケットの間にあるパケットを選ばずにいる場合、そのパケットを最大のパケットと入れ替えます。最小のパケットはそのままで、最大のパケットは小さくなるだけなので、差が大きくなることはありません。間がなくなるまでこれを繰り返します。
最初の例では、3つずつのウィンドウの差は4、5、4、6となるので、答えは4です。ソートには O(n log n)、ウィンドウをスライドさせる処理には O(n) かかります。
アルゴリズム
- 荷物を昇順に並べて
sizesに入れます。 - 最初のウィンドウとして、
bestをsizes[m-1] - sizes[0]に設定します。 - 開始位置
iを1からn-mまで順に取り、sizes[i+m-1] - sizes[i]とbestを比較し、小さい方を保持します。 bestを返します。
def minDifference(packets, m):
sizes = sorted(packets)
best = sizes[m - 1] - sizes[0]
# The window sizes[i..i+m-1] holds m packets; its first is the smallest, its last the largest.
for i in range(1, len(sizes) - m + 1):
best = min(best, sizes[i + m - 1] - sizes[i])
return best
落とし穴と境界ケース
- ウィンドウの終端を
i+m-1ではなくi+mにすることで、m+1個のパケットを測定してしまう。 - ウィンドウを1つ早く終了してしまう。開始位置は0から
n-mまで（両端を含む）。m = 2の[1, 10, 20, 21]の場合、i < n-mのループでは、唯一の差である1を見逃す。 - ソートを省略してしまう。
[9, 3, 15, 7, 11, 4]では、最初の3つのパケットの差は12だが、答えは4。 - 最初のウィンドウだけを測定してしまう。
m個の最小のパケットを選ぶ方法もあるが、最適なグループはどこからでも始められる。 - 数値をテキストとしてソートしてしまう。JavaScriptでは、比較関数なしの
sort()は100000を9より前に並べる。
よくある質問3
チョコレート分配問題の時間計算量はどれくらいですか？
ソートには O(n log n) かかり、m 個のパケットのウィンドウをスライドさせるには O(n) かかるため、合計では O(n log n) となります。追加の領域は、ソート済みのコピーを作成する場合は O(n)、入力をその場でソートする場合はソート自体を除いて O(1) です。
チョコレートの配分問題はスライディングウィンドウ問題ですか？
はい、ソート済みのパケット上の固定サイズのウィンドウです。累積和を使うウィンドウとは異なり、移動しても更新するものはありません。各ウィンドウの差は、最後のパケットから最初のパケットを引くだけで求められます。
チョコレートの分配問題は、ソートせずに解けますか？
ここでサイズは最大でも 10^5 なので、計数ソートを使えば O(n + 10^5) 時間で並べられ、同じ議論が成り立ちます。サイズに上限がない場合、比較だけでは O(n log n) より速くできません。m = 2 のとき、答えが 0 になるのは2つのパケットが等しい場合に限られ、重複を検出するには最悪の場合、同じ回数の比較が必要です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def minDifference(packets, m):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
packets = [9, 3, 15, 7, 11, 4] m = 3
期待される出力
4