Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2010-06-06

Google Code Jam 2010 Round 2 15:50 Google Code Jam 2010 Round 2  - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 2  - nodchipのTopCoder日記 Google Code Jam 2010 Round 2  - nodchipのTopCoder日記 のブックマークコメント

1362位で敗退でした

A. Elegant Diamond

  • なんだ実装ゲーじゃん
  • "Incorrect"
  • ・・・あ、あれ?
  • "Incorrect"
  • ・・・あれ、あれ?
  • オワタorz

上下左右対象のところを点対称でやってしまっていたようです。TL上でも同じミスをされていた方がいたようです。以下はPractiveでsmall/large両方通ったコードです

static char maze[1024][1024];

int main() {
	int T;
	cin >> T;
	for (int t = 1; t <= T; ++t) {
		fill_n((char*)maze, sizeof(maze), ' ');
		cerr << t << endl;

		int k;
		cin >> k;
		string line;
		getline(cin, line);

		for (int y = 0; y < 2 * k - 1; ++y) {
			getline(cin, line);
			for (int i = 0; i < line.size(); ++i) {
				maze[256 + i][y + 256] = line[i];
			}
		}

		int bestAnswer = INT_MAX;
		for (int cx = 256 - 10; cx <= 256 + 2 * k + 10; ++cx) {
			for (int cy = 256 - 10; cy <= 256 + 2 * k + 10; ++cy) {
				//if (maze[cx][cy] == ' ' && maze[cx - 1][cy] == ' ' && maze[cx + 1][cy] == ' ' && maze[cx][cy + 1] == ' ' && maze[cx][cy - 1] == ' ') {
				//	continue;
				//}

				//printf("%c%c%c%c%c\n", maze[cx][cy], maze[cx - 1][cy], maze[cx + 1][cy], maze[cx][cy + 1], maze[cx][cy - 1]);

				int maxDistance = 0;
				bool ok = true;
				for (int fromX = 256 - 10; ok && fromX <= 256 + 2 * k + 10; ++fromX) {
					for (int fromY = 256 - 10; ok && fromY <= 256 + 2 * k + 10; ++fromY) {
						if (!isdigit(maze[fromX][fromY])) {
							continue;
						}

						maxDistance = max(maxDistance, abs(cx - fromX) + abs(cy - fromY));

						const int toX = cx * 2 - fromX;
						const int toY = cy * 2 - fromY;

						set<char> cs;
						cs.insert(maze[toX][toY]);
						cs.insert(maze[toX][fromY]);
						cs.insert(maze[fromX][toY]);
						cs.insert(maze[fromX][fromY]);
						cs.erase(' ');
						ok = cs.size() == 1;
					}
				}

				if (!ok) {
					continue;
				}

				int counter = 0;
				set<pair<int, int> > memo;
				for (int x = cx - maxDistance; x <= cx + maxDistance; ++x) {
					for (int y = cy - maxDistance; y <= cy + maxDistance; ++y) {
						const int distance = abs(cx - x) + abs(cy - y);
						if (maxDistance % 2 == distance % 2 && distance <= maxDistance) {
							if (maze[x][y] == ' ') {
								++counter;
							}
						}
					}
				}

				bestAnswer = min(bestAnswer, counter);
			}
		}

		printf("Case #%d: %d\n", t, bestAnswer);
	}
}

B. World Cup 2010

  • 何が何だか分からない・・・
  • これそれぞれのチケットを買うか買わないかで2^19すればいいのかなぁ・・・
  • コードが思い浮かばないorz
  • せめてsmallは通さねば!
  • smallだけ通った・・・

他の方の解答を見たところ、下から再帰で全探索すれば良かったようです。以下はPracticeでsmall/largeを通したコードです。

int M[1024];
ll prices[10][1024];

ll dfs(int p, int x, int k) {
	if (p == -1) {
		if (M[x] < k) {
			return INT_MAX;
		} else {
			return 0;
		}
	}

	return min(dfs(p - 1, x * 2, k) + dfs(p - 1, x * 2 + 1, k) + prices[p][x],
		dfs(p - 1, x * 2, k + 1) + dfs(p - 1, x * 2 + 1, k + 1));
}

int main() {
	int T;
	cin >> T;
	for (int t = 1; t <= T; ++t) {
		int P;
		cin >> P;
		REP(i, 1 << P) {
			cin >> M[i];
		}

		REP(p, P) {
			REP(x, 1 << (P - p - 1)) {
				cin >> prices[p][x];
			}
		}

		int answer = (int)dfs(P - 1, 0, 0);
		printf("Case #%d: %d\n", t, answer);
	}
}

C. Bacteria

  • 見た感じでsmallは実装ゲー、largeは頭使うゲー
  • smallだけでいいや・・・

以下はsmallのみ通ったコードです。

static int memo[2][128][128];

int main() {
	int C;
	cin >> C;
	for (int c = 1; c <= C; ++c) {
		int R;
		cin >> R;
		memset(memo, 0, sizeof(memo));

		for (int r = 0; r < R; ++r) {
			int x1, y1, x2, y2;
			cin >> x1 >> y1 >> x2 >> y2;

			for (int x = x1; x <= x2; ++x) {
				for (int y = y1; y <= y2; ++y) {
					memo[0][x + 1][y + 1] = true;
				}
			}
		}

		int front = 1;
		int back = 0;

		int counter = 1;
		for (;; ++counter) {
			memset(memo[front], 0, sizeof(int) * 128 * 128);
			bool alive = false;
			for (int x = 1; x < 128; ++x) {
				for (int y = 1; y < 128; ++y) {
					if (memo[back][x][y]) {
						if (!memo[back][x - 1][y] && !memo[back][x][y - 1]) {
						} else {
							memo[front][x][y] = true;
							alive = true;
						}
					} else {
						if (memo[back][x - 1][y] && memo[back][x][y - 1]) {
							memo[front][x][y] = true;
							alive = true;
						}
					}
				}
			}

			//for (int y = 1; y < 10; ++y) {
			//	for (int x = 1; x < 10; ++x) {
			//		cout << memo[front][x][y];
			//	}
			//	cout << endl;
			//}
			//cout << endl;

			swap(front, back);

			if (!alive) {
				break;
			}
		}

		printf("Case #%d: %d\n", c, counter);
	}
}

D. Grazing Google Goats

  • お!smallはwata先生のライブラリにあったはず
  • "Incorrect"
  • なんですと!?
  • 誤差死かorz

本番ではwata先生も誤差死されていたようです。

総評

全体的に焦りが強かったです。常時落ち着いて解けるようになりたいです。

iftczjsiwfiftczjsiwf2013/08/28 02:27ksismupqdpefs, <a href="http://www.ovsuncelik.com/">ehpnvyqgad</a> , [url=http://www.eoiutlzryf.com/]oultgnswgt[/url], http://www.hsswkylvsl.com/ ehpnvyqgad

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20100606
 |