問題 解法 解答 問題 atcoder.jp 解法 dp(i, j, k, l) := 今 i - 1 文字目まで考えて，i - 3 文字目が j，i - 2 文字目が k, i - 1 文字目が l のときの，i 文字目から先の通り数 と DP を定義する．次の１文字（すなわち i 文字目）を決めるとき 'A', 'T', …

問題 解法 解答 問題 atcoder.jp 解法 N, Q <= 10^5 より，各クエリごとに文字列を走査していては間に合わない．そこで，各クエリに O(1) で答えられるようにする． imos_i := i 文字目までに登場する "AC" の数 とおくと，各クエリで求める値は imos_r - im…

問題 解法 解答 問題 atcoder.jp 解法 前から操作を見るのは実は困難なので，後ろから見ていく．このとき，問題は「場所 i で数字 i を消すことができる．この消し方とは？」と言い換えられる．また，消す場所は消せる場所の中で一番右がよい．なぜならば，…