ABC 421 G — Increase to make it Increasing

考察

range [L,R]への+1は差分dでd[L-1]へ+1、d[R]へ-1を移す操作になる。非減少条件は内部差分d[1..N-1]を全て非負にすることなので、余剰boxから不足boxへballを運ぶ問題になる。d_i>0は供給、d_i<0は需要で、index Nは最終値を上げても内部非減少性を壊さない無限供給源とみなせる。range操作(L,R)はRからL-1へunitを運ぶ。

採用する候補: 差分indexを頂点とするmin-cost flow

各許可rangeを一球移動cost1の有向辺にし、不足総量を満たす最小operation数をflow costとして得られる。

棄却する候補: 各負差分を局所的に直すgreedy

一つのoperationがどの余剰sourceをどの不足へ運ぶかの組合せがあり、局所選択は全体最小costを保証しない。

range操作(L,R)はRからL-1へunitを運ぶ。

sourceから正d_iへcapacity d_i、負d_iからsinkへcapacity -d_i、sourceからNへINF、各rangeにR→L-1 capacity INF cost1を張る。需要Kのmin-cost flowが流れなければ-1、流れればcostを出す。

典型の発動条件

差分によるrange update変換

発動条件: range一様加算を端点二箇所の変化へ写す。

Aの拡張差分d_0…d_Nで操作をunit transferとして表す。

min-cost flow

発動条件: 供給から需要へ許可edgeを通してunitを運び、edge使用回数和を最小化する。

不足総量をrequired flowとし、range edgeだけcost1にする。

問題固有の要素

末尾差分d_Nは負でもよいため、box Nを無限供給にすることで総和保存と目的制約を同時に表現できる。

別の問題へ持ち帰る視点: 制約外の境界differenceをslack source/sinkとしてflow modelへ組み込む。

正当性

区間加算は差分box RからL−1へ一unitを動かす。内部負差分の不足を満たすflowがちょうど非減少化で、cost1のrange辺の流量和は操作回数。box Nの無限供給と正差分供給は末尾増加/余剰を許し、flow分解で操作multisetへ戻せる。

実装上の注意

  • d_0=A_1とd_N=-A_Nを含むindexを正しく作り、required flowは内部0..N-1の負分だけを数える。

復習の核

  • 単一不足、Nからの供給必須、到達不能なtransfer graphを小整数探索と比較する。

計算量と制約

時間

N要素M区間、差分不足総量K。V=N+3,E=O(N+M)、potential min-cost flowの安全上界 O(K E log V)。

空間

差分とnetwork O(N+M)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq N \leq 300; 1\leq M \leq 300; 1\leq A_i \leq 300; 1\leq L_i\leq R_i\leq N; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Increase to make it Increasing の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 最小費用流・circulation

主題
  • 最小費用流・circulation: 流量と費用を持つ残余networkを設計し、potential付き最短路・slope・cycle cancelingで流量別最小費用を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 最小費用流・circulation

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

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

    学習の位置

    体系上の位置: 最小費用流・circulation

    • 流量と費用を持つ残余networkを設計し、potential付き最短路・slope・cycle cancelingで流量別最小費用を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題