Codeforces Round 919 (Div. 2)

　Dまで四完。

コンテストへのリンク

コンテスト後のツイート

D 操作をx回行ったときのAの長さをもっておき、クエリkが何回目の操作で超えるかを二分探索。その操作が倍加のものだったら、余りを取って同じことを行う。
E DP[x][y]を直前にy個0があり、良いstringの個数がx個である個数というDP。x,yを小さい方からやっていけば三乗になるけど、三乗で通るのかな。

— titia (@titia_til) January 13, 2024

E. Counting Binary Strings

　ツイートした方法で通った。

　D通した時点で残り時間が少なかったけど、そこまで難しくないDPなので20分あれば通せて良かった。DPの高速化する問題だろう、と思うなら、dict（Counter）でDPを実装したのは筋が悪かった。dictで実装すると高速化が必要なとき手間が増えてしまう。