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個ずれるし、そういうのもあるんだね」

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

#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
 
vector<int> p;	// canMake()で使うのでグローバル変数にする
 
// num番目（p[num-1]まで）でvalを作れるか
bool canMake(int num, int val) {
	// num-1番目までで、val-p[num-1]かvalが作れたらOK
	return canMake(num-1, val-p[num-1]) || canMake(num-1, val);
}
 
int main(void) {
	int N;
	cin >> N;
	p = vector<int>(N);
	
	rep(i, N) cin >> p[i];
 
	// 例えば「Xを作れるか？　と聞かれたら」
	int X;
	cin >> X;
 
	if (canMake(N, X))cout << "Yes" << endl;
	else cout << "No" << endl;
 
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)

vector<int> p; // canMake()で使うのでグローバル変数にする

// num番目（p[num-1]まで）でvalを作れるか

bool canMake(int num, int val) {

// num-1番目までで、val-p[num-1]かvalが作れたらOK

return canMake(num-1, val-p[num-1]) || canMake(num-1, val);

}

int main(void) {

int N;

cin >> N;

p = vector<int>(N);

rep(i, N) cin >> p[i];

// 例えば「Xを作れるか？　と聞かれたら」

int X;

cin >> X;

if (canMake(N, X))cout << "Yes" << endl;

else cout << "No" << endl;

return 0;

}

▲「こんな感じ？」

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

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

#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
 
vector<int> p;	// canMake()で使うのでグローバル変数にする
 
// num番目（p[num-1]まで）でvalを作れるか
bool canMake(int num, int val) {
	if (num == 0) {
		// 0番目までで作れるのは0だけ！
		return val == 0;
	}
	// num-1番目までで、val-p[num-1]かvalが作れたらOK
	return canMake(num-1, val-p[num-1]) || canMake(num-1, val);
}
 
int main(void) {
	int N;
	cin >> N;
	p = vector<int>(N);
	
	rep(i, N) cin >> p[i];
 
	// 例えば「Xを作れるか？　と聞かれたら」
	int X;
	cin >> X;
 
	if (canMake(N, X))cout << "Yes" << endl;
	else cout << "No" << endl;
 
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)

vector<int> p; // canMake()で使うのでグローバル変数にする

// num番目（p[num-1]まで）でvalを作れるか

bool canMake(int num, int val) {

if (num == 0) {

// 0番目までで作れるのは0だけ！

return val == 0;

}

// num-1番目までで、val-p[num-1]かvalが作れたらOK

return canMake(num-1, val-p[num-1]) || canMake(num-1, val);

}

int main(void) {

int N;

cin >> N;

p = vector<int>(N);

rep(i, N) cin >> p[i];

// 例えば「Xを作れるか？　と聞かれたら」

int X;

cin >> X;

if (canMake(N, X))cout << "Yes" << endl;

else cout << "No" << endl;

return 0;

}

■「そうだね。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、みたいな」

■「それでいこう」

#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
 
vector<int> p;	// canMake()で使うのでグローバル変数にする
vector<vector<int>> memo;
 
// num番目（p[num-1]まで）でvalを作れるか
// valは必ず0以上
bool canMake(int num, int val) {
	// メモ済ならmemoの内容を出力（1ならtrue）
	if (memo[num][val] != -1) return memo[num][val] == 1;
 
	if (num == 0) {
		// 0番目までで作れるのは0だけ！
		return val == 0;
	}
	// num-1番目までで、val-p[num-1]かvalが作れたらOK
	if (val - p[num - 1] < 0) {
		// val-p[num-1]が負になる場合は、valのみチェック
		if (canMake(num - 1, val)) {
			// メモに記録して出力
			memo[num][val] = 1;
			return true;
		}
		else {
			// メモに記録して出力
			memo[num][val] = 0;
			return false;
		}
	}
	else {
		if (canMake(num - 1, val - p[num - 1]) || canMake(num - 1, val)) {
			// メモに記録して出力
			memo[num][val] = 1;
			return true;
		}
		else {
			// メモに記録して出力
			memo[num][val] = 0;
			return false;
		}
	}
}
 
int main(void) {
	int N;
	cin >> N;
	p = vector<int>(N);
	int sum = 0;	// memoの大きさのための合計
	rep(i, N) {
		cin >> p[i];
		sum += p[i];
	}
	// メモを確保。はじめは-1で埋める
	memo = vector<vector<int>>(N + 1, vector<int>(sum + 1, -1));
 
	// 例えば「Xを作れるか？　と聞かれたら」
	int X;
	cin >> X;
 
	if (canMake(N, X))cout << "Yes" << endl;
	else cout << "No" << endl;
 
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)

vector<int> p; // canMake()で使うのでグローバル変数にする

vector<vector<int>> memo;

// num番目（p[num-1]まで）でvalを作れるか

