ABC159F - Knapsack for All Segments
DPの考え方の整理と全完を逃した反省文として。
問題リンク
https://atcoder.jp/contests/abc159/tasks/abc159_f
考え方
配列Aの[L,R]での範囲について総和がSになるような部分列の作り方の通りについて、1≤L≤R≤Nを満たすL,R全てに対する総和はいくつか求める問題。
問題文そのままでL,R全通り試していてはTLに間に合わない。
そこで、総和がSになるような部分列の作り方を先に見つけておいて、その部分列が作れるL,Rの組の数を数えるようにする。
この問題文の言い換えはABC151Eとか第6回ドワンゴ予選Bとかでも出た頻出パターン。
総和がSになるような部分列の作り方を求めるのはDPみを感じる。
部分列の左端・右端のインデックスも知りたいのでdp[左端][右端][総和]みたいな配列を作りたくなるが、これだと3重ループになって間に合わない。
そこで耳DP。
dp[N][S][t(状態)]とおいて、
t=0: 左端も右端も未確定な状態
t=1:左端は確定したが右端は未確定な状態
t=2: 左端も右端も確定な状態
とする。
左端を確定させる(t=0->1へ遷移させる)ときに取り得るLの範囲(i+1)を掛けておく。
右端も同様に、右端を確定させる(t=1->2へ遷移させる)ときに取り得るRの範囲(N-i)を掛けておく。
左端/右端を同時に確定させる(t=0->2へ遷移させる)パターンもあって、その場合は(i+1)*(N-i)を掛けるところに注意。
求めたい答えはdp[N][S][2]。
提出コード
https://atcoder.jp/contests/abc159/submissions/11157006
考え方2
dp[N][S]とおいて、dp配列に状態を持たせずにやってみる。
左端が確定するタイミング＝部分列の総和が0からA[i]に増えるタイミングなので、そこで一緒に(i+1)を掛けておく。
右端については、今回興味があるのは部分列の総和がSになるものだけなので、総和がA[i]-SからSに増えるタイミングで(N-i)を掛けておく。
求めたい答えはdp[N][S]。
提出コード
https://atcoder.jp/contests/abc159/submissions/11157008
EDPCで勉強してDPが結構書けるようになってきたと思ってきたところだったので、今回Fが通せなかったのは悔しい。
まだまだ精進不足ですね。
TDPCの方も解いてみようかな。
謝辞
提出コードを実装するにあたり、けんちょんさんのModintライブラリを利用させていただきました。
ありがとうございました。
https://drken1215.hatenablog.com/entry/2020/03/22/224200
