AGC011 A, B 考察

AGC011 A - Airport Bus

バスの数を最小にしたいので各バスに乗せられるだけ乗せるようにすると良さそうだ。 T_i + K まで出発を遅延させてその時点で到着している人を乗れるだけ乗せるという貪欲法で解けそう。証明はできないけどおそらく最善だ。

まず T を昇順にソートしておく。しゃくとりの要領で l と r を 0 から N まで走査する。 T_r <= T_l + K の間 r を進める。進めなくなったところでバスに乗せる。 l を C だけ進める (ただし r を超える場合は r + 1 までにする) 。バスに乗せた回数が答えになる。

https://atcoder.jp/contests/agc011/submissions/16083873

AGC011 B - Colorful Creatures

A を昇順にソートしておく。 i が i + 1 を食べられるかどうかは A_1 から A_i までの和を S_i として S_i * 2 >= A_{i + 1} で表される。前から順に最後まで食べ切れる生き物かを確認する。食べきれなかった生き物を生き物の総数から引くと答えになる。

https://atcoder.jp/contests/agc011/submissions/16084114

ABC176 嘘解法っぽいもので通して良い成績になりそう。また書く。

熱が出ている。