https://atcoder.jp/contests/abc169/tasks/abc169_f

前提知識

動的計画法

解説

https://atcoder.jp/contests/abc169/submissions/13925811

問題設定がややこしいが、慣れている人であれば、これは主客転倒テクをしてくれというメッセージにも見える。
一部が言ってるだけなので、あまり強調すると怒られそうだけれど、主客転倒テクという言い方は便利なので、
できれば使いたい。
主客転倒テクは、
「Aを全列挙して、それぞれに含まれるBの点数を全部計算して足す」
みたいな問題を
「Bを全列挙して、それが出てくるAの組合せを計算して、(Bの点数)×(Bが出てくる組み合わせの総和)」
のように言い換えること。
この手の言い換えはよく見るし、テクニックとしてもいいと思う。

さて、これを使ってどうするかであるが、
部分集合Tを全列挙して、f(T)を全部計算して足すのが、この問題。
f(T)というのは、Tから更に部分集合Xを取って総和がSとなる部分集合Xの個数。
主客転倒する。
今回の問題は、「総和がSとなる部分集合X」を部分集合に持つTの組合せの総和が答えと等しくなる。
(Bの点数)×(Bが出てくる組み合わせの総和)と比較してみると、Bの点数にあたる部分は1なので、消えている。
ここまでをまず理解しないと進まない。

ここまでしっかり理解できていれば、1つ目の山は越えられている。
「総和がSとなる部分集合X」を部分集合に持つTの組合せは何通りになるだろうか。
例えば、X={x1, x2, ..., xk}であるとすると、これを部分集合に持つTは少なくとも、Xは持っている。
それ以外は持っていてもいいし、持っていなくてもいい。
よって、2^N-k通りある。
この組合せで重要なのは集合Xの要素数だけである。
よって、総和がSである集合Xを考えるが、要素数を除いて抽象化して問題ないということだ。
以下のDPを考える。

dp[i][tot][k] := i番目までのAを使って、総和がtotで要素数がk個の組合せ
これを使えば、k=1..Nについてdp[N][S][k] * 2^{N - k}の総和が答え。
このDPを作るまでが2つ目の山。

このDPではO(SN²)なので間に合わない。
もう1段落工夫が必要である。最後の山である。ここがきつい。
dp[i][tot][k]の更新式は

dp[i + 1][tot][k] += dp[i][tot][k]
dp[i + 1][tot + A[i]][k + 1] += dp[i][tot][k]

であり、最後にdp[N][S][k] * 2^{N - k}としている。
最後をちょっと変形してみると、dp[N][S][k] * 2^N / 2^kである。
つまりは、要素数分÷2をしている。
言い換えると、選択する遷移回数文÷2をしている。
よって、遷移式を以下のように変える。

dp[i + 1][tot][k] += dp[i][tot][k]
dp[i + 1][tot + A[i]][k + 1] += dp[i][tot][k] / 2

すると、最後はdp[N][S][k] * 2^Nとなる。
これが重要でkの要素を持っていたのは最後に必要だったからで、遷移に÷2を持ってくることで最終的に
kを使って係数を変えて足し合わせる必要がなくなった。
つまり、iとtotが同じであればkの違いによる計算の違いがなくなったことになる。
kの情報は必要なくなったので、削除しよう。

dp[i + 1][tot] += dp[i][tot]
dp[i + 1][tot + A[i]] += dp[i][tot] / 2

すると、dp[N][S] * 2^Nが答え。
自分の実装では初期値dp[0][0][0]=1ではなく、dp[0][0][0]=2^Nとして、答えをdp[N][S]としている。

int N, S, A[3010];
Comb<mint, 101010> com;
mint dp[3010][6010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
    rep(i, 0, N) cin >> A[i];

    dp[0][0] = mint(2) ^ N;
    rep(i, 0, N) rep(tot, 0, S + 1) {
        dp[i + 1][tot] += dp[i][tot];
        dp[i + 1][tot + A[i]] += dp[i][tot] / 2;
    }

    cout << dp[N][S] << endl;
}

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

hamayanhamayan's blog

Knapsack for All Subsets [AtCoder Beginner Contest 169 F]

前提知識

解説