ABC 307 G — Approximate Equalization

考察

隣接transferはprefix sum S_i (1≤i<N)を±1する操作に一致するため、固定target Bへのminimum operationsはΣ_{i<N}|S_i−T_i|である。total sumをNq+r (0≤r<N)とfloor divisionすると、valid Bはq+1をちょうどr positions、qを残りに置く列に限られる。boundary iを跨ぐnet transport量はS_i−T_iで、そのabsolute value以上の操作が必要かつ実際にその量をedge iで移せるためcost式がtightである。dp[i][j]=min(dp[i−1][j],dp[i−1][j−1])+|iq+j−S_i|で、jの範囲だけがtarget arrangement historyを要約する。

棄却する候補: C(N,r)通りのtarget arrangementsを列挙してprefix-distance costを比較する。

target候補数が指数的である。

採用する候補: dp[i][j]を先頭i positionsにq+1をj個置いたminimum prefix costとして、次をq/q+1の二択で遷移する。

target prefix T_i=iq+jだけでcostが決まり、O(Nr)≤O(N^2)で全配置を圧縮できる。

adjacent mass transfersをprefix imbalanceのL1 costへ変換し、balanced targetのhigh-value positionsをcount DPで最適配置する。

典型の発動条件

隣接移動とprefix imbalance

発動条件: 隣接要素間で単位量を移し、初期列から固定target列へのminimum movesを求めるとき。

各boundaryを通る必要net flowをprefix sums差として絶対値合計する。

個数制約付き二値列DP

発動条件: target entriesが二値で、一方を置く総個数だけが固定されているとき。

processed positionsとhigh-value countをstateにしてprefix-dependent costを加える。

問題固有の要素

A_iが負でもq=floor(sum/N)、r=sum−Nqを0≤r<Nと定義すればq/q+1構造が崩れない。

別の問題へ持ち帰る視点: negative totalのquotient/remainderはlanguage truncationではなくmathematical floor divisionへ正規化する。

正当性

均等化後の各値はqまたはq+1で高値がr個。辺iを跨ぐ移送量は元prefixと目標prefixの差で費用は絶対値。iまでの高値個数jだけで目標prefix iq+jが定まり、低/高の二遷移で全配置のL1費用を最小化する。

実装上の注意

  • DP infinityとprefix sums/costには64 bitを使い、j≤min(i,r)かつr−j≤N−iとなるreachable statesだけ処理する。
  • i=Nのcost termはtotal sumsが等しく0だが、含めても同じ答えになるようindex規約を統一する。

復習の核

  • 隣接transfer問題は各boundaryを横切るnet amountをprefix sums差で表す。
  • 総和保存と均等化条件からtarget valuesと各個数を先に一意化する。

計算量と制約

時間

N、総和S、平均q=floor(S/N)、r=S−Nq。DP O(N(r+1))⊆O(N²)。

空間

rolling high値個数 O(r+1)、prefix和O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 5000; \lvert A_i \rvert \leq 10^9; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Approximate Equalization の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 資源・容量DP

主題
  • 資源・容量DP: 資源軸の上限と更新順を選び、選択の重複を避けられる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 資源軸knapsack DP

    補助タグ: 累積和・差分配列

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 資源・容量DP

    • 資源軸の上限と更新順を選び、選択の重複を避けられる。

    先に読む単元:

    この解説で扱わないこと:

    • 使用済み要素集合そのものを状態とし、容量・個数の値軸を持たないDP。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題