きろく

特筆すべき記録のまとめ

AtCoder Beginner Contest 123:C - Five Transportations

問題

atcoder.jp

解法

A, B, C, D, E のうち最も少ない人数に合わせて人を運ぶという方針でよい.なぜなら,それより多い人数を運んでも,容量の小さい箇所で人が溜まってしまい,結局は同じになってしまうから.よって,容量の小さい箇所を i とすると,N 人のうち最初の min(A, B, C, D, E) 人がそこまで到達するのに i - 1 分,N 人が i を通過するのにかかるのが ceil(N / min(A, B, C, D, E)) 分,N 人のうち最後の日とがゴールまで到達するのに 5 - i 分かかるので合計して 4 + ceil(N / min(A, B, C, D, E)) 分.O(1).

解答

atcoder.jp

f:id:babcs2035:20190408133938p:plain