ABC169-F "Knapsack for All Subsets" DPの遷移式について
本番中は解けなかったのですが、苦手なDPに少しずつ慣れてきたこともあり、O(N^2 * S) のTLE解までは書くことができました（それでも十分嬉しい）。
解説を読み、O(N*S) の解法が理解できて解説ACできたので、自分の場合のDPの発想手順と、想定解のDP遷移式を解説します。
概要
長さNの正整数列 A1, A2, ..., AN と 正の整数Sが与えられる。
そこから、数列Aの部分集合であって和がSとなるものの個数を求める…… なら分かりやすいが、今回は「数列Aの部分集合Tの部分集合Uであって和がSとなるものの個数を求める」という問題。
DPを発想するまで
いやいやいや部分集合の部分集合で？？？ 和がS？？？ なに？？？ となって3分くらい頭がフリーズしました。
ちょっと落ち着いた頃、Uは、Aの部分集合の部分集合と言うと分かりにくいが、まあとにかくAの部分集合であることには違いない、と考え始めました。
すると、難しいところは置いておいて、とにかく「部分和問題」という典型の一種であり、DPで解ける可能性が高いのでは、となりました。
（ナップサックという問題タイトルがヒントになっています。F問題に挑戦する人だと大体ナップサックDPを書いたことがあるんだと思いますが、自分は名前だけ知っていて、概要は知らない状態でした。とにかく検索すれば見つかります）
O(N^2 * S) の TLE解
（一応載せてみましたが、TLE解なので読まなくていいです）
さて、DPを考えてみます。（残念ながらこれはTLEします）
求めたいのは条件を満たす部分集合Uの数なので、それをDP配列に入れる値にすることにします。
Tのことは今は考えるのを一旦停止しています。
DP[i][j][k] := 数列の左端から Ai までのうち j 個の数を使って作る、和 k となる部分集合の数
※どうせTLE解なので、遷移式は省略します。気になる場合は提出コードを見てください。
このDPを求められれば、最終的に、DP[N-1][1][S] ～ DP[N-1][N][S] の部分に、「数を1個～N個使って和がSとなる部分集合の数」が入ります。
これはそのまま答えにはなりませんが、ここに計算を加えると答えを出すことができます。
例えば数列Aの要素数が5(A0, A1, A2, A3, A4)で、和がSとなるある部分集合Uに使った数の個数が3(A0, A2, A4)だったとします。
この部分集合Uが属する部分集合Tは、(A0, A2, A4), (A0, A2, A4, A1), (A0, A2, A4, A3), (A0, A2, A4, A1, A3) の4種類です。
部分集合Tのパターンをよく見ると、これは Uに選ばれなかった各要素（今回ならA1, A3）それぞれにつき、「Tに入れる」「Tに入れない」の2パターンがあるので、
部分集合U の要素数 が j だった時、それが属する部分集合 T の種類は 2^(N-j) 種類 と求められるわけです。
これを使うと、
(答え) = Σ(j:1~N) dp[N-1][j][S] * 2^(N-j) % MOD となります。
とはいえTLEなので、頑張ってDPの次元を落とす（ [ ] の数を減らす）ことになります。
次元の落とし方
さて、ここからどうやって [ ] を減らすか……
自分は残念ながら解説を読んで理解したのですが、恐らく考え方はこうです。
とにかく減らす対象は[i]か[j]か[k]かしかない、つまり「何個目までとったか」をなくすか、「何個とったか」をなくすか、「和がいくつになったか」をなくすかの3種類しかない。
そう考えてみると、「何個目までとったか」をなくしてしまうと、次にどれを取るか選ぶのに毎回O(N)かかってどうしようもないですし、「和がいくつになったか」をなくしてしまったら、どう考えてもにっちもさっちも行きません。
すると、「何個目までとったか」をなくすしかありません。
さて、そうすると先程のTLE解で最後に行った「2^(N-j)をかけて答えを出す」ができないので、答えそのものをDPに入れないといけないことになります。
ここで、若干放り投げ気味だった「部分集合T」と向き合うことになります。
今回の「答え（個数）」は何か？
実は今回の難しいポイントは、問題文の「答え」が何のことか、がわかりにくいことだったのじゃないかと思っています。
集合1~Nの空でない部分集合Tとして考えられる全てについてのf(T)の和…… などと言われると「何やねん！」とシャーペンを投げたくなりますが、
ゆっくり考えると、「『和がSとなるようなAの部分集合U』と『 U を含むような より大きい部分集合T』の組合せの数」と言い換えられます。
この「組合せ」という考え方を利用すると、遷移式が理解しやすくなると思います。
次元を落としたDP
それでは、O(N*S)のDPの解説に入ります。
TLE解では DP[i][j][k] としましたが、そこから「何個とったか」つまり [j] がなくなったので、DPはこうなります。
DP[i][k] := 数列の左端から Ai までのうちから、自由な個数の数を選んでつくる、『和 k となる部分集合U』と『Uを含むようなより大きい部分集合T』の組合せの数
このようにDPを組んだとき、まずは下の図のようになることを、よく考えて理解してください。
これが理解できれば、遷移式の理解もすぐです。
ちなみに、DP[0][2以降] = 0 です。そのようなUの数は0だからです。
恐らく「つまずきポイント」となるのは、数が「1」ではなくいきなり「2」から始まることだと思いますが、これは、Uの種類が1つであっても、それを含むようなTの数は複数あるからです。
このように、Uの種類とTの種類の増え方の違いを意識することがポイントです。
遷移式
以下の図のようになります。
いや、なんか図がグッチャグチャになってしまいましたが……。
DP[i-1][k-Ai] から、DP[i][k] にいく遷移は、UもTも「新しくAiを加える」の1パターンなので分かりやすいのですが、「×2」のところが難しいポイントだと思います。
これはともかく具体例を見ていただくしかないですが、
U には何も入れていないのに、T のパターンが2倍になる！ という遷移になっています。
なぜこうなるか？ というと、AiをUに入れなくても、Tには入れることができるし、入れないこともできることが理由です。
T:{} -> {3} と {1} -> {1, 3} がTにAiを入れた遷移 （これで ×1）
T:{} -> {} と {1} -> {1} がTにAiを入れない遷移（これで ×1）
この2種類の遷移があるため、「×2」が発生したということになります！
どうでしょうか？
分からないところがあれば、ぜひご質問ください。
