G - The baggage Editorial by kyopro_friends
次の手順で荷物の割り当てを決ればよいです。
- ステップ1：各 \(i\) について、重さ \(i\) の荷物を可能な限り体力 \(i\) の人に割り当てる
- ステップ2：残りの荷物を、重い順に、可能な限り体力の高い人から割り当てる。すなわち、次の順序で割り当てを行う。ただし、割り当ての過程において、体力 \(i\) の人に重さ \(j\) の荷物を割り当てた後、その人は体力 \(i-j\) の人として扱うことにする。
- 重さ \(5\) の荷物を可能な限り体力 \(5\) の人に割り当てる
- 重さ \(4\) の荷物を可能な限り体力 \(5\) の人に割り当てる
- 重さ \(4\) の荷物を可能な限り体力 \(4\) の人に割り当てる
- 重さ \(3\) の荷物を可能な限り体力 \(5\) の人に割り当てる
- 重さ \(3\) の荷物を可能な限り体力 \(4\) の人に割り当てる
- 重さ \(3\) の荷物を可能な限り体力 \(3\) の人に割り当てる
- 重さ \(2\) の荷物を……以下省略
正当性の証明
「もし答えがYesなら、この手順で構築可能な全ての荷物の割り当て方が存在する」 を示せば十分。
ステップ1について。もし、体力 $i$ であって、重さ $i$ の荷物を持っていない人 $X$ と、体力が $i$ でなく、重さ $i$ の荷物を持っている人 $Y$ が存在したと仮定する。このとき、$X$ の持っている全ての荷物と、$Y$ の持っている重さ $i$ の荷物を交換することができる。この操作を繰り返すことで、ステップ1の条件は必ず満たすことができるとわかる。
ステップ2について。ステップ1の証明と同様に、適切に荷物をswapすることで、前の条件から順に満たされているようにできることを示す。例として「ステップ1の条件を満たし、かつ、ステップ2の過程のうち『重さ $3$ の荷物を可能な限り体力 $5$ の人に割り当てる』が初めて満たされていない」場合を示す。すなわちこのとき、重さ $3,4,5$ の荷物を持っていない体力 $5$ の人 $X$ と、重さ $3$ の荷物を持っている体力 $4$ の人が存在する。体力 $5$ の人が重さ $1,2$ の荷物を持っているかどうかで $4$ 通りに場合分けをすると、いずれの場合も、$X$ の持っている荷物のいくらかと、$Y$ の持っている重さ $3$ の荷物を交換できることが示せる。他の場合も同様である。
なおこの割り当て方は、問題の値が1から5ではなく、1から6の場合破綻します。（体力5,6の人が1人ずついて、荷物が4,3,3,1のケースと、4,3,2,2のケースを考えると貪欲な割り当てが困難であることがわかります）
posted:
last update: