問題 解法 解答 問題 https://atcoder.jp/contests/otemae2019/tasks/otemae2019_g 解法 N が大きいので，P, Q, R, S, A_i, B_i, C_i, D_i を x, y 座標に分けて座標圧縮をする．また，上下・左右方向にワープ可能な領域をそれぞれ累積和で求めておく．この…

問題 解法 解答 問題 https://atcoder.jp/contests/otemae2019/tasks/otemae2019_f 解法 以下の DP を考える． dp(i, j) := i 日目で右側に j 枚コインがあるとき，i + 1 日目以降のコストの和の最小値 遷移は，右側にのせるコインは j 枚のまま次の日にいく…

問題 解法 解答 問題 https://atcoder.jp/contests/otemae2019/tasks/otemae2019_e 解法 参加者 i は (D_1 - 1) + (D_2 - 1) + ... + (D_i - 1) 秒後に動き始める．これを t_i とおく．なので，参加者 i が座標 1 に到達するのは t_i + (1 + i) 秒後になる．…

問題 解法 解答 問題 https://atcoder.jp/contests/otemae2019/tasks/otemae2019_d 解法 以下の DP を考える． dp(i, j, k) := 上から i 桁目まで決めて，今まで j 回発言し，上から i 桁目までの整数を 3 で割った余りが k であるときの，i + 1 桁目以降の…