// valは必ず0以上

bool canMake(int num, int val) {

// メモ済ならmemoの内容を出力（1ならtrue）

if (memo[num][val] != -1) return memo[num][val] == 1;

if (num == 0) {

// 0番目までで作れるのは0だけ！

return val == 0;

}

// num-1番目までで、val-p[num-1]かvalが作れたらOK

if (val - p[num - 1] < 0) {

// val-p[num-1]が負になる場合は、valのみチェック

if (canMake(num - 1, val)) {

// メモに記録して出力

memo[num][val] = 1;

return true;

}

else {

// メモに記録して出力

memo[num][val] = 0;

return false;

}

else {

if (canMake(num - 1, val - p[num - 1]) || canMake(num - 1, val)) {

// メモに記録して出力

memo[num][val] = 1;

return true;

}

else {

// メモに記録して出力

memo[num][val] = 0;

return false;

}

int main(void) {

int N;

cin >> N;

p = vector<int>(N);

int sum = 0; // memoの大きさのための合計

rep(i, N) {

cin >> p[i];

sum += p[i];

}

// メモを確保。はじめは-1で埋める

memo = vector<vector<int>>(N + 1, vector<int>(sum + 1, -1));

// 例えば「Xを作れるか？　と聞かれたら」

int X;

cin >> X;

if (canMake(N, X))cout << "Yes" << endl;

else cout << "No" << endl;

return 0;

}

▲「これでどう？」

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

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

■「うん」

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

#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
 
vector<int> p;	// canMake()で使うのでグローバル変数にする
vector<vector<int>> memo;
 
// num番目（p[num-1]まで）でvalを作れるか
// valは必ず0以上
bool canMake(int num, int val) {
	// メモ済ならmemoの内容を出力（1ならtrue）
	if (memo[num][val] != -1) return memo[num][val] == 1;
 
	if (num == 0) {
		// 0番目までで作れるのは0だけ！
		return val == 0;
	}
	// num-1番目までで、val-p[num-1]かvalが作れたらOK
	if (val - p[num - 1] < 0) {
		// val-p[num-1]が負になる場合は、valのみチェック
		if (canMake(num - 1, val)) {
			// メモに記録して出力
			memo[num][val] = 1;
			return true;
		}
		else {
			// メモに記録して出力
			memo[num][val] = 0;
			return false;
		}
	}
	else {
		if (canMake(num - 1, val - p[num - 1]) || canMake(num - 1, val)) {
			// メモに記録して出力
			memo[num][val] = 1;
			return true;
		}
		else {
			// メモに記録して出力
			memo[num][val] = 0;
			return false;
		}
	}
}
 
int main(void) {
	int N;
	cin >> N;
	p = vector<int>(N);
	int sum = 0;	// memoの大きさのための合計
	rep(i, N) {
		cin >> p[i];
		sum += p[i];
	}
	// メモを確保。はじめは-1で埋める
	memo = vector<vector<int>>(N + 1, vector<int>(sum + 1, -1));
 
	int ans = 0;	// 作れる数の個数
	// 0からsumまで全部試す
	rep(i, sum + 1) {
		if (canMake(N, i))ans++;
	}
 
	cout << ans << endl;
 
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)

vector<int> p; // canMake()で使うのでグローバル変数にする

vector<vector<int>> memo;

// num番目（p[num-1]まで）でvalを作れるか

// valは必ず0以上

bool canMake(int num, int val) {

// メモ済ならmemoの内容を出力（1ならtrue）

if (memo[num][val] != -1) return memo[num][val] == 1;

if (num == 0) {

// 0番目までで作れるのは0だけ！

return val == 0;

}

// num-1番目までで、val-p[num-1]かvalが作れたらOK

if (val - p[num - 1] < 0) {

// val-p[num-1]が負になる場合は、valのみチェック

if (canMake(num - 1, val)) {

// メモに記録して出力

memo[num][val] = 1;

return true;

}

else {

// メモに記録して出力

memo[num][val] = 0;

return false;

}

else {

if (canMake(num - 1, val - p[num - 1]) || canMake(num - 1, val)) {

// メモに記録して出力

memo[num][val] = 1;

return true;

}

else {

// メモに記録して出力

memo[num][val] = 0;

return false;

}

int main(void) {

int N;

cin >> N;

p = vector<int>(N);

int sum = 0; // memoの大きさのための合計

rep(i, N) {

cin >> p[i];

sum += p[i];

}

// メモを確保。はじめは-1で埋める

memo = vector<vector<int>>(N + 1, vector<int>(sum + 1, -1));

int ans = 0; // 作れる数の個数

// 0からsumまで全部試す

rep(i, sum + 1) {

if (canMake(N, i))ans++;

}

cout << ans << endl;

return 0;

}

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

▲「えっと、一回の 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