ABC024 A, B, C 考察

ABC024 A - 動物園

合計人数 (S + T) が K 以上なら S * (A - C) + T * (B - C) を K 未満なら S * A + T * B の入場料になる。

https://atcoder.jp/contests/abc024/submissions/15708840

ABC024 B - 自動ドア

ある人が来てから最長で T 秒開く。ただし次の人が T 秒経つ前に来た場合は次の人から T 秒しか開かない。つまり A_i と A_{i + 1} の間が T 秒以下なら A_{i + 1} - A_i 秒を合計に加算し T 秒を超えているなら T 秒を合計に加算していく。最後の A_N は次の人がいないので T 秒開くので合計に T を加算する。 O(N) で N <= 10^5 なので間に合う。

MIN(A_{i + 1} - A_i, T) を加算していけば良いと気づいたので書き直した。

https://atcoder.jp/contests/abc024/submissions/15709707

ABC024 C - 民族大移動

S_i < T_i ならその民族は → の街へ。 S_i > T_i ならその民族は ← の街へ移動していくと良い。移動できるタイミングはその民族のいま居る街を C_i とすると L_i <= C_i <= R_i のとき。移動できる先は ← は L_i まで → は R_i までだ。いまいる街 C_i と T_i に到達したときの日数 D_i を記録しておく。前から順に D 日を走査し日ごとにすべての民族 K 種類を走査して上記の移動を繰り返せば良い。 O(DK) で D <= 10^4 K <= 100 なので DK <= 10^6 となり間に合う。

https://atcoder.jp/contests/abc024/submissions/15709376

リングフィットアドベンチャーを続けている。