476.1

手が遅いです...。気付くのも遅かったけど。

250

ペットを飼いたいが、個体ごとの飼育コストが、現在のペット数でリニアに変化する。このとき与えられた予算で最大何匹飼えるか、という問題。

K匹飼うときのコストをソートして小さい方からK個拾う、というのを試していくだけ。

550

見てない。

1000

ある2地点間をそれぞれの方向に移動できる最大人数が与えられる。最大人数を変更するという作業を任意に行って、N人の人がどのような初期配置にあっても地点0に移動できるようにしたい。ただし、どの地点も高々1個のループにしか含まれない。このときの変更する人数の最小値を答えよ、という問題。

グラフは、ループがいくつかと、それをつなぐループにはならない辺からなる。後者は常にN人通れるように修正しなくてはならない。つまりループの中をどう通れるようにするか、という問題でしかない。

各点について、ループの左側と右側にL人とR人とに分けるとする。左側での分配が分かれば、それよりも少ない人数しか左側に流せない。(流してもいいけれど、全体を再計算しないといけないし、意味がない。)これは単純なDPになる。

ここでNがかなり大きく、DPの各ステップがO(N^2)になるのを回避しないといけない。実は先の左側での分配からそれより少ない人数で、というくだりを拡張していくと、左側に流す人数というのは、初期値で出てくる数字から算出される値だけを考慮すればいいことになる。ループの長さはNと比較してかなり小さいので、これでTLEにはならない。