ABC 364 E — Maximum Glutton

考察

食事が終了するのは、直前までの甘さまたはしょっぱさが上限を超えた後である。したがって最後に食べる一皿を除いた集合の二合計はX,Y以下である。二合計を上限内に保って選べる最大皿数をmとすると、答えは全皿を選べる場合を除いてm+1である。最後の一皿の値は上限内である必要がない。dp[k][a]を甘さ合計aでk皿選ぶ最小しょっぱさとすれば、bを足す通常0/1 knapsackで存在性を圧縮できる。m<Nなら上限内集合を先に食べ、未選択の任意一皿を最後に食べることでm+1皿を必ず達成できる。

採用する候補: 選択個数と甘さ合計をkey、最小しょっぱさをvalueとするknapsack DPでmを求め、min(m+1,N)を返す。

大きい二予算の片方を最小化valueへ移し、Nが小さいことを状態軸として活用できる。

棄却する候補: 甘さ合計・しょっぱさ合計の二次元表に最大個数を持つ。

XとYがともに10000で積の状態数が大きく、料理数80という小さい軸を使えていない。

dp[0][0]=0、他を∞とする。各料理(A_i,B_i)についてkと甘さaを降順に走査し、dp[k+1][a+A_i]をdp[k][a]+B_iでmin更新する。a≤Xかつdp[k][a]≤Yとなる最大kを探し、min(k+1,N)を出力する。

典型の発動条件

DPのkey-value交換

発動条件: 二つの資源上限の積が大きいが、選択個数が小さいとき。

一方の資源と個数をindexにし、もう一方の最小消費をvalueにする。

停止直前集合への変換

発動条件: 閾値超過を起こす最後の操作も回数に含まれるとき。

最後の一手を外したfeasible集合を最適化し、答えへ一つ戻す。

問題固有の要素

制約を満たす皿数そのものではなく、その直後に閾値を超える一皿も食べ終えられるため+1が付く。

別の問題へ持ち帰る視点: processが違反検出後に停止するなら、違反を起こしたactionが成果に含まれるか確認する。

正当性

countと甘さを固定して塩気最小だけ持つと、他の候補は両制約への余裕で劣る。全料理の選択/非選択を旧行から更新して最大feasible count kを得る。実際はそのk個の後に閾値を超す一皿も食べられるため min(k+1,N)。

実装上の注意

  • 0/1選択なのでkとaを降順更新する。a+A_iはXを超える状態を保持せず、答えの+1はNでcapする。

復習の核

  • 「食べられる」と「次を選べる」の時点を区別し、N=1や全皿が上限内の例で+1処理を確認する。

計算量と制約

時間

N料理、甘上限X。選択個数×甘さ DP O(N²X)。

空間

count×甘さ O(NX)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 80; 1 \leq A_i, B_i \leq 10000; 1 \leq X, Y \leq 10000; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Maximum Glutton の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

      主タグ: 資源軸knapsack DP

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

      学習の位置

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

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

      先に読む単元:

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

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

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題