2019-08-05

大手前プロコン 2019：E - 最悪の教頭 (Worst Head Teacher)

問題
解法
解答

問題

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) 秒後になる．

各クエリの T_i 秒後の区間 [L_i, R_i] を T_i - L_i + 1 秒後の区間 [1, R_i - L_i + 1] として考える．T_i - L_i + 1 秒後にこの区間にいる条件は，座標 1 に到達するのが [T_i -R_i + 1, T_i - L_i + 1] 秒後であるときになる．この区間に含まれる t_i の個数を std::lower_bound(), std::upper_bound() を用いて計算すればよい．O(N + QlogN)．

解答

https://atcoder.jp/contests/otemae2019/submissions/6696894

f:id:babcs2035:20190805154915p:plain

2019-08-05

大手前プロコン 2019：D - FizzBuzz (FizzBuzz)

競技プログラミング AtCoder その他の問題

問題
解法
解答

問題

https://atcoder.jp/contests/otemae2019/tasks/otemae2019_d

解法

以下の DP を考える．

dp(i, j, k) := 上から i 桁目まで決めて，今まで j 回発言し，上から i 桁目までの整数を 3 で割った余りが k であるときの，i + 1 桁目以降の通り数

遷移は i + 1 桁目に 0 ~ 9 を当てはめてみればよい．当てはめたあとの k を newK とおくと，newK == (k * 10 + l) % 3 (0 <= l <= 9) となる．newK が 3 で割り切れるとき，3 の倍数が構成できており，l == 0, 5 であるとき，5 の倍数が構成できている．構成出来た倍数と j + 1 回目の発言の内容が一致していれば dp(i + 1, j + 1, newK) に遷移すればよい．もし，3 の倍数でも 5 の倍数でもないときは dp(i + 1, j, newK) に遷移すればよい．O(NM)．