AtCoder Typical DP Contest – A「コンテスト」その2

Pocket

「さあ、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] なんてされたら困っちゃうもんね」

「そう、順番を気にせず、添字の小さい方から計算していけばいい」

「じゃあ、こんな感じ?」

「完璧だね。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マスターじゃなかったのかー?」

「お兄ちゃんの意地悪ー!!」

Pocket

スポンサーリンク
レクタングル大
レクタングル大

シェアする

  • このエントリーをはてなブックマークに追加

フォローする