2011/06/26(日)ttsuki: ICPCの問題と結果見てる。今年はついに4問必須になったようだ。いかにABCを序盤1時間くらいでさくさくっと解いて、残りの2時間でDEFGのうちどれかを何とか通せればって感じだな。問題さらっと読んだとこでは、DとFはたぶん解けそうだけど、EとGは??

はてブ数 2011/06/26 05:51 計算機な日記::プロコンつーさ
ICPCの国内予選があったらしいので問題読んだりコード書いたりしてみた。

以下解答の方針とか書いてるので、解いてみたい人は読まないで。

問題はこちら http://icpc2011.ait.kyushu-u.ac.jp/icpc2011/contest/all_ja.html
ルールはこちらhttp://icpc2011.ait.kyushu-u.ac.jp/ja/domestic-contest
とりあえず、4問DCBA書いてみた。

問題読んでた時間も含めて1時間半弱くらいなので、WAが無ければペナルティは13800くらいかしら。いつも通りの順番でやったら10200って感じ。まぁ、WAが無ければ、ね……。

D。たかだか円盤が24個しかないのと、白白黒黒とか取れるときは、どっちを先にとってもいいので、取れるやつを取ってけばおk? ただ、白白白とかあったときにはどういうペアで取るかで結果が変わっちゃうから、ここは探索する必要があるかな。メモ化DFSでおk? 後はまぁ、普通に円の交差判定と、上に重なってる状態をどうやって表現するかというデータ構造がさくっと思いつけるかどうか。

C。定番のシードフィル。が、まさかのバグって、デバッグに+20分ほど掛かっちまいました。テヘペロ。左上起点だから右と下にだけ見てけばいいよね、ってそんなわけあるか! が主な原因です。後は、再起で書いたり四重ループにしてみたりしてたら40分くらい経ってました。

B。文字列を一行読む方法を知ってるかと。「その間にある文字列の中で 括弧がバランスしている」とかに釣られて再帰関数で書いちゃうと、ちまいバグが出て泥沼化する予感。ここですんなり、スタックが使えれば簡単。

A。エラトステネス。素数というと、初めて出た2007年アジア地区予選(東京大会)のBを思い出す。素数表の作り方を知っていれば簡単。試し割りでも解けるのかな?

F。たぶん解けそうとか言ってたけど、問題をよく見ると、建物回り込んでフェンスが届いちゃうときの処理が、円の交点計算が必要?でちょっとめんどくさそう。

建物にひもが回り込んでいくところとか、条件分岐が激しくてコード量も結構増えそうなので、落ち着いて正確にコードが書けるかが試されそう。

Eとかよーわからん。また考える。

Gとか問題おもしろい。見たことない感じ。
迷路を見るとわくわくするわね。

今年は、ウチの大学からは国内予選突破チームが出なかったらしい。まぁ、まぁ。残念。うーん、アジア地区予選はオンライン国内予選の1048576倍は楽しいから、是非行ってほしいと思うのだ。

そんな、気づけば、朝。

#include <iostream>
#include <string>
#include <vector>
#include <stack>

using namespace std;

//#define SOLVE_A
//#define SOLVE_B
//#define SOLVE_C
//#define SOLVE_D

#ifdef SOLVE_A
// 10分くらい

// 素数系ではお約束、定番のエラトステネスをば。
const int MAX_PRIME = 1000000;
bool table[MAX_PRIME];
vector<int> primes;
void initprimes()
{
	memset(table, 0xFF, sizeof(table));
	table[0] = table[1] = false;
	for (int i = 2; i < MAX_PRIME; i++)
	{
		if (table[i])
		{
			primes.push_back(i);
			for (int j = i * 2; j < MAX_PRIME; j += i)
				table[j] = false;
		}
	}
}

int main()
{
	initprimes();
	while (true)
	{
		int n; cin >> n;
		if (n == 0)
			break;

		int count = 0;
		for (int i = n + 1; i <= 2 * n; i++)
			if (table[i])
				count++;

		cout << count << endl;
	}
	return 0;
}

#endif

#ifdef SOLVE_B
// 15分くらい
int main()
{
	while(true)
	{
		// 文字列を1行読む方法知ってますか?
		string line;
		getline(cin, line);
		
		if (line == ".")
			break;

		// 括弧の状態を保持するスタック
		stack<char> cacco;

		bool state = true;
		for (int i = 0; i < line.size(); i++)
		{
			switch(line[i])
			{
				case '(': cacco.push(')'); break;
				case '[': cacco.push(']'); break;
				case ')':
				case ']':
					if (!cacco.empty())
					{
						state &= cacco.top() == line[i];
						cacco.pop();
					}
					else
						state = false;
					break;
			}
		}
		cout << (state ? "yes" : "no") << endl;
	}
}

#endif


#ifdef SOLVE_C
// 40分くらい

