ABC 226 G — The baggage

考察

荷物の重量と人の体力は1,…,5だが個数は10^16まである。個人単位に展開せず、重さwの荷物数A_wと残り体力cの人数bucketで処理する。総重量だけでは、体力3一人に重さ2二個を入れられないという容量の断片化を見落とす。

重さ3以上は一人に高々一個だから、まず重い物から適合人数を確保する。5→体力5、4→体力4の後5、3→体力3の後5、最後に4という順にする。3を単に弱い適合人から順に置かず、5を4より先にする理由は、残りが2になる方が残り1になるより重さ2に有用だからである。

これを数字で比較する。重さ5,4,3を全て置いた後の残余総量V=ΣcB_c−Σ_{w=3}^5wA_wは配置によらない。残余が奇数の人数をO、重さ3を体力4へ置いた人数をzとすると

O = B_1+B_3+B_5 − A_5−A_3 + 2z
重さ2を置ける総枠U = (V−O)/2

となる。5は奇数残余を一つ減らし、4は偶奇を変えず、3は奇数体力なら奇数残余を一つ減らし、体力4なら一つ増やすためである。従ってzを最小にすることがUを最大にする。体力5へ置かざるを得ない4はmax(0,A_4−B_4)個なので、3に残せる体力5の最大数はB_5−A_5−max(0,A_4−B_4)。体力3も先に使うと、必要なzの最小値は

max(0, A_3−B_3−(B_5−A_5−max(0,A_4−B_4)))

で、上の順序がこれを達成する。

実装ではpack(w,c)をq=min(残荷物[w],残余人数[c])として、荷物[w]と人数[c]からqを引き、人数[c−w]へqを加える操作にする。pack(5,5),(4,4),(4,5),(3,3),(3,5),(3,4)の後、重さ2はc=5,4,3,2の降順、重さ1はc=5,4,3,2,1の降順でpackする。降順なら同じ人が減った残余bucketへ移って再度載せる処理も定数回で済む。残荷物が全て0ならYesとする。

典型の発動条件

定数種類のbucket貪欲

発動条件: 値・容量の種類が小さな定数で個数だけが巨大であり、同じ種類の対象を区別する必要がないとき。

残り容量ごとの人数と重量ごとの荷物数だけを持ち、一回のmin演算で同種の割当てをまとめて進める。

残余容量の断片化を守る交換論法

発動条件: 総容量だけでは不十分で、次に置く荷物が特定の剰余・最小bucketを必要とするとき。

重い荷物の割当て順を交換し、重さ2に使える偶数部分の総量を最大に保つ順序を選ぶ。

問題固有の要素

重さ3を載せる先は強い人から単純に使うのではなく、体力5を体力4より先に使うことで、後の重さ2に使えない余り1を増やさずに済む。

別の問題へ持ち帰る視点: bin packing型の貪欲順は残余総和だけでなく、次の品物単位に対する余りの剰余分布まで比較する。

正当性

重さ3以上を各人が高々一個持つことから、A_5≤B_5、A_4+A_5≤B_4+B_5、A_3+A_4+A_5≤B_3+B_4+B_5は必要である。指定順は、5だけが使える人、4以上だけが使える人を先に確保するので、これらが満たされれば重さ3以上を全て置ける。

その任意の配置で残余総量Vは一定で、重さ2の総枠はΣfloor(残余/2)=(V−O)/2。重さ4を体力4へ最大限置くと、重さ3に残せる体力5の人数を最大にできる。さらに体力3と5を先に使うことで、3を体力4へ置く人数zを考察の下限まで減らせる。O=B_1+B_3+B_5−A_5−A_3+2zだから、この貪欲は全ての重荷物配置の中で2用の枠を最大化する。

残る荷物は1と2だけである。この残余配置へ置ける必要十分条件はA_2≤Uと2A_2+A_1≤V。前者なら各人のfloor(残余/2)枠へ2を任意に置け、置いた後の全残余V−2A_2には後者により全ての1が入る。従って実現可能解が一つでもあれば、U最大の貪欲配置でも2と1を全て置ける。逆に完了したbucket操作は合法な割当てを表すため、成功判定も正しい。

実装上の注意

  • 元のA,Bを用いる証明のV,O,Uと、packで更新する残荷物・残余人数を区別する。全て64bit整数で保持できる。
  • 重さ2を一人に一個だけ置くのではない。c=5から降順にbucketを移すと5→3→1、4→2→0も処理できる。
  • 重さ3は体力3,5,4の順。体力4を先に使うと、2用の枠を一つ失う場合がある。

復習の核

  • 総重量条件だけで満足せず、次に重い単位が入る『まとまった残余容量』を何個残せるかまで追う。

計算量と制約

時間

O(1)、重量/体力値域1..5の固定bucket。

空間

O(1)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq T \leq 5\times 10^4; 0 \leq A_i,B_i \leq 10^{16}; 1 \leq A_1+A_2+A_3+A_4+A_5; 1 \leq B_1+B_2+B_3+B_4+B_5; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

The baggage の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 交換論から選択順を導く

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

      主タグ: 貪欲法と交換論

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

      学習の位置

      体系上の位置: 交換論から選択順を導く

      • 局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。

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

      • 対称操作による状態の正規化。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題