ABC159 - F - Knapsack for All Segments
概要
長さNの数列A[]が与えられる。次のようにf(l, r)を定める。
- l <= x_1 < x_2 < ... < x_p <= rで、x_1+x_2+...+x_p=Sになるような(x_1, x_2, ..., x_p)の選び方の場合の数(x_1, x_2, ..., x_pがすべて一致する場合だけを1通りと数える)
さて、1 <= l <= r <= Nとなるすべてのf(l, r)の和を998244353で割ったあまりを答えよ。
制約： 1 <= N <= 3000, 1 <= S <= 3000, 1 <= A[i] <= 3000
ACするまで
1. ひとまず、とある区間の始点と終点を固定して、そこで作れる場合の数が分かれば、これの重複カウントの回数がわかる。
2. よって、始点と終点を固定して考えてみたが、これでDPをする場合、始点、終点、和の3重ループになってTLEする。(愚直解と同じ)
3. フラグを持たせてうまくDPできないか？と考える。
4. しかし、フラグでいい考えがまとまらず、コンテスト時間TLE。
5. フラグ持たせてDPをする。選びはじめと選び終わりを明確化して、フラグ(3値)を持たせれば
考察
この問題には本質的には同じながらも、複数の解法が存在する。
解説解法
愚直解を考えてみると、始点を毎回ずらして、そしてナップサック問題を解くということになり、これは計算量となり、TLEする。
この中で削れる計算量は何だろうか？
本質的にはナップサック問題をするため、ナップサックの計算量は落とせなさそう。→1つずつずらさないようにDPできないか？
ずらす必要があるのは、どこから始まったのか？を明確的に持つ必要があったから。これをフラグで圧縮できないかを考える。
結論から言うと、これは
の3値フラグを持たせればよい。
区間を閉じるという操作は、和に関係なく行えて、最終的に和がSになってる区間が閉じられたもののみ見ればよい、と考えれば次のように遷移できる。
まだ区間を始めていない場合
の3通りがある。
区間を始めて、まだ閉じてない場合
- 今の数字を素通りする。
- 今の数字を素通り or 選択して区間を閉じる。
の2通りがある。
区間をもうすでに閉じた場合、
- 今の数字を素通りする。
の1通りしかない。
以上のを実装すれば、無事解ける。
ACソースコード：
Submission #11139418 - AtCoder Beginner Contest 159
余談だが、配るDPでMODを取るとき、
(dp[i + 1][j + A[i]][1] += dp[i][j][0] + dp[i][j][1]) % MOD;
で簡単に書ける。
ちなみに、ほかにDPにフラグを持たせると簡単に解ける問題としては、次のようなものがある。
sen-comp.hatenablog.com
ikefumy解法
これはikefumy(@ikefumy000)さんから教えてもらった解法で、個人的には公式解法よりも思い浮かびやすかった。
始点と終点両方を決めて、数え上げる場合では愚直解と同じ計算量になるが、終点だけ固定する場合はどうなんだろうか？
始点任意で、終点だけ固定すると、0-idxでi番目の要素で区間を閉じる、ということならば、数え上げに寄与するのはN - i通りである。
始点任意でどう計算するかだが、これは普通のナップサックを書いて、dp[i][j] := i番目まで選んで和がjになったときの場合の数、として
dp[i][0] = i + 1; iは0-idx
とすればよい。(何も選ばない場合、始点をどこから始めるかで上のような場合の数がかかる)
あとは、普通のナップサックと違うのは、和がSになった時点でdp[i + 1][S] += dp[i][S]せずに、その時点で答えに寄与する分を後ろの余ってる長さのぶんだけかけて(この時点ですでに和がSなので、後ろの余ってる場所のどこで区間を終了させてもいい)、答えに足すことである。
ACソースコード：
Submission #11139734 - AtCoder Beginner Contest 159
こちらの方がコーディング量が減って書きやすいかもしれない。
一言
典型で解けそうなのに、あと一歩足りなかった。自分に足りないものがよく認識できる。
