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

Pocket

「ねえ」

「ん? どうした?」

「お兄ちゃんに勧められて “競技プログラミング” をやってるんだけど、”動的計画法“っていうのがよく分かんない」

「ああ、確かに、初めのうちは難しいな。僕だって難しいのは分からないし」

「なんか良い勉強法とか無いの?」

「それなら、AtCoder Typical DP Contest を解いてみたら?」

「それ、調べたら出てきたから解こうと思ったんだけど、A問題から分からなくて……」

「確かにあれ、いきなり結構難しいもんなあ。教育的で良い問題だけど」

「お兄ちゃんはどこまで解いたの?」

「確かD問題までじゃなかったかな……。もっと解かないといけないのは分かってるんだけどね」

「じゃあA問題教えてよ!」

「いいよ。僕の復習にもなるし」

Typical DP Contest A『コンテスト』……っと」

「この問題だね。コンテストの配点リストが与えられるので、合計得点としてあり得る点数は何通りか」

「結局、もらった数列のうちいくつかを使ってできる和が何通りあるか、ってことだよね?」

「その通り。でも、愚直にやると 2^N 通りになっちゃう」

「使うか使わないかだもんね」

「そう。でも、今回は N?100,p[i]?100 だから、多項式オーダーなら結構自由だね」

「自由と言われましても……」

「問題を変えてみよう。『この中からいくつか選んで和を X にできますか?』という判定問題ならどうかな」

「んー、なるほど、それができたら、全部試して数えたらいいんだね。1 は? 2 は? って」

「そうだね。でもとりあえずは1つだけ質問される問題として考えよう」

「ちょっと考えてみる。うーん……」

「お兄ちゃん! 分かんない!

「そうか。じゃあヒントを出そうか。とりあえず、簡単な例で考えよう。{2, 3, 4, 6} から、11 を作れるか? を考えよう」

「作れるね。2 と 3 と 6 で」

「どうやって考えた?」

「どうやってって、なんか分かるじゃん」

「まあそうなんだけど、段階とか無かった?」

「うーん、6があるから、5 が作れるかなーと思ってみたら、2 と 3 があったからいけるーって」

「お、良いね。ほぼ答えだよ」

「え!? どういうこと!?」

「ちょっと意地悪な問題だけど、{?, ?, ?, 6} から、11 を作れるか? って聞かれると、どう?」

「どうって…… そんなの、? が分からないと分からないよ」

「そうだね、でも、” ? がどうだったら作れる” みたいな条件は考えられるんじゃない? さっきの考え方みたいにさ」

「さっきの考え方? あ、” {?, ?, ?} で 5 が作れたら作れる” ってこと?」

「良いんだけど惜しい。{?, ?, ?} で 5 が作れなくても、11 を作れる場合があるよ」

「そうだね、{?, ?, ?} だけで 11 が作れたら、6 なんて関係無いんだね」

「そうそう。だから条件は、”{?, ?, ?} で 5 か 11 が作れたら作れる” ということだね」

「それで?」

「次は,”{?, ?, 4} で 5 が作れるか?” と “{?, ?, 4} で 11 が作れるか?” を調べる必要がある」

「? が 1 つオープンになったね」

「そうだね。これも {?, ?} の条件で説明できる?」

「えっと、前のが “{?, ?} で 1 か 5 が作れたら作れる” で、後ろのが “{?, ?} で 7 か 11 が作れたら作れる” かな?」

「正解。もともと “{?, ?, 4} で 5 か 11 が作れたら作れる” だったから、この2つが”または”でつながるんだね」

「じゃあ、”{?, ?} で 1 か 5 か 7 か 11 が作れたらOK” ってことになるのかな?」

「その通り。この操作の繰り返しで、最終的には “{2} で 1 か 2 は作れるか?” みたいな問いになって、判定できるようになる」

「なるほど…… ってこれじゃあ毎回条件が2倍になるから、最後は 2^N 通りになるんじゃないの!?」

「それをうまく回避する方法があるんだ。とりあえず、これを再帰関数で実装してみよう」

「”これを”って、どれを?」

「ああ、ちょっと説明不足だったね。今までの問いは、全部 “前から k 番目までで X を作れるか?” という問いだった」

「そうだね。{?, ?, …, ?} っていうのが “前から k 番目まで” だよね」

「うん。だから、それを判定する関数を作る」

「えっと、bool canMake(int num, int val) で、”num 番目までで val を作れたら true、作れなかったら false” ってこと?」

「良いね。そのままコードに書けそうだね」

「最初の数字って、0番目? 1番目?」

「ああ、それは1番目にしよう」

「なんで? プログラミングって0始まりが普通なんじゃないの?」

「確かに0-indexed(0始まり)が多いけど、これは動的計画法のテクニックなんだ。後々便利になるよ」

「ふーん、まあ、累積和も添字が1個ずれるし、そういうのもあるんだね」

「そうそう。じゃあ書いてみよう」

