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]の合計はそれぞれ8、13、10なので、コストは13です。コストが12の分割はありません。各合計を12以下にして左から順に詰めると、[6, 2]、[9]、[4, 7]、[3]となり、許されているのは3つまでなのに、4つに分かれてしまいます。
- 入力
- nums = [8, 1, 1, 1, 5]k = 2
- 出力
- 8
- 説明
- 8はどこかの部分に含まれているため、どの分割もコストが8未満にはなりません。
[8]と[1, 1, 1, 5]はいずれも合計が8なので、8に到達します。
- 入力
- nums = [3, 0, 4]k = 3
- 出力
- 4
- 説明
- 3つの値と3つの部分なので、各部分に1つずつ値が入り、合計は3、0、4になります。中央の部分の合計は0ですが、問題ありません。部分には値が1つ入っていれば十分です。
提出時に隠しテスト+20件
発展問題
貪欲法の各判定では、すべてのn個の値を読み取ります。累積和を使えば、代わりに二分探索で各部分の終わりを見つけられます。kが小さく、numsが長い場合、手法全体はどれくらい速くなるでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
最大の部分の合計が最大でも
cになると誰かが約束したとします。k個の部分で十分かどうかをすばやく判断できますか？左から順に部分を埋め、次の値を加えると
cを超える場合にのみ、その部分を閉じます。これで部分の数を最小限にでき、cを大きくしても部分の数が増えることはありません。最大値と合計の間で
cを二分探索します。貪欲法で数えた個数がk以下なら、答えはc以下です。そうでなければ、答えはcより大きくなります。
解説
2つの要件は互いに相反します。ちょうどk個の区間を使い、最大の区間をできるだけ小さくしたいのです。k-1個の切れ目の場所をすべて試すと組み合わせが爆発し、先頭からの部分列に対する動的計画法を使えばO(k·n²)まで減らせますが、5000個の値に対してはまだ遅すぎます。高速な方法では、問題を逆から考えます。最適な分割を探す代わりに、上限を仮定し、k個の区間をその上限以下に抑えられるかどうかを調べます。貪欲法を1回適用すれば答えがわかり、上限を大きくしていくと答えは一度だけ切り替わるので、二分探索を使えば約29回の処理でその切り替わりを見つけられます。
接頭辞に対する動的計画法
正しいが、最大のテストでは終わらない
考え方
分割の最後の部分を考えます。最初の j 個の値を p 個の部分に分けるとき、最後の部分はある連続区間 nums[i..j-1] で、最初の i 個の値は残りの p-1 個の部分を構成します。コストは、次の2つの数値の大きい方です。すなわち、その p-1 個の部分のコストと、最後の区間の合計です。最後の区間がどのようなものであっても、最初の i 個の値は可能な限り小さいコストで分割したいはずです。その最適な分割は右側の部分には左右されません。そのため、一度計算して再利用できます。
best[p][j] を、最初の j 個の値を p 個の部分に分割するときの最小コストとします。1つの部分に分ける方法は1通りしかありません。つまり、best[1][j] は最初の j 個の値の合計です。部分が複数ある場合は、最後の部分の開始位置 i をすべて試します。best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]) となります。ここで prefix[j] は最初の j 個の値の合計です。最後の部分の開始位置 i は、空でない p-1 個の部分には少なくとも p-1 個の値が必要なので p-1 から始まり、最後の部分にも1つの値が必要なので j-1 までです。答えは best[k][n] です。行 p が参照するのは行 p-1 だけなので、長さ n+1 の行を2つ用意すれば十分です。
最初の例では、[6, 2, 9, 4] を2つの部分に分ける場合、最初の部分を6の後で終えると（コストは max(6, 15) = 15）、2の後で終えると（max(8, 13) = 13）、9の後で終えると（max(17, 4) = 17）なります。そのため、best[2][4] = 13 です。次に、best[3][6] では最後の部分 [7, 3] を試すと max(13, 10) = 13 となり、ほかのどの開始位置でもこれを下回ることはありません。
問題は計算量です。行は k 個あり、各行に n 個の終端位置があり、各終端位置について最大 n 個の開始位置を試すため、最大で k·n²/2 ステップになります。n = 5000、k = 2500 の場合、内側のループは約 1.8 × 10^10 回実行されます。毎秒 10^9 回の単純なステップを実行できたとしても、18秒かかります。このDPを知っておく価値はあります。値が非負であるとは仮定しないため、高速な方法が使えない場合でも機能します。
アルゴリズム
prefixを作成します。ここでprefix[j]は、最初のj個の値の合計です。- 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 を選び、nums を、各部分の合計が c 以下になるように k 個に分割できるかを考えます。問題の答えは、可能となる最小の上限です。この問いは、元の問題よりずっと簡単です。その理由は2つあります。
まず、貪欲法で1回走査すれば答えが出ます。左から右へ進み、現在の部分の合計が c 以下に収まる間は値を追加します。次の値を加えると c を超える場合は、その部分を確定し、その値から新しい部分を始めます。この方法で、上限内で分割する際に必要となる部分の数を最小にできます。他の有効な分割と、部分ごとに比べてみましょう。どちらの最初の部分も先頭の値から始まり、貪欲法は次の値が収まらないときにだけ止まるため、貪欲法の最初の部分は少なくとも同じ位置まで右に進みます。すると貪欲法の2番目の部分は、もう一方の2番目の部分と同じ位置か、それより後から始まります。その部分の終わりまでの値は、もう一方の部分の一部であり、負の値がなければ一部の合計が全体の合計を超えることはないので、それらは上限内に収まり、貪欲法は再び少なくとも同じ位置まで進みます。貪欲法が後れを取ることはないため、必要な部分の数が増えることもありません。
次に、部分の数が k より少なくても、ちょうど k 個の場合と同じように扱えます。貪欲法で必要な部分が m < k 個なら、2つ以上の値を含む部分を2つに分割します。負の値がないため、その分割後の部分の合計は元の部分の合計を超えません。また、n ≥ k なので、k 個になるまで、必ずそのように分割できる部分があります。したがって、判定条件は partsNeeded(c) ≤ k です。
ここで重要な性質があります。判定結果は単調です。上限 c で可能なら、同じ分割がより大きな上限にも収まるため、c+1 でも可能です。max(nums) から sum(nums) までの上限に対する答えは、いいえ、いいえ、……、いいえ、はい、はい、……、はいとなり、求めるのは最初の「はい」です。範囲の両端は安全です。max(nums) より小さい上限ではその値を収められず、合計全体は常に1つの部分に収まります。また、最初の「はい」は単なる上限ではなく、実際のコストでもあります。もしその分割のどの部分の合計も c と等しくなければ、上限 c-1 でも可能だからです。
最初の例 [6, 2, 9, 4, 7, 3]、k = 3 をたどってみましょう。上限は9から31までです。上限20では [6, 2, 9]、[4, 7, 3] に分かれます。部分は2つなので、可能です。範囲は9から20になります。上限14では [6, 2]、[9, 4]、[7, 3] に分かれます。部分は3つなので、可能です。範囲は9から14になります。上限11では [6, 2]、[9]、[4, 7]、[3] に分かれます。部分は4つなので、不可能です。範囲は12から14になります。上限13では部分が3つ必要で、可能です。範囲は12から13になります。上限12では4つ必要で不可能なので、答えは13です。
各走査では n 個の値を読み取り、範囲は毎回半分になります。合計 S が最大 5 × 10^8 の場合、5000個の値に対して約29回の走査、つまり約150000ステップです。
アルゴリズム
lo = max(nums)、hi = sum(nums)を設定します。lo < hiの間、mid = lo + (hi - lo) / 2を求めます。- 上限
midで貪欲法に必要な部分数を数えます。部分数を1、累積和を0で開始し、値を加えると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, 9]に対してk = 2のとき、上限5でも問題ないと判定してしまいます。最大値から開始するか、単一の値が上限を超えた場合に判定を失敗させてください。partsNeeded(c) == kを検査している。貪欲法で必要な区間数はkより少なくなることがよくあります。[3, 0, 4]でk = 3の場合、上限4では[3, 0]と[4]にまとめられます。==では、どの上限も条件を満たしません。区間数が少なければ、必ずさらに分割できるので、≤ kを検査してください。- 区間数を0から数えている。値が上限を超える前から最初の区間は存在するため、個数は1から始めます。
midが条件を満たすときにhi = mid - 1としている。これでは答えそのものを飛ばす可能性があります。hi = midを保ち、lo < hiの間ループしてください。- DPの
iを0から始めている。i < p-1のときのセルbest[i]は、区間数より値の数が少ない状態を表しますが、そのような分割はできず、0で埋めた行ではコスト0として扱われます。[100, 1, 1]でk = 3の場合、DPは100ではなく2を返します。iはp-1から始めてください。 - 上限が大きい場合にオーバーフローする。ここでは合計は最大でも
5 × 10^8なので、32ビット整数で格納できます。値が10^6に達する場合、2148個ですでに2^31-1を超えるため、合計には64ビット整数を使ってください。
よくある質問4
Split Array Largest Sum の時間計算量はどれくらいですか？
二分探索の計算時間は O(n log S) です。ここで、n は nums の長さ、S はその合計です。各貪欲法による判定では配列を1回走査し、上限の範囲は判定ごとに半分になります。S = 5 × 10^8 の場合、判定回数は約29回です。追加の領域は O(1) です。DPの計算時間は O(k·n²)、領域計算量は O(n) です。
実現可能性のチェックが単調なのはなぜですか？
ある分割のすべての部分の合計が最大でも c なら、同じ分割ではすべての部分が最大でも c+1 になります。したがって、ある上限で条件を満たせば、それより大きい上限でも条件を満たし、ある上限で条件を満たさなければ、それより小さい上限でも条件を満たしません。答えは「いいえ」が続いた後に「はい」が続く形になるため、境界を見つけるのに二分探索がちょうど使えます。
貪欲法によるチェックで、なぜ分割数が最小になるのでしょうか？
貪欲法では、次の値を加えると上限を超えるまで、値を部分に追加し続けます。これを有効な分割と部分ごとに比較します。貪欲法の各部分は、同じ番号のもう一方の分割の部分と同じ位置か、それより後から始まるため、その部分の終わりまでの値は、上限以下に収まる部分の一部です。値はどれも負ではないので、その一部も上限以下に収まり、貪欲法は少なくとも同じ位置まで伸ばせます。貪欲法が遅れを取ることはないため、どの分割よりも少ない部分数で配列全体を網羅できます。
二分探索は負の数でも機能しますか？
いいえ。負の値がある場合、値を足すことで合計が小さくなることがあるため、貪欲法では部分を早く閉じすぎて、うまくいく分割を見逃す可能性があります。また、部分を分割すると、片方の合計が元の全体の合計を上回ることもあるため、部分の数が k 未満であっても、k 個に分割すればうまくいくとは限りません。DPはどちらの仮定にも依存せず、O(k·n²) の時間計算量で正しく動作します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def splitArray(nums, k):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [6, 2, 9, 4, 7, 3] k = 3
期待値
13