Split Array Largest Sum
非負整数の配列 nums と整数 k が与えられます。nums をちょうど k 個の部分に分割してください。各部分は隣り合う値が連続する空でない区間であり、部分の順序は維持します。それぞれの部分には合計値があり、分割のコストはそれらの合計値の最大値です。
k 個の部分への分割で達成できる最小コストを返してください。
関数
- numsinteger-array
- 順に並んだ、0以上の値
- kinteger
- それらを分割する連続した部分の数
- 戻り値integer
- 最大の部分和の可能な最小値
制約
1 ≤ nums.length ≤ 50000 ≤ nums[i] ≤ 1051 ≤ k ≤ nums.length- 各部分には少なくとも1つの値があります。値がすべて 0 の部分の合計は 0 となり、これは許容されます。
例
- 入力
- nums = [6, 2, 9, 4, 7, 3]k = 3
- 出力
- 13
- 説明
[6, 2]、[9, 4]、[7, 3]に分割すると、コストは13です。コスト12で済む分割はありません。12以下で左から順に部品をまとめると、[6, 2]、[9]、[4, 7]、[3]となり、4つの部品になります。
- 入力
- nums = [8, 1, 1, 1, 5]k = 2
- 出力
- 8
- 説明
- 8 はいずれかの部分に含まれているため、どの分割でもコストが 8 未満になることはありません。
[8]と[1, 1, 1, 5]はどちらも合計が 8 です。
- 入力
- nums = [3, 0, 4]k = 3
- 出力
- 4
- 説明
- 3つの値と3つの部分なので、各部分に1つずつ値があり、合計は3、0、4です。合計が0の部分も許可されます。
発展問題
累積和を使うと、貪欲な判定では二分探索によって各部分の終点を見つけられます。k が小さい場合、手法全体の実行速度はどのくらいになるでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
最大の部分の合計が最大でも
cになると誰かが約束したとします。k個の部分で十分かどうかをすばやく判断できますか？部分は左から右へ埋め、次の値を入れると
cを超える場合にのみ、その部分を閉じます。これにより部分の数を最小限にでき、cを大きくしても部分の数が増えることはありません。最大値と合計の間で
cを二分探索します。貪欲法による個数がk以下なら、答えはc以下です。そうでなければ、答えはそれより大きくなります。
解説
最適な分割を直接探すには、動的計画法を使っても O(k·n²) の計算コストがかかります。問いを逆にしてみましょう。k 個の部分に、与えられた上限以下で収まるでしょうか？ 貪欲法による1回の走査で答えがわかり、上限を大きくしていくと答えは一度だけ「いいえ」から「はい」に変わります。その変化点を二分探索で見つけます。
接頭辞に対する動的計画法
正しいが、最大のテストでは終わらない
考え方
best[p][j] を、最初の j 個の値を p 個の部分に分割する際の最小コストとします。最後の部分が nums[i..j-1] の場合、コストは best[p-1][i] とその部分の合計のうち大きい方です。また、最初の i 個の値の最適な分割は、その右側にあるものには依存しません。したがって、best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]) となります。すべての部分に少なくとも1つの値が含まれるよう、i の範囲は p-1 から j-1 です。行 p が参照するのは行 p-1 だけなので、2行あれば十分です。
最大で k·n²/2 ステップかかります。n = 5000、k = 2500 の場合、約 1.8 × 10^10 ステップです。
アルゴリズム
prefix[j]が最初のj個の値の合計となるようにprefixを作成し、1つの部分に対してbest[j] = prefix[j]を設定します。- 部分の数
pを2からkまで、各終端jをpからnまで動かし、iをp-1からj-1まで動かしたときのmax(best[i], prefix[j] - prefix[i])の最小値を求めます。 - それらの最小値を新しい行に格納し、それを
bestにします。 best[n]を返します。
def splitArray(nums, k):
n = len(nums)
# prefix[j] is the sum of the first j values
prefix = [0] * (n + 1)
for i, x in enumerate(nums):
prefix[i + 1] = prefix[i] + x
# best[j]: the smallest largest part when the first j values form one part
best = prefix[:]
for parts in range(2, k + 1):
nxt = [0] * (n + 1)
for j in range(parts, n + 1):
lowest = prefix[j] # never worse than one part holding everything
for i in range(parts - 1, j):
# the first i values form parts-1 parts, nums[i..j-1] is the last part
worst = max(best[i], prefix[j] - prefix[i])
if worst < lowest:
lowest = worst
nxt[j] = lowest
best = nxt
return best[n]最大の合計値に対する二分探索
考え方
上限 c を試すには、左から右へ進み、現在の部分の合計が c 以下である間、値を追加し、その後、新しい部分を開始します。これにより、可能な限り少ない部分数になります。有効な分割と比べると、貪欲法の最初の部分の終わりは少なくとも同じ位置まで右に進むため、次の部分はもう一方の分割と同じか、それより後から始まります。その部分の終わりまでの値は、条件を満たす部分の一部であり、負の値がなければ、その一部の合計が全体の合計を超えることはありません。したがって、貪欲法が遅れをとることはありません。
k 未満の部分数でも k 個の場合と同じように扱えます。2つ以上の値を含む部分を2つに分割しても、合計が増えることはないためです。したがって、判定条件は partsNeeded(c) ≤ k です。
一部には必ずその値が含まれるため max(nums) から、1つの部分に必ず収まる sum(nums) までの範囲で、条件を満たす最小の上限を二分探索します。
アルゴリズム
lo = max(nums)およびhi = sum(nums)を設定します。lo < hiの間、mid = lo + (hi - lo) / 2を求めます。midのもとで貪欲に分割した部分の数を数えます。合計を 0 として 1 つの部分から開始し、値を加えるとmidを超える場合は、部分を 1 つ追加し、その値を新しい合計として再開します。- 個数が
k以下なら、hi = midを設定します。そうでなければ、lo = mid + 1を設定します。 loを返します。
def splitArray(nums, k):
def parts_needed(cap):
# Fill each part left to right and start a new one only when the next value would pass cap.
parts, current = 1, 0
for x in nums:
if current + x > cap:
parts += 1
current = x
else:
current += x
return parts
lo, hi = max(nums), sum(nums) # one value per part at best, everything in one part at worst
while lo < hi:
mid = (lo + hi) // 2
if parts_needed(mid) <= k:
hi = mid # mid works, so the answer is mid or smaller
else:
lo = mid + 1 # mid needs more than k parts, so the answer is larger
return lo
落とし穴と境界ケース
loをmax(nums)より小さく設定する。貪欲法では、上限より大きい値はそれだけで1つの区間に入るため、k = 2の[1, 9]に対して、上限5でも問題ないと判定してしまう。partsNeeded(c) == kをテストする。[3, 0, 4]とk = 3の場合、上限4では[3, 0]と[4]に分割されるため、どの上限でも条件を満たさない。- 区間数を0から数えると、数が常に1つ少なくなる。
midが機能する場合にhi = mid - 1と設定すると、答えがmidのときにその答えを見失う。- DPの
iを0から始める。区間数より値の数が少ないセルのコストが0として扱われ、[100, 1, 1]とk = 3では、100ではなく2が返される。
よくある質問3
配列を分割して最大の合計を求める問題の時間計算量はどれくらいですか？
O(n log S)時間、追加領域はO(1)です。ここでSはnumsの合計です。各貪欲チェックは1回の走査で、チェックのたびに上限の範囲が半分になります。S = 5 × 10^8の場合、チェック回数は約29回です。DPはO(k·n²)時間かかります。
実現可能性のチェックが単調なのはなぜですか？
分割の各部分の合計がすべて最大でも c なら、同じ分割は c+1 以下にも収まります。つまり、ある上限で条件を満たせば、それより大きい上限でもすべて条件を満たすため、答えは「いいえ」が続いた後に「はい」が続く形になります。二分探索で最初の「はい」を見つけます。
二分探索は負の数でも機能しますか？
いいえ。負の値は合計を小さくすることがあるため、貪欲法では一部を早く閉じすぎる可能性があり、分割すると一方の部分が全体を上回ることもあります。DPはそのどちらの仮定も置かず、正しさを保ちます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def splitArray(nums, k):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [6, 2, 9, 4, 7, 3] k = 3
期待される出力
13