「こんな感じ?」

「良い感じだけど、これじゃあ終わらないよ」

「あっ、終了条件忘れてた。これでどうだ」

「そうだね。num==0 の場合の処理もちゃんと書けてるね」

「やった! num が 0 だと、”0番目まで” になるけど、0番目なんて無いもんね」

「でもこれだと O(2^N) だよね?」

「そうだよ! ここからどうするの?」

「このcanMake()に与えられる引数って、何種類ある?」

「引数の種類? えーと、num は 0 から N までの N+1 通りでしょ、val は 0 から X まで? あれ? そういえばこれって val に負の値がくることもある?」

「今はあり得るね。でも、val が負の場合は再帰呼び出しをしないようにすれば大丈夫」

「なるほど、となると、num が N+1 通り、val が X+1 通りだから、(N+1)(X+1) 通り?」

「正解。これって、2^N と比べてどう?」

「あ! すごく小さい!」

「ということは、どういうこと?」

「えーっと、同じ引数ペアで呼び出されることがあるってことだよね。鳩ノ巣原理!」

「そうだね。その場合、過去の出力を覚えていれば、計算を省略できるよね?」

「確かに! 全部覚えても大した量じゃないもんね」

「じゃあ、メモを作ろう」

「メモ? 過去の引数と出力を記録するメモってこと?」

「そう。今回は二次元配列(二次元vector)で作れるよね」

「vector<vector<bool>>で、memo[num][val] = canMake(num, val)の出力、って感じ?」

「良い感じだけど、それだと “その引数で実行済みか?” が分からないよね」

「あー、確かに。”まだ記録がありません” っていうのも必要なんだね。じゃあ vector<vector<int>>の方が良いかな。true なら 1 、false なら 0 、まだやってないなら -1、みたいな」

「それでいこう」

「これでどう?」

「うん、大丈夫そうだね。このまま、元の問題を解くプログラムに変えてみようか」

「0 から p[i] の合計まで全部試して、作れる数の個数を数えるの?」

「うん」

「えーっと、こんな感じ?」

「いいね。このアルゴリズムの計算量は分かる?」

「えっと、一回の canMake() のオーダーがいくつだろ。メモにある場合と無い場合があるからなあ……」

「メモに無い場合にメモする作業は最大で何回行われるかな?」

「メモ全部埋めちゃえば、そこから先は全部メモにあることになるから、メモの容量分しか記録は行われないよね? じゃあ、(N+1)*(sum+1) かな?」

「そうだね。記録済みの部分を見ることも、実は各1回ずつしか無いんだ。」

「なんで?」

「ちょっとややこしいけど、(num, val) の引数ペアで canMake() が呼ばれるのは、(num+1, val) か (num+1, val+p[num]) のどちらかの canMake() からだけなんだ。まあこれは気が向いたら考えてみて」

「ふーん。まあ、メモ済みの部分を見るパターンは、メモしてないところの計算をするよりは速いっぽいもんね」

「じゃあ、これで提出してみようか」

「え、いやいや、今のはあくまで1回の canMake() の計算量でしょ? (sum+1) 回実行するんだから、全体の計算量は O(N*sum^2) になるんじゃないの? 今回は N?100, p?100 だから sum?10^4 で、全体は N*sum^2?10^10 程度になるんじゃないの?」

「ああ、それは違うんだ。メモは使いまわすからね」

「メモは使いまわす? ……あ、だんだんメモ済みの部分が増えていって、最後の方はほとんど探索せずに答えが分かるんだ」

「そうそう。だから全体でも O(N*sum) で、10^6 程度なので余裕で間に合うと思うよ」

「へー、メモすごいね」

「じゃあ、提出してみよう」

「よし、提出するぞー。ACしてくれ……」

「おお! ACだー! 2点! ひっく! でも早い! 4ミリ秒!」

「TDPC は正式なコンテストじゃないからね。配点は全部1桁だね。計算量は100万程度だからかなり高速だね」

「いやー、解けて良かった。ありがとうお兄ちゃん!」

「いやいや、これで終わりじゃないよ?」

「へ? これが動的計画法なんじゃないの?」

「今やったのはメモ化再帰というテクニック。動的計画法の一種とも言えるけど、テーブルをループで埋めていくタイプのDPもやっておきたい」

「よし! じゃあやろう!」

「うん、やる気だね」

「でも」

「ん?」

「一旦終わっておいた方が良くない? 長さ的に」

「長さって、何の?」

「読み込みに時間かかってもアレだからね。それではみなさん、また来週~」

「読み込みって何の!? みなさんって誰!?」

Pocket

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

シェアする

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

フォローする

コメント

  1. […] ▲「AtCoder Typical DP Contest の A問題『コンテスト』を、さっきはメモ化再帰で解いたんだよね」 […]

  2. […] ▲「うん。この前お兄ちゃんにDPを教えてもらったけど、なんか A 問題と全然違うんだけど」 […]