▲「さあ、DPだよ、お兄ちゃん! あたしにDPを教えろー」
■「さっきのあれは何だったんだ……? まあいいや、ループでテーブルを更新するDPの話だね。」
▲「AtCoder Typical DP Contest の A問題『コンテスト』を、さっきはメモ化再帰で解いたんだよね」
■「そうだね。ここから発展させよう。まず、サンプル1の {2, 3, 5} のパターンについて、メモの内容を実際に見てみよう」
▲「{2, 3, 5} だと、数字が 3 個で合計が 10 だから、メモは 4×11 だね」
■「そうだね。手計算で紙に書いてみよう。せっかくだから、memo[3][10] から考えてみよう」
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
0 | |||||||||||
1 | |||||||||||
2 | |||||||||||
3 |
▲「”3番目までで 10 が作れるか?” ってことだよね。まず、3番目の p[2] が 5 だから、”2番目までで5が作れるか、2番目までで10が作れるか” を確認したらいいんだよね」
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
0 | |||||||||||
1 | |||||||||||
2 | |||||||||||
3 |
■「いい感じ。でも、まだ分からないよね」
▲「えっと、2番目の p[1] が 3 だから、”1番目までで 2 か 5 か、7 か 10 が作れるか” になるんだね」
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
0 | |||||||||||
1 | |||||||||||
2 | |||||||||||
3 |
■「良いね。もう一押し!」
▲「1番目の p[0] が 2 だから、”0番目までで 0 か 2 か 3 か 5 か、5 か 7 か 8 か 10 が作れるか?” だね」
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
0 | |||||||||||
1 | |||||||||||
2 | |||||||||||
3 |
■「これで書けるようになったね」
▲「0番目までで作れるのは 0 だけだから、一番上の段は左端だけ〇で、他は全部×だよね」
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
0 | 〇 | × | × | × | × | × | × | ||||
1 | |||||||||||
2 | |||||||||||
3 |
■「そうだね。確認しなくていい部分は埋まらないね。これで、2段目の色付きの部分も埋められるね」
▲「memo[1][2] は、memo[0][0] が〇だから〇、他は全部×だね」
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
0 | 〇 | × | × | × | × | × | × | ||||
1 | 〇 | × | × | × | |||||||
2 | |||||||||||
3 |
■「この調子で残りも埋めよう」
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
0 | 〇 | × | × | × | × | × | × | ||||
1 | 〇 | × | × | × | |||||||
2 | 〇 | × | |||||||||
3 | 〇 |
▲「おお、書けたー」
■「書いてみて、どうだった?」
▲「うーん、プログラムだと簡単だけど、手計算は面倒だね。だって、1箇所埋めるのにいっぱい見ないといけないんだもん。上まで行ったら一気に埋まるけど、それまでは先が見えないというか」
■「じゃあ、上から埋めてみるのはどう?」
▲「確かに、上から埋めていくのは良さそうだね。でも、無駄な部分も埋めちゃうんじゃない?」
■「まあやってみようよ。とりあえず、最上段は左端 (0, 0) だけが〇で、他は×だよね」
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
0 | 〇 | × | × | × | × | × | × | × | × | × | × |
1 | |||||||||||
2 | |||||||||||
3 |
▲「2段目は、メモ化再帰と同じように埋めたら良いんだよね。1番目の p[0] は 2 だから、”真上が〇か、真上の2つ左が〇なら〇、それ以外は×” だね」
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
0 | 〇 | × | × | × | × | × | × | × | × | × | × |
1 | 〇 | × | 〇 | × | × | × | × | × | × | × | × |
2 | |||||||||||
3 |
■「そうだね。
memo[num][val] = memo[num-1][val] || memo[num-1][val-p[num-1]]
になるから、num=1 だと p[num-1] が 2 だから、
memo[1][val] = memo[0][val] || memo[0][val-2]
だね」
▲「なんかいきなりややこしい式が出てきたけど、そんな感じだよね。”0個目までで val か val-2 が作れたらOK” みたいな話だったもんね」
■「そうだね。この漸化式がDPで重要になるんだ」
▲「漸化式? って確か、数列のやつだよね」
■「そうそう、二次元配列も、添字が2つになった数列みたいなものだよ」
▲「なるほど、前の値から今の値を計算する統一ルールってことか……」
■「さあ、残りも埋めてしまおう」
▲「3段目は、p[2] が 3 だから、こんな感じかな」
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
0 | 〇 | × | × | × | × | × | × | × | × | × | × |
1 | 〇 | × | 〇 | × | × | × | × | × | × | × | × |
2 | 〇 | × | 〇 | 〇 | × | 〇 | × | × | × | × | × |
3 |
■「そうだね。(2, 0) から (3, 0) と (3, 3) が〇になって、(2, 2) から (3, 2) と (3, 5) が〇になるんだね」
▲「それで、4段目はこう!」
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
0 | 〇 | × | × | × | × | × | × | × | × | × | × |
1 | 〇 | × | 〇 | × | × | × | × | × | × | × | × |
2 | 〇 | × | 〇 | 〇 | × | 〇 | × | × | × | × | × |
3 | 〇 | × | 〇 | 〇 | × | 〇 | × | 〇 | 〇 | × | 〇 |
■「そうだね、(3, 5) は、(2, 0) と (2, 5) の両方から〇にされるね」
▲「うん、”または” にして、同じマスで管理してるから、二重カウントにならないんだね」
■「そうなんだけど、これをちょっと作り変えると、”ある値を作る方法は何通り?” という質問に答えられるようになるんだ」
▲「えーと、その場合は、(3, 5) は 2 になってほしいんだよね。作れないところは 0 で。じゃあ、こんな感じかな?」
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
3 | 1 | 0 | 1 | 1 | 0 | 2 | 0 | 1 | 1 | 0 | 1 |
■「その通り。”または” の部分で、数を足すようにすればいいんだね」
▲「とりあえず今回はこっちの表だね。これの、最後の段の〇を数えれば良いんだね」
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
0 | 〇 | × | × | × | × | × | × | × | × | × | × |
1 | 〇 | × | 〇 | × | × | × | × | × | × | × | × |
2 | 〇 | × | 〇 | 〇 | × | 〇 | × | × | × | × | × |
3 | 〇 | × | 〇 | 〇 | × | 〇 | × | 〇 | 〇 | × | 〇 |
■「そうだね。今回もちゃんと7個になってるね」
▲「更新はさっきの漸化式で良いの?」
■「うん。
memo[num][val] = memo[num-1][val] || memo[num-1][val-p[num-1]]
だね。ポイントは、右辺の添字が必ず左辺のものより小さいこと」
▲「添字が小さいと何が良いの?」
■「右辺の添字が小さいということは、添字の小さい順に見ていけば、ある memo[num][val] を計算したいとき、それに必要な値は必ず計算済みになるんだ」
▲「なるほどなるほど…… 確かに漸化式で a[n] = a[n-1] + a[n+1] なんてされたら困っちゃうもんね」
■「そう、順番を気にせず、添字の小さい方から計算していけばいい」
▲「じゃあ、こんな感じ?」
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include <iostream> #include <vector> using namespace std; #define repr(i,a,b) for(int i=a;i<b;i++) #define rep(i,n) for(int i=0;i<n;i++) int main(void) { int N; cin >> N; vector<int> p(N); int sum = 0; // memoの大きさのための合計 rep(i, N) { cin >> p[i]; sum += p[i]; } // メモを確保。はじめはfalseで埋める // memo[i][j] = i番目まででjを作れるか vector<vector<bool>> memo(N + 1, vector<bool>(sum + 1, false)); // 0番目までで作れるのは0だけ // memo[0][n]のn!=0の部分はすでにfalseが入っている memo[0][0] = true; repr(num, 1, N + 1) { rep(val, sum + 1) { if (val - p[num - 1] < 0) { // val-p[num-1]が負になる場合はmemo[num-1][val]だけチェック memo[num][val] = memo[num - 1][val]; } else { // num-1番目まででvalかval-p[num-1]が作れたらOK memo[num][val] = memo[num - 1][val] || memo[num - 1][val - p[num - 1]]; } } } // N番目までで作れる数の個数を計算 int ans = 0; rep(i, sum + 1) { if (memo[N][i])ans++; } cout << ans << endl; return 0; } |
■「完璧だね。repr(i, a, b) は、i=a から初めて b-1 で終わる、半開区間 [a,b) のループだね」
▲「うん。じゃあこれで提出しちゃおっか」
■「良いと思うよ」
▲「おー、AC! しかもさっきのメモ化再帰より速いしメモリ消費も少ない! なんで?」
■「メモリ消費は、再帰のオーバーヘッドが無くなったからだろうね。関数を呼びだす度にメモリを消費するから。深すぎる再帰はスタックオーバーフローにもつながるし」
▲「速いのは?」
■「ちゃんとは分からないけど、これも再帰呼び出しが関わってると思うよ。関数を呼び出すのは時間が掛かるみたいだから。メモリ空間上のアクセス順序とかも関係してるかもしれないけど……」
▲「なるほど、再帰は結構たいへんなんだね」
■「まあ、10万ぐらいの深い再帰でも大丈夫みたいだし、今はあまり気にしなくてもいいんじゃないかな」
▲「結局、何がどうなったらDPなの? 漸化式で表を逐次計算したら?」
■「そうだね、基本的にはテーブル(表)の値を、漸化式を使って計算していくものが多いね。でも、木DPとかもあるから、テーブルと言えるから微妙な場合もあるんだ。ちょっとこれを見てみて」
▲「うげ、なにこれ、気持ち悪い」
■「これが何か分かる?」
▲「何って、えーっと、丸が矢印でつながってるから、グラフ?」
■「そうだね。そのなかでも特に、有向グラフだね」
▲「矢印、つまり辺に向きがあるってことだね」
■「この辺のつながり方は、今回の問題のサンプルケース1に対応してるんだ」
▲「あ、ほんとだ。縦の並びが num で、横の並びが val だね。さっきまで書いてた表と同じ配置だね。それで、矢印の先を計算するのに、矢印の元の情報が必要ってことなんだね」
■「その通り。ある頂点の値を計算するためには、そこに入る辺の根元側の頂点について、計算済みでないといけない」
▲「で、このグラフがなんなの?」
■「このグラフをよく見てほしいんだけど、適当な頂点から矢印を辿っていったらどうなる?」
▲「えっと、何回かで絶対に一番下の段に行って、そこから進めなくなるね」
■「そう。ということはつまり、同じ場所にとどまったり、ぐるぐる回ったりできないよね?」
▲「そうだね、絶対に次の頂点に進まないといけないんなら、進むしかないね。元には戻れない」
■「つまり、このグラフは DAG だ」
▲「ダグ? なにそれ」
■「Directed Acyclic Graph 、日本語では “有向非巡回グラフ” とも言うけど、閉路の無い有向グラフのことだよ」
▲「へー。で、それがどうしたの?」
■「DAG には、順序をつけることができるんだ。”矢印の元の方が先よりも小さい” というルールに基づいて、相異なる値を割り振ることができる」
▲「意味わかんない」
■「こんな風に左上から右に向かって番号を割り振ると、必ず “矢印の元の方が先よりも小さい” という状態になるよね」
▲「なってるね。全部の矢印で値が増えてる」
■「DAG ならこれが必ずできるんだ。この数字の割り当てをトポロジカル順序と言ったりする。トポロジカル順序と言うときは、0から始まって 頂点数-1 で終わるように連続した整数を割り当てるかな」
▲「でもこれって一意じゃないよね? 例えば一番上の 0 と 1 が入れ替わってても大丈夫だよね?」
■「そう。トポロジカル順序は一意じゃないんだ。でも、とにかくこんな割り当てができる」
▲「まあ確かに、これができたらDAG、っていうのは絶対だよね、永遠に増え続けるのは無理なんだから、いつか終わりが来るってことで」
■「そうだね。DAG⇒トポロジカル順序が割り当て可能、というのも真なんだけど、今はそれはいいや」
▲「で、トポロジカル順序? が得られると何がうれしいの?」
■「このトポロジカル順に沿ってDPの更新をすることができる」
▲「えっと、あ、そういうことか。矢印の先を計算するのに、矢印の元の情報が必要だったけど、矢印の元の方は先よりもトポロジカル順序が小さいから、必ず計算済みなんだね」
■「そう。だから、DPっていうのは、DAGの頂点に持たせる情報を、トポロジカル順で計算していく、というものなんだ。だから、木でもできる。木は辺の向きを決めればDAGになるからね」
▲「なるほど…… なんかかえって難しくなってない?」
■「うーん、そうだね。とりあえずは、n次元配列のある値を、添字の小さいものだけで計算する漸化式があれば、ループで全部計算できる、と考えておけばいいかな」
▲「ふー、疲れたー」
■「同じ問題を2回解いたからね」
▲「えっと、DPの基本は、こんな感じ?
dp[i][j] = (dp[i-1][j]とかdp[i][j-1]とか、添字が小さいものだけの式)
みたいな漸化式が、すべての (i, j) で成り立てばいいのかな?」
■「基本はそうだね。でも、2次元に限らないよ。1次元や3次元もあるし、場合によっては6次元なんてのも……」
▲「うわぁ、大変そう…… それで、計算量はDPテーブル(DPに用いる表)の大きさ?」
■「いや、(DPテーブルの大きさ)×(1回の更新の計算量)だね。dp[i][j]の計算にdp[i-1][0]~dp[i-1][j]まで全部見る、とかになると、1回の更新にも線形オーダーがかかってくるんだ。」
▲「なるほど、そっちの計算量も注意しないといけないね」
■「難しい問題になると、DPの計算量を二分探索やセグメント木で落とす問題が出てくるね。」
▲「それは追々ということで……」
■「そうだね。とりあえず、ABCのC問題の過去問とか、TDPCのB問題とかを考えてみればいいんじゃないかな」
▲「ありがとうお兄ちゃん! これであたしもDPマスターだー」
■「さすがにDPマスターは早すぎるんじゃないか…… DPマスターになりたいなぁ」
▲「ちょっとお兄ちゃーん!! TDPC のB問題が分かんないんだけどー!!」
■「あれー、DPマスターじゃなかったのかー?」
▲「お兄ちゃんの意地悪ー!!」