Hatena::Grouptopcoder

しめじ栽培室@TopCoder部

2011-01-19

SRM 483 Div1 Hard Sheep

23:53

あとで

if the correct answer to the problem is C, i.e. we can take all sheep with maxRuns runs or less when the boat has capacity C, then we also can make it with all capacities greater than or equal to C + MAX_WEIGHT,

where MAX_WEIGHT is the weight of the heaviest sheep

no boat can be less full in a scheme where the capacity is >= C + MAX_WEIGHT than one where capacity is C, unless there are no more sheep to take.

If such a boat were less full, then there would be space in the boat more than or equal to MAX_WEIGHT (and can put a sheep there). Since all the boats are at least as full, if we require more boats then the total mass of sheep must have increased.

2011-01-17

SRM 481 Div1 Hard TicketPrinters

| 11:24

ここで練習会で解けなかった問題の復習をして行く予定です。

多分Editorialの解説や誰かのコードを見て勉強したことのメモが大半になると思います。

続きを読む