第11回日本情報オリンピック本選参加記

結果は220点でBランクでした。問1でバグ死というありえない落ち方をして、正直現実の出来事として捉えられていませんが、
これからゆっくりと現実と向き合っていこうと思います(大袈裟)。

初日 Practice前

自作のきゅうり帽(右写真)を持参していった。かぶってkyuridenamidaをオリセンで出迎えたら卒倒していた。
これまでインターネット上で名前を知っていてかつ今回はじめて顔を認識した人だと、li_sakuさんとかDEGwerさんとかとも合流する。

初日 Practice

今回は時間通りに受付が開始していてよかった。Practiceでは全員で簡単な問題をSegment Treeで解いたりショートコーディングをしたり、みんなできゅうりに群らがって害活をしたりしていた。
後からJMO組が合流。tozangezanがPracticeの問題を覚えていてパナかった。

hogloid君は去年の雰囲気はそのままに自信満々な感じ成長していて、tozangezanとのやりとりがとても面白かった。

あと伊藤さんに「(きゅうり帽を見て)それ本選で被るのかい?」とか言われました。

初日 講演・夕食・宿泊

NTTデータの人の講演は、去年より技術的な話になっていて興味深く、非常に面白かった。
夕食時の隣はroxion1377(合宿おめでとうございます)と、favdragon_reanさんだった。たしかにreanさんは竜という感じの人だった。自己紹介では今回の目標と自分の趣味について語った。
今年はしっかり宿泊したので悲しい思いをしないですんだ。きゅうり帽をrngさんが結構気に入ってくれてよかった。
夜はkyuridenamidaとtozangezanの睡眠時間削りレースが白熱していた。

2日目 本選

前述のように問1のバグがどうしても取れなくて、定義通り(O(N^3)の解法と)の解の出力と、最大8ケタまで総当たりで比較するコードを書いたりしたがデバッグできなかった。解説聞いたが想定解すぎて本当に叫びたい。20点。
問2は最初ただのLCSを書いてしまったが考え直したら意外にも解けた。100点。
問3も解けた筈なのだが何故かWAしており、結果を見たら90点とかいう気持ち悪すぎる感じだった。semiexpさんの後の話をちょろっと聞いた感じだとやっぱり正しい解法らしく何がいけないんだろう。
問4は最後の悪あがきとして愚直解で10点とりました。
問5は読んでいない。

今年から終了直後に暫定ではあれ得点を紙でくれるようになった。進化している。

まあiwiさんのサインアリ本に貰ったしこれだけでも成果だと思う事にしよう。

まとめ

正直全く触れていない時期もあったとは言え、1年半にわたる目標を失なったので、正直今何も考えられない状態ですが、情報オリンピックを通じて得られた物は決して小さくないと思うので、それらを活かせるよう大学以降でもがんばっていこうと思いました。

一応解のソースを一番最後においておきます。僕はもう怖くて見直ししたくないので誰か見てください(他力本願)
追記2012/2/14 問1違うソース貼ってたので貼りなおした

再追記

JAPLJ先生が間違い箇所を探してくれて、現実を認識できて正気に戻れるかと思いきや一段と気が狂いそうです。
このミスはなしだろぉぉぉぉぉぉ…。
という訳で、同じ悲しいミスをしない為にこのコードのデバッグを以降JOIに出られる諸氏への宿題とします。

問1

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

class JOI {
public:
	char c;
	int n;
	JOI(char c, int n) : c(c), n(n) {}
};

int smart(const char *S)
{
	vector<JOI> jois;
	const int len = strlen(S);
	jois.reserve(len);
	char last = -1, cnt = 1;
	for (int i = 0; i < len; ++i) {
		if (S[i] != last) {
			if (last != -1)
				jois.push_back(JOI(last, cnt));
			cnt = 1;
			last = S[i];
		} else {
			cnt++;
		}
	}
	if (last != -1)
		jois.push_back(JOI(last, cnt));

	int res = 0;
	for (int i = 0, l = jois.size() - 2; i < l; ++i) {
		if (jois[i].c == 'J' && jois[i + 1].c == 'O' && jois[i + 2].c == 'I' &&
			jois[i].n >= jois[i + 1].n && jois[i + 1].n <= jois[i + 2].n) {
			res = max(res, jois[i + 1].n);
		}
	}
	return res;
}

int main()
{
	char S[1000002];
	scanf("%s\n", S);

	const int res = smart(S);
	printf("%d\n", res);

	return 0;
}

問2

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int lenA, lenB;
	scanf("%d %d\n", &lenA, &lenB);
	vector<int> A(lenA, 0), B(lenB, 0);
	for (int i = 0; i < A.size(); ++i) {
		int t;
		scanf("%d", &t);
		A[i] = t - 1;
	}
	for (int i = 0; i < B.size(); ++i) {
		int t;
		scanf("%d", &t);
		B[i] = t - 1;
	}

	vector<vector<int> > same(1000);
	for (int i = 0; i < A.size(); ++i) {
		same[A[i]].push_back(i);
	}
	for (int i = 0; i < same.size(); ++i) {
		sort(same[i].begin(), same[i].end());
	}

	int res = 0;
	for (int i = 0; i < B.size(); ++i) {
		if (same[B[i]].empty())
			continue;
		int cur = same[B[i]][0], cnt = 1;
		for (int j = i + 1; j < B.size(); ++j) {
			if (same[B[j]].empty())
				break;
			vector<int>::iterator it =
				upper_bound(same[B[j]].begin(), same[B[j]].end(), cur);
			if (it == same[B[j]].end())
				break;
			cur = *it;
			cnt++;
		}
		res = max(res, cnt);
	}
	printf("%d\n", res);
	return 0;
}

問3

#include <cstdio>
#include <vector>
using namespace std;

int main()
{
	int N, T, S;
	scanf("%d %d %d\n", &N, &T, &S);
	vector<int> A(N), B(N);
	for (int i = 0; i < N; ++i)
		scanf("%d %d\n", &A[i], &B[i]);
	vector<vector<int> > dp(N, vector<int>(T + 1, 0));
	if (S == 0) {
		for (int i = B[0]; i <= T; ++i) {
			dp[0][i] = A[0];
		}
	} else {
		for (int i = B[0]; i <= S; ++i) {
			dp[0][i] = A[0];
		}
	}
	for (int i = 1; i < N; ++i) {
		for (int j = 0; j <= T; ++j) {
			int& cur = dp[i][j];
			cur = dp[i - 1][j];
			if (j >= B[i]) {
				if (j - B[i] < S && S < j) {
					cur = max(cur, dp[i - 1][S]);
				} else {
					cur = max(cur, dp[i - 1][j - B[i]] + A[i]);
				}
			}
		}
	}
	printf("%d\n", dp[N - 1][T]);
	return 0;
}

問4

#include <cstdio>
#include <vector>
using namespace std;

int main()
{
	int N, M;
	scanf("%d %d\n", &N, &M);
	vector<vector<bool> > kugi(N);
	for (int i = 0; i < N; ++i)
		kugi[i] = vector<bool>(i + 1, false);
	for (int h = 0; h < M; ++h) {
		int a, b, x;
		scanf("%d %d %d\n", &a, &b, &x);
		a--, b--;
		for (int i = 0; i <= x; ++i)
			for (int j = 0; j <= i; ++j)
				kugi[a + i][b + j] = true;

	}
	int res = 0;
	for (int i = 0; i < kugi.size(); ++i)
		for (int j = 0; j < kugi[i].size(); ++j)
			res += (kugi[i][j] == true);
	printf("%d\n", res);
	return 0;
}