ABC 415 E — Hungry Takahashi

考察

右/下へ一歩進むたびi+jが1増えるため、cell(i,j)を訪れる日はpathによらずi+j-1日目に固定される。B_{i,j}=A_{i,j}-P_{i+j-1} とすれば各cell到着時の所持金変化になり、必要なのは全prefix所持金を非負にできるright/down pathと最小初期額である。dpは現在cellでcoinsを回収・食費を払う前の額なので、現在のnet Bを得た後に次cellの必要額を満たす条件はcash≥nextNeed-Bである。必要額は非負に制限されるためBが十分正なら0でよい。grid外の遷移を∞とすればedge/cornerも同じ式で処理できる。

採用する候補: dp[i][j]をcell到着直前に必要な最小所持金としてgoalから逆向きに計算する

次cellへ必要な額の小さい方を選び、現在の純増Bを差し引いて0未満をclampすれば dp=max(0,min(down,right)-B)。局所最適が将来必要額を完全に表す。

棄却する候補: 初期額xをbinary searchし、各xについて到達可能cellと最大残金をforward DPする

判定一回O(HW)にさらにlog answerが掛かり、必要資金を逆算すれば一回のDPで厳密値が得られる。

必要額は非負に制限されるためBが十分正なら0でよい。

各cellのB=A-P_{i+j-1}を計算する。i=H..1,j=W..1の逆順で、goalはmax(0,-B)、他はmax(0,min(dp[i+1][j],dp[i][j+1])-B)とする。dp[1][1]を出力し、rolling rowでもO(W) memoryにできる。

典型の発動条件

必要資源の逆向きDP

発動条件: 各地点で資源が増減し、終点までprefix非負にする最小開始資源を求めるとき。

後続の必要額から現在の純増を引き、0でclampして逆算する。

時刻の座標不変量

発動条件: monotone grid pathでevent costがstep番号に依存するとき。

i+j-1が訪問日と固定されることからcell weightへ日別costを埋め込む。

問題固有の要素

日ごとの食費をpath状態として持たず、monotone移動の対角線番号へ吸収すると、通常のweighted grid DPになる。

別の問題へ持ち帰る視点: step依存costがある格子路では、全pathが同じ座標へ同じstepで着くrank関数がないか先に調べる。

正当性

dpはそのマスへ入る前に必要な最小所持金。後続へ必要額はdown/rightの小さい方で、その額から現在純増Bを引く。所持金非負条件を加えてmax(0,need−B)。どの額もこの最小以上なら同じ将来pathが可能なので局所最小が十分。

実装上の注意

  • goalでもその日の回収後にPを払うためmax(0,-B_goal)が必要。差と累積必要額は64 bitを使い、H=1またはW=1の唯一pathも扱う。

復習の核

  • 1×1、全B正、最初に大赤字後で黒字、二pathで最終利益とprefix不足が逆転する例を全pathのprefix和と比較する。

計算量と制約

時間

H×Wマス。逆順DP O(HW)。

空間

rolling row O(W)、入力A保持なら O(HW)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: H,W\geq 1; H\times W \leq 2\times 10^5; 1\leq A_{i,j}\leq 10^9; 1\leq P_k\leq 10^9; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Hungry Takahashi の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: グリッド・多次元表の局所DPを設計する

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: グリッド・多次元表の局所DP

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

      学習の位置

      体系上の位置: グリッド・多次元表の局所DPを設計する

      • グリッドまたは多次元表の依存方向と境界状態を定め、計算済みの局所近傍からDAG順に全状態を更新できる。

      先に読む単元:

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

      • 一次元の初歩的なDP、部分集合・資源DP、および区間の分割点を列挙する区間DP。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題