ABC 322 E — Product Development

考察

各parameterは目標Pを超えた量が以後の達成可否やcostへ影響しないため、値をmin(value,P)へcapできる。K,P≤5なので、cap後のparameter vectorは各成分0..Pの(P+1)^K通りしかない。各planは一度だけ使えるので、planを順に見てskip/takeする0/1 DPにできる。状態aからplan iを取った先は各jでa'_j=min(P,a_j+A_{i,j})となり、将来に必要な情報を完全に保持する。vectorをbase P+1の整数へencodeすれば、固定長array上で全状態を走査できる。

採用する候補: capしたK次元parameter vectorを状態とし、各planの不採用・採用をrolling DPで更新する。

2^Nのsubsetを同じ到達parameterへ集約し、各状態には最小costだけを残せる。

棄却する候補: 全plan subsetを列挙してparameterとcostを計算する。

N≤100で2^N通りは扱えない。

棄却する候補: costあたりparameter増加が大きいplanからgreedyに選ぶ。

K個の不足方向が異なり、1つの比率では相補的なplan組合せの最小costを決められない。

state数D=(P+1)^K、dp[0-vector]=0、他INFで始める。各planについてnext=dpを作り、全stateをdecodeして各成分をPでcapしながらA_iを加えたtoをencodeし、next[to]=min(next[to],dp[state]+C_i)とする。dp=nextを繰り返し、全digit PのgoalがINFなら-1、そうでなければそのcostを出力する。

典型の発動条件

達成thresholdでの状態cap

発動条件: 値が目標以上かだけが重要で、増加操作しかないとき。

各parameterをPで打ち切り有限状態化する。

多次元状態のmixed-radix encode

発動条件: 各成分が小さい固定範囲のvector DP。

base P+1の1整数へ写してdense arrayを使う。

0/1 item DP

発動条件: 各planを高々一度だけ選ぶ最小cost問題。

前layerからskip/takeの2遷移を行う。

問題固有の要素

parameterの実値は最大ΣAまで伸びるが、全成分について「P未満の正確値」または「達成済みP」のK桁だけが選択の将来効果を決める。

別の問題へ持ち帰る視点: 単調resourceを複数持つ最適化では、各目標thresholdで同値状態をまとめてstate productを小さくする。

正当性

各parameterはP以上で将来区別不要なのでcapが安全。同じcapvectorへの到達はcost小が常に有利。各planで不採用・採用一回を旧行から生成する帰納法により全subset最小costを得る。

実装上の注意

  • 同じplanを複数回使わないよう、更新先を別arrayにするか、元dp snapshotからのみ遷移する。
  • 最小costは最大100×10^9なので64bit整数と十分大きいINFを使う。

復習の核

  • Pを超える増加を含む2-parameter例をencodeし、異なる実値が同じcap状態へmergeされても将来の最小costを失わないか確認する。

計算量と制約

時間

N plan、K parameter、目標P、状態D=(P+1)^K。decode/update O(K)で O(NKD)。

空間

rolling dp O(D)、入力 O(NK)。

制約との対応

公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 1 \le N \le 100; 1 \le K,P \le 5; 0 \le A_{i,j} \le P(1 \le i \le N,1 \le j \le K); 1 \le C_i \le 10^9(1 \le i \le N); All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Product Development の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

    主タグ: 資源軸knapsack DP

    補助タグ: DPの最小十分状態

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

    学習の位置

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

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

    先に読む単元:

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

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

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題