はまやんはまやんはまやん

hamayanhamayan's blog

Max Sum Counting [AtCoder Beginner Contest 216 F]

https://atcoder.jp/contests/abc216/tasks/abc216_f

前提知識

解説

https://atcoder.jp/contests/abc216/submissions/25449760

DPが分かっていることは前提なので勉強してきてほしい。

何から始めるのか

手がつかない場合は問題の弱点を探るのが良い。
今回は条件のうち、maxの上限が5000である部分が弱点となりうる部分である。
maxの上限が5000であるということはBの総和の上限も5000まで考えればいいことになる。
この条件は考察するうえでとても有用な条件であるように見える。

まあ、ここまではいいとして、ここからちょっと思考の飛躍が必要となる。
条件のmaxの値は選択された値の中での最大値によって決まり、
「それより小さい数についてはどのように選択されても変化しない」
といえる。
ここがとても重要な部分で、この「どのように選択されても変化しない」という部分にDPの同一視が適用できそうである。
さて、小さい数について、細かな状態は無視したいので、配列をまずはソートすることにする。
AとBを1つのグループにまとめてAでソートしておく。
max, sumや部分集合の選択方法に順番は影響しないので、ソートしても答えは変化しない。
この状態でDPを考える。

DP定義

dp[i][Btot] := i番目まで選択が確定していて、かつ、「i番目を選択していて」、かつ、選択した要素のBの総和がBtotである組合せ

このDPを更新していくことを考える。
これを貰うDPで実装していくことを考えると、

dp[to][Btot]の更新はto未満である全てのcuに対してdp[cu][Btot - B[to-1]]の総和

が更新ルールとなる。
これをそのまま実装するとO(N2 Bmax)になるので間に合わない。
更新時に利用している値は、toを1から順番に計算していることを考えるとdp[to未満の全て][とある値]の総和を取得していることになる。
これは事前に計算することができる。
よって、
tot[x] := dp[これまで][x]の総和
と定義して、dp[to][any]の更新が終わった直後に、totにその値を入れることで、
dp[to][any]を更新→tot[x]を更新→更にそれを使ってdp[to+1][any]を更新→…みたいな感じに高速に計算ができる。
この辺は累積和を使った更新最適化と捉えることもできる。
https://blog.hamayanhamayan.com/entry/2017/03/20/234711

答えを取得する

これでdp[i][Btot]について考えると、maxの値はA[i-1]になっているので、BtotがA[i-1]以下であるものが条件を満たすものになる。
なので、全てのdpの要素dp[i][Btot]についてBtot≦A[i-1]である組合せの総和を取れば答えになる。

int N;
int A[5010], B[5010];
pair<int, int> AB[5010];
mint dp[5010][5010];
mint tot[5010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];
    rep(i, 0, N) AB[i] = { A[i], B[i] };

    sort(AB, AB + N);

    dp[0][0] = 1;
    tot[0] = 1;
    rep(to, 1, N + 1) {
        rep(Btot, 0, 5010) if (AB[to - 1].second <= Btot) dp[to][Btot] = tot[Btot - AB[to - 1].second];
        rep(Btot, 0, 5010) tot[Btot] += dp[to][Btot];
    }

    mint ans = 0;
    rep(to, 1, N + 1) rep(Btot, 0, AB[to - 1].first + 1) ans += dp[to][Btot];
    cout << ans << endl;
}