Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

JOI 本選 2012 - 2013 参加記

JOI コンテスト

2 / 9 (Sat.) から 2 / 10 (Sun.) にわたって開催されたJOI (日本情報オリンピック) の参加記を書きます.

  • 2 / 8 (Fri.), Okinawa

・本選開催前日だというのに25 時まで起床する.
・8 時30 分からある生物の試験に恐れ慄きながら就寝する.

・生物の試験で(たぶん) 2 点を獲得する.
・実用英語の試験で 2 点を獲得する. ここまで常用対数値です.
・10 時 40 分には学校が終わってしまった.
・14 時に家に帰る. 帰りの車の中でJOI 国のお祭り事情を書いてAccept する.
・なんか問題ときたいけどわからねーってしてたら19 時まで寝てしまった.

  • 2 / 9 (Sat.), Okinawa - Tokyo

・本選開催日だというのに26 時まで起床する.
・6 時に起床する. マフラーとコートを着たがめっちゃ暑かった.
・空港に8 時半くらいに着く. そうこうしているうちに離陸の時間となる.

・2 時間位一緒に来た友人と話をする. (リア充との格の違いを見せつけられた
・羽田空港に着く. そのままモノレールに乗って浜松町へ.
・ポケモンセンターその⑥くらいを実施した. ブイズを買い占める予定がサンダースだけを買いそびれてしまった(悔しい).
・そのまま参宮橋へ. 道中で @sndtkhr くんと会う. 色々話しながらオリンピックセンターへ.

・オリセンにはすでに @DEGwer3456 くんだったり, @satashun くんや @catupper くんを始めとする灘勢がいた.
・受付のときに結構豪華なトロフィーを頂いた. すごかった.(小並感
・そのままPractice へ. @EY1997 くんとか数名と初めてお話をした.

- 5 つの数の和を求めるプログラム
- 100000 個の試合の勝敗判定を行うプログラム
- 大文字と小文字が混じった文字列を小文字だけにするプログラム
- IOIOI
- Darts

　が出題された. それぞれ

- BIT, 和を持つセグメント木
- 比較演算子
- tolower
- for 文
- upper_bound

・を使って解いた. ジャッジシステムすごいことと同時に, imos 先生が神であることを再認識した.

・荷物置いたりした後は講演会があった. @gamelove765 くんに名刺を渡したりする.
・灘勢含め数名が遅れて入ってきていてよくないと思った(小並感②
・IC カードの話だった. どうでも良いことだけど1 msec とかの話してたし

for (int i = 0; i < strlen(str); i++)

　は少し気になった. (いやきっとわかりやすくしてくれているだけなんだろうけど...

・一息ついてから懇親会の会場へ行く.
・自己紹介phase が開催されていた. 皆今日twitter を始めたらしい.
・@wo_M さんに名刺を渡して少しお話したりした.
・@wasabiz さんも来ていて, 煽られないかとても不安だったが, そんなことなかった(良心
・ここにきて@japlj 先生も見かけなく焦りを感じてくる. が, しばらくして登場した.
・！！！写真を撮るしか無い！！！
・累計110 枚くらいのjaplj 先生の写真を撮る. とっている間, 終始imos 先生といちゃいちゃしているのを目撃した.
・チューターやOB の自己紹介Phase. 印象に残ったのは

@Hujiwara さん「ゆるゆりでセンターうまくいきました.」
japlj 先生「好きな言語はロシア語です」
@rng_58 さん「明日の30 時 - 33 時のFHC にウォーミングアップとして出場しましょう」

　の3 つの発言です.

・いろいろ落ち着いてから, それぞれ部屋に戻るphase に. @nullmineral くんと色々話をする(終始自分から煽られに来ていてやばかった
・談話室に遊びに行ったら, rng_58 さんや @hogloid さん, catupper くんが体育会系の遊びをしていた.
・怖すぎるのでこの日は23 時 30 分に就寝した.

  • 2 / 10 (Sun.) Tokyo

・朝5 時半くらいに起きる. 30 分くらいぼーっとして, ふとダンジョンをとこうと思ったので書き始める.
・ちょうど皆が起き始める時間くらいにAccept したので, 皆を誘ってご飯へ.
・nullmineral くんは言うほど食べてなかった気がする.

・そうこうしているうちに本選の会場へ. すごく緊張してくる.
・問1 - 3 が完全フィードバックで, 4, 5 が例のみか. 300pts 以上を狙おうと決める.
・10 時から少し遅れて本選が開始される.

- 問1 電飾 (Illumination)
・緊張から頭が真っ白になってやばかった.
・なにこれむずい.
・とりあえずbit 反転させて繋げればいいから, 3 つの区間の和として表せそう.
・書いた. Submitする. (ボタン押した後に, コードに1 箇所 + 1 を書きそびれたことに気づく)
・7 件正解, 25 件不正解 (0)
・やばい+ 1 書いてないじゃん... 再送信する.
・32 件正解 (100)
・ひょえー取り敢えず一安心
・コード (本選時に書いたもの):

#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
	int N;
	static int bit[100000], trans[100000];
	static int bSum[100001], rSum[100001];
	static int brev[100001], rrev[100001];
	int ans = 1;
	
	scanf("%d", &N);
	
	for (int i = 0; i < N; i++) scanf("%d", bit + i);
	for (int i = 0; i < N; i++) trans[i] = bit[i] ^ 1;
	bSum[0] = rSum[0] = 1;
	brev[N - 1] = rrev[N - 1] = 1;
	
	for (int i = 1; i < N; i++){
		bSum[i] = (bit[i] != bit[i - 1]) * bSum[i - 1] + 1;
		rSum[i] = (trans[i] != trans[i - 1]) * rSum[i - 1] + 1;
		ans = max(ans, max(bSum[i], rSum[i]));
	}
	
	for (int i = N - 2; i >= 0; i--){
		brev[i] = (bit[i] != bit[i + 1]) * brev[i + 1] + 1;
		rrev[i] = (trans[i] != trans[i + 1]) * rrev[i + 1] + 1;
	}
	
	for (int i = 0; i < N - 1; i++){
		if (bit[i] == bit[i + 1]){
			ans = max(ans, bSum[i] + rrev[i + 1] + brev[i + rrev[i + 1] + 1]);
		}
	}
	
	printf("%d\n", ans);
	
	return (0);
}


- 問2 IOI 列車で行こう (Take the 'IOI' train)
・奇数文字だったり, Iで始まってIで終わるとか面倒だなあ.
　・偶数長だったら(長さ - 1)を答えにしてしまえば良いことに気づく.
・始点O(MN) 個に対して愚直に最適な数求めれば良さそう.
・漸化式Part は恐ろしく簡単なので正義.
・メモ化配列は使い回し利くし正義.
・よしゃーSubmitしよう.
・N 件正解 (100) (ここから記憶が曖昧
・よしゃーよしゃー！！
・だいぶ精神状態が良くなってくる.
・コード (本選時に書いたもの):

#include <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
 
int memo[2][2048][2048];
int M, N;
char s[2048], t[2048];
char st[] = "IO";
 
int getMax(bool sel, int ns, int nt)
{
	if (ns == M && nt == N){
		return (0);
	}
	if (~memo[sel][ns][nt]) return (memo[sel][ns][nt]);
	
	int res = 0;
	//bool flag = false;
	if (ns < M){
		if (s[ns] == st[sel]){
			//flag = true;
			res = max(res, getMax(sel ^ 1, ns + 1, nt) + 1);
		}
	}
	if (nt < N){
		if (t[nt] == st[sel]){
			//flag = true;
			res = max(res, getMax(sel ^ 1, ns, nt + 1) + 1);
		}
	}
	
	return (memo[sel][ns][nt] = res);
}
 
int main()
{
	scanf("%d %d", &M, &N);
	scanf("%s", s);
	scanf("%s", t);
	
	memset(memo, -1, sizeof(memo));
	int ans = 0;
	for (int i = 0; i <= M; i++){
		for (int j = 0; j <= N; j++){
			if (getMax(0, i, j) & 1){
				ans = max(ans, getMax(0, i, j));
			}
			else {
				ans = max(ans, getMax(0, i, j) - 1);
			}
		}
	}
	
	printf("%d\n", ans);
	
	return (0);
}


- 問3 現代的な屋敷 (Modern Mansion)
・移動の軸になるのは始点, スイッチ, 終点だけだなあ.
・!!!グリッドグラフ!!! 辺貼ってDijkstra だなーこれ.
・で, 隣り合うところだけに辺貼ればO(K log K) じゃん. うっひょー!!
・うえー始点にスイッチあるの恐ろしく面倒なんだよなあ.
・実装方針が迷走してしまい, なぜか[今どの向きを見ているか][どの行/どの列にいるか] を状態とした嘘Dijkstra を書く. (劇ヤバ
・↑を提出する. 29 件正解, 2 件不正解 (70).
・こんなにあたってしまったのでコーナーケースにハマってんのかなあと思い12 時までデバッグしまくる. 12 時で一旦諦めて次の問題へ.
・12 時すぎて戻ってくる. 結局自分で嘘を撃墜は出来たものの, 始点にスイッチがあるときをうまく対処できず思うように実装できなかった.
・愚直に書くが, 辺を貼りまくったO(K^2 log K)のコードを書いてしまいTLE (30).
・頭抱えながらコーディング時間終了した.
・帰宅後実装した. 実装力大事だなーと改めて時間したのと同時に, 面白い問題だなあと身にしみて思った.
・コード (帰宅後書いたもの):

#include <cstdio>
#include <queue>
#include <algorithm>
#include <climits>
#include <map>
#include <vector>

#define MAX_K (200010)

typedef long long lint;

using namespace std;

struct Point {
	int x, y, id;
	Point(int x, int y, int id) : x(x), y(y), id(id) {}
	Point() {}
};

struct Edge {
	int to;
	lint cost;
	Edge(int to, lint cost) : to(to), cost(cost){}
	Edge() {}
};

bool cmpx(const Point &a, const Point &b)
{
	if (a.x - b.x) return (a.x < b.x);
	return (a.y < b.y);
}

bool cmpy(const Point &a, const Point &b)
{
	if (a.y - b.y) return (a.y < b.y);
	return (a.x < b.x);
}

bool operator > (const Edge &a, const Edge &b)
{
	return (a.cost > b.cost);
}
	
vector<Point> Xv, Yv;
vector<Edge> G[(MAX_K + 2) * 2];
lint dist[(MAX_K + 2) * 2];

int main()
{
	int M, N, K;
	
	scanf("%d %d %d", &M, &N, &K);
	
	Xv.push_back(Point(0, 0, 0));
	Xv.push_back(Point(M - 1, N - 1, 1)); Yv.push_back(Point(M - 1, N - 1, MAX_K + 1));
	G[1].push_back(Edge(MAX_K + 1, 1)); G[MAX_K + 1].push_back(Edge(1, 1));
	for (int i = 2; i < K + 2; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		
		Xv.push_back(Point(x - 1, y - 1, i)); Yv.push_back(Point(x - 1, y - 1, MAX_K + i));
		G[i].push_back(Edge(i + MAX_K, 1));
		G[MAX_K + i].push_back(Edge(i, 1));
	}
	
	sort(Xv.begin(), Xv.end(), cmpx);
	sort(Yv.begin(), Yv.end(), cmpy);
	
	for (int i = 0; i < Xv.size() - 1; i++){
		if (Xv[i].x == Xv[i + 1].x){
			G[Xv[i].id].push_back(Edge(Xv[i + 1].id, abs(Xv[i].y - Xv[i + 1].y)));
			G[Xv[i + 1].id].push_back(Edge(Xv[i].id, abs(Xv[i].y - Xv[i + 1].y)));
		}
	}
	
	for (int i = 0; i < Yv.size() - 1; i++){
		if (Yv[i].y == Yv[i + 1].y){
			G[Yv[i].id].push_back(Edge(Yv[i + 1].id, abs(Yv[i].x - Yv[i + 1].x)));
			G[Yv[i + 1].id].push_back(Edge(Yv[i].id, abs(Yv[i].x - Yv[i + 1].x)));
		}
	}
	
	fill(dist, dist + (MAX_K + 2) * 2, LLONG_MAX);
	
	priority_queue<Edge, vector<Edge>, greater<Edge> > pq;
	
	for (pq.push(Edge(0, 0)); pq.size(); pq.pop()){
		Edge e = pq.top();
		
		if (dist[e.to] <= e.cost) continue;
		dist[e.to] = e.cost;
		
		for (int i = 0; i < G[e.to].size(); i++){
			pq.push(Edge(G[e.to][i].to, e.cost + G[e.to][i].cost));
		}
	}
	
	lint ans = min(dist[1], dist[MAX_K + 1]);
	
	printf("%lld\n", ans != LLONG_MAX ? ans : -1);
	
	return (0);
}

　 - 問4 JOIOI の塔 (Tower of JOIOI)
　・シンプルな問題設定で, 扱うのもシンプルな操作なので, 解法もシンプルなんだろうと思った.
　 ・嘘DP を書いてサンプルすら通らなかったが, 解けそうな3 に気を取られていたので嘘のままSubmit.
　・帰った後に実装した. k 個作れるんだったら k - 1個作れるし, 二分探索かなあとは思ったけど, まさかこんなにシンプルだとは思わなかった.
　・コード (帰宅後書いたもの) :

#include <cstdio>

using namespace std;

char s[1000001];
int Ipos[1000001]; // int Imos[1000001];

int main()
{
	int N;
	
	scanf("%d", &N);
	scanf("%s", s);
	
	int ctr = 0;
	for (int i = N - 1; i >= 0; i--){
		if (s[i] == 'I') Ipos[++ctr] = i;
	}
	
	int left = 0, right = N;
	
	while (left != right){
		int center = (left + right + 1) / 2;
		
		int Jnum = 0, Onum = 0, Inum = 0;
		
		for (int i = 0; i < N; i++){
			if (s[i] == 'J' || (i < Ipos[center] && s[i] == 'I'))  Jnum++;
			if (s[i] == 'O' && Onum < Jnum) Onum++;
			if (s[i] == 'I' && Inum < Onum && i >= Ipos[center]) Inum++;
		}
		
		if (Jnum >= center && Onum >= center && Inum >= center) left = center;
		else right = center - 1;
	}
	
	printf("%d\n", left);
	
	return (0);
}

　 - 問5 バブルソート (Bubble Sort)
　・交換する組がO(n^2) 個あって, 交換した後に真面目にバブルソートをするとO(n^2), 分割統治とかしてもO(nlogn).
　・併せてO(n^3 log n)は部分点もキツそう.
　 ・初めにO(n log n) (部分点ならO(n^2)でも全然間に合うが) で反点数を求めて, 各組について累積和を取るとO(n^2)が達成できる.
・考察してStarry Sky 木を組むとO(n log n)まで落ちるらしい. ヤバそう.
・とはいっても, 本当に手が出ないというほどガチヤバな難易度ではなさそうだし, 早いうちに復習しようと思った.

・と色々あったが, コンテスト終了. 100 + 100 + 70 + 0 + 0 = 270 で, メダルは厳しそうと思い皆の出来を聞く.
・どうやら問3 をバグらせてしまったり, 時間超過させたらしい(辺の張りすぎ).
・nullmineral くんとか, hogloid くんとか, EY1997 くんが3 完したという話を聞く(もう1 人は誰だろう？
・合宿は余裕なラインかと思った. 地域優秀 + 優秀賞くらい？
・ご飯を食べてから解説Phase . どうでもいいが炒飯が来るまでにINF 時間かかっていた.

・解説Phase. 1 は物凄く簡潔に書けるようでガチヤバコード書いてしまい恥ずかしくなる.
・2 のjaplj さんのスライドが最高にクールだった(′ʘ⌄ʘ‵).
・3 は想定解法そのままで, 想定解法の注意点のどちらにも1 回ずつ引っかかるという残念な人を実現してしまった.
・4 はimos 先生の神アルゴリズムで神の様に解けた. imos 先生は神だと再認識した.
・5 はiwi さんの説明を半分くらいしか理解しきれていないが, 頭を整理して早いうちに書きたい.
・なにより, どの問題も面白かった!

・去年のIOIers の皆さんが来ていた. Hujiwara さんがゆるゆり布教をしていた.
・@werewolfized さんに日頃お世話になっているので, ブイズのうち1 つをプレゼントする.
・ホテルへ. スカイツリー見たりする. 歌舞伎町怖い.
・だらだらTwitter をしながらJOIOI の塔やモダンなマンションの問題を解く.

・2 / 11 (Mon.) Tokyo - Okinawa

・モダンなマンションの問題バグりまくってたのと, 眠かったのがあったので26 時ごろに就寝する.
・朝起きて1 からマンションを書き直す. 書き直しの大事さを痛感する.綺麗に解けてよかったよかった.
・荷物がめっちゃ重くてカバンが破れていた. (6.6 kg + α

・ポケセンが11:00 から開くのだが, 飛行機が11:55 に出発するのでポケモンセンターその⑦の実施を諦める.

・飛行機に乗って参加記を書き始める.
・昨日のjaplj 先生のスライドの顔文字を載せたいが, ネットに繋げないのでフラストレーションがたまる.
・帰りの車で発見して幸せになる (′ʘ⌄ʘ‵)

>>>まとめ<<<

・たのしかったです(小並感
・3 月に来れそうなので来れそうな人はまた仲良くしてやってください(帰りの車の中でいけることが確定した).
・合宿では 1 の位で四捨五入したら 0 になるような順位を目指します.