Typical DP Contest

お知らせ

• モーダルが現れました。(9/01 1:00)
• 順位表が一部正しく表示されていません。原因を調査中です。(9/01 0:12)
• 9 月になりました。あけましておめでとうございます。コンテストは残り一時間です。現在とかれていない問題は Q のみです。(9/01 00:00)
• リジャッジを行いました。(8/31 23:24)
• P 問題のリジャッジを行います。(8/31 23:17)
• 半分経過しました。現在とかれていない問題は P, Q, R の三問です。(8/31 22:30)
• リジャッジを行いました。(8/31 21:04)
• H 問題に不正な入力がありました。申し訳ございません。リジャッジを行います。(8/31 21:00)
• 質問に回答しています。質問も定期的にご確認ください。(8/31 20:44)
• D 言語は使用できないようです。(8/31 20:32)
• ペナルティタイムは 5 分になりました。(8/31 20:14)
• コンテストを開始しました。(8/31 20:00)
• お知らせがある可能性があるので、定期的にここを見にきてください。(8/31 19:50)
• 配点を公開しました。(8/31 16:09)
• 出力の末尾には、必ず改行を出力してください。(8/24 12:55)
• 何か変なことが起きた場合、ここに書かれます。(8/24 12:55)

このコンテストについて

このコンテストは動的計画法 (Dynamic Programming, DP) の練習をすることを目的として作られています。

DP とは

たとえば、次の問題を考えてみてください。

N (1 ≤ N ≤ 1000) 匹のリスが一列に並んでいる。左から i 匹目のリスには、整数 a_i が書かれている。この中から何匹かのリスにぶどうをのせ、ぶどうの乗ったリスにかかれた整数が左から昇順に並んでいるようにしたい。最大何匹のリスにぶどうを乗せられるか。

ぶどうの乗ったリスのうち、最も右のリスが i 番目であるときのぶどうの乗ったリスの引数の最大値を dp_i とおくと、漸化式

dp_i = max_{1 ≤ j < i, a_j < a_i} {dp_j} + 1

が成り立つことが分かります。このことを利用して上の問題を C++ 言語で解くと、

int a[1010];
int dp[1010];

int main(void){
	int N,i,j;
	
	cin >> N;
	for(i=0;i<N;i++) cin >> a[i];
	
	for(i=0;i<N;i++){
		dp[i] = 1;
		for(j=0;j<i;j++) if(a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);
	}
	
	int ans = 0;
	for(i=0;i<N;i++) ans = max(ans, dp[i]);
	cout << ans << endl;
	
	return 0;
}

となります。 このように、漸化式を用いた手法を DP といいます。

ルール

• 5 時間 20 問です。
• 解いた問題の配点の合計が得点となります。
• 同点の場合は (最後に得点が増えた時間) + (5 min) * (WA の回数) が小さいほうを上位とします。

配点

100 点満点です。

問題	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T
配点	2	3	4	4	4	4	4	5	5	5	5	5	5	5	6	6	6	7	7	8

その他

• AtCoder でサポートされている言語はすべて使用できます。
• 出題される問題はすべて (他のコンテストで使用できないほど) 典型的な DP の問題です。
• 難易度は TopCoder SRM d2 hard 程度のものが多いです。
• 配点の高いものは低いものより実装量が多い傾向があります (ただしすべての問題に当てはまるとは限りません)。
• DP に慣れている人は満点を目指してください。問題数が多いので比較的大変だと思います。