// 配列を簡単にコピーしたいときは構造体に内包してしまうがよい。
struct Panel
{
	int c[10][10];
};

// pを塗り、塗ったマスの数を返す。前提: from == to だとバグる
int seedfill(Panel &p, int x, int y, int from, int to)
{
	if (p.c[x][y] != from)
		return 0;

	p.c[x][y] = to;
	return seedfill(p, x-1, y, from, to) + seedfill(p, x, y-1, from, to) +
		seedfill(p, x+1, y, from, to) + seedfill(p, x, y+1, from, to) + 1;
}

// 塗ったものを返す
Panel seedfill(Panel p, int to)
{
	if ( p.c[1][1] == to) return p;
	seedfill(p, 1, 1, p.c[1][1], to);
	return p;
}

// 塗ったマスの数を返す
int seedfillcount(Panel p)
{
	return seedfill(p, 1, 1, p.c[1][1], 0);
}

// 同じような処理をn重ループさせたいときは再帰関数が楽。
// 関数名dfsってなってるけど、別に検索してないなこれ。
int dfs(Panel p, int d, int last)
{
	if (d == 4)
	{
		seedfill(p, last);
		return seedfillcount(p);
	}

	int max = 0;
	for (int i = 1; i < 6; i++)
	{
		Panel pc = seedfill(p, i);
		int r = dfs(pc, d + 1, last);
		if (r > max)
			max = r;
	}
	return max;
}

int main()
{
	while(true)
	{
		int h, w, c;
		cin >> h >> w >> c;
		if (h == 0)
			break;

		// 読み込み
		Panel p0 = { {{0}} };
		for (int y = 0; y < h; y++)
			for (int x = 0; x < w; x++)
			{
				int k = 0;
				cin >> k;
				p0.c[x+1][y+1] = k;
			}

		// 再帰関数で書くか
		// cout << dfs(p0, 0, c) << endl;

		// 素直に4重ループで書くか
		#define REP(i,n) for (int i = 0; i < (n); i++)
		int max = 0;
		int i0 = p0.c[1][1];
		REP(i1, 6)
		{
			Panel p1 = seedfill(p0, i1 + 1);
			REP(i2, 6)
			{
				Panel p2 = seedfill(p1, i2 + 1);
				REP(i3, 6)
				{
					Panel p3 = seedfill(p2, i3 + 1);
					REP(i4, 6)
					{
						Panel p4 = seedfill(p3, i4 + 1);
						
						// 最後の1回は色が決まってる。
						Panel p5 = seedfill(p4, c);
						int count = seedfillcount(p5);
						if (count > max) max = count;
					}
				}
			}
		}
		cout << max << endl;
	}

	return 0;
}

#endif


#ifdef SOLVE_D
// 20分くらい

int visited[16777216];
// typedef bitset<24> Field; // とかもいいかも

struct Envan { int x, y, r, c; };
vector<Envan> envans;
vector<vector<int>> hit;


// 取り除けますか
inline bool isRemovable(int field, int i)
{
	// 円盤が存在するか
	bool ok = (field & 1 << i); // ←bitsetなら単にfield[i]と書ける

	// それよりも上に乗っている円盤がすべて存在しないか
	for (int j = 0; j < hit[i].size(); j++)
		ok = ok && ((field & 1 << hit[i][j]) == 0);

	return ok;
}


int dfs(int field)
{
	// 訪問済み
	if (visited[field] != -1)
		return visited[field];

	int max = 0;
	// 円盤二枚を選ぶ。
	for (int i = 0; i < envans.size(); i++)
	{
		if (!isRemovable(field, i)) continue;
		for (int j = i + 1; j < envans.size(); j++)
		{
			if (envans[i].c != envans[j].c) continue;
			if (!isRemovable(field, j)) continue;

			// 取り除いて次へ
			int r = dfs(field ^ (1 << i) | (1 << j)) + 2;
			if (r > max)
				max = r;
		}
	}

	return visited[field] = max;
}

int main()
{
	while(true)
	{
		int n;
		cin >> n;
		if (n == 0) break;

		// リセット
		envans.clear();
		hit.clear();
		memset(visited, 0xFF, sizeof(visited));

		// 読み込み
		for (int i = 0; i < n; i++)
		{
			int x, y, r, c;
			cin >> x >> y >> r >> c;
			Envan e = {x, y, r, c};
			envans.push_back(e);

			// ついでに重なり判定
			vector<int> hitting; // ←重なってるやつリスト
			for (int j = 0; j < i; j++)
			{
				int dx = envans[j].x - e.x;
				int dy = envans[j].y - e.y;
				int sr = envans[j].r + e.r;
				if (dx * dx + dy * dy < sr * sr)
					hitting.push_back(j);
			}
			hit.push_back(hitting);
		}
		cout << dfs((1<<envans.size())-1) << endl;
	}
	return 0;
}

#endif