Hatena::Grouptopcoder

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

 | 

2013-03-17

AtCoder Regular Contest #013 22:49 AtCoder Regular Contest #013 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - AtCoder Regular Contest #013 - nodchipのTopCoder日記 AtCoder Regular Contest #013 - nodchipのTopCoder日記 のブックマークコメント

A 梱包できるかな?

  • next_permutation()回しておしまい
  • Accepted
int main() {
	std::ios::sync_with_stdio(false);

	int N, M, L, P, Q, R;
	cin >> N >> M >> L >> P >> Q >> R;

	vector<int> pack;
	pack.push_back(N);
	pack.push_back(M);
	pack.push_back(L);
	sort(ALL(pack));

	int answer = -1;
	do {
		MAX_UPDATE(answer, (pack[0] / P) * (pack[1] / Q) * (pack[2] / R));
	} while (next_permutation(ALL(pack)));
	cout << answer << endl;
}

B 引越しできるかな?

  • サイズをソートしてmaxとっておしまい
int main() {
	std::ios::sync_with_stdio(false);

	int C;
	cin >> C;
	int p = 0, q = 0, r = 0;

	REP(c, C) {
		int size[3];
		cin >> size[0] >> size[1] >> size[2];
		sort(size, size + 3);
		MAX_UPDATE(p, size[0]);
		MAX_UPDATE(q, size[1]);
		MAX_UPDATE(r, size[2]);
	}
	cout << p * q * r << endl;
}

C 笑いをとれるかな?

  • smallはO(20^6)のDPすれば通りそうだけどTLEしそう
  • largeは石取りゲームに帰着するのかな
  • 各軸の各方向から見て何マス切り取れるかを見ていくのだと思う
  • 2マス以上切り取れる場合は2マスとしてしまってよいのかな?(<-間違い)
  • ・・・
  • Wrong Answer
  • うむむ
  • 2マス以上もそのまま扱わなければならないらしい
  • Nimに帰着するのでxorっぽい

D 切り分けできるかな?

  • smallは適当にやればいけるはず・・・
  • Wrong Answer
  • ・・・うむむ

結果

順位ユーザ名梱包できるかな?引越しできるかな?笑いをとれるかな?切り分けできるかな?得点 / Total
75nodchip100 02:31100 06:09(4)(2)200 06:09

非常に悪い結果となってしまいました。Nimに気付ければもう少しだけ良い成績を取れたかもしれません。

NPCA Programming Contest Alpha #2 (Div.1) 18:03 NPCA Programming Contest Alpha #2 (Div.1) - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - NPCA Programming Contest Alpha #2 (Div.1) - nodchipのTopCoder日記 NPCA Programming Contest Alpha #2 (Div.1) - nodchipのTopCoder日記 のブックマークコメント

24 伝書男

  • 深い考察が必要になる問題?
  • これ計苦手なのでパスorz

25 ファインディング・芋

  • 図を見ただけで悪寒がする・・・
  • naiveに肥料を計算するとO(N^2)くらいでTLE
  • 直感だといもす法的な何か?
  • ・・・
  • 肥料の効果が始まる地点に+1、終了地点に-1を置くいもす法をやりたい
  • +1を置く部分は特に問題なし
  • -1はstepを表す配列を作って記録し、バックトラック時に消していけばいいかも
  • 1pass目で最大値を記録し、2pass目で答えを列挙する
  • 書いてみた
  • Wrong Answer
  • ・・・
  • 諦めた
  • ・・・
  • しばらくして戻ってきてみるとRejudgeで通っていた
  • Accepted
vector<vector<int> > graph;
vector<vector<int> > fertilizers;
vector<int> fadeouts;
int maxFertilized;
vector<int> answers;

void dfs(int node, int depth, int fertilized, bool firstPass) {
	fertilized -= fadeouts[depth];

	// 残りdepth < Kに注意
	for (vector<int>::iterator it = fertilizers[node].begin(), itEnd = fertilizers[node].end(); it != itEnd; ++it) {
		++fertilized;
		if (depth + *it + 1 < fadeouts.size()) {
			++fadeouts[depth + *it + 1];
		}
	}

	if (firstPass) {
		MAX_UPDATE(maxFertilized, fertilized);
	} else {
		if (fertilized == maxFertilized) {
			answers.push_back(node);
		}
	}

	for (vector<int>::iterator it = graph[node].begin(), itEnd = graph[node].end(); it != itEnd; ++it) {
		dfs(*it, depth + 1, fertilized, firstPass);
	}

	// 残りdepth < Kに注意
	for (vector<int>::iterator it = fertilizers[node].begin(), itEnd = fertilizers[node].end(); it != itEnd; ++it) {
		// fertilizedは無視
		if (depth + *it + 1 < fadeouts.size()) {
			if (--fadeouts[depth + *it + 1] < 0) {
				while(1);
			}
		}
	}
}

int main() {
	std::ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;
	graph.resize(N + 1);
	fertilizers.resize(N + 1);
	fadeouts.resize(N + 1);
	
	for (int to = 2; to <= N; ++to) {
		int from;
		cin >> from;
		graph[from].push_back(to);
	}

	REP(i, M) {
		int a, b;
		cin >> a >> b;
		fertilizers[a].push_back(b);
	}

	dfs(1, 0, 0, true);
	dfs(1, 0, 0, false);

	sort(ALL(answers));

	REP(i, answers.size()) {
		cout << answers[i] << endl;
	}
}

26 私を月に連れてって

  • 各ノードに(距離、餅の数)のリストを記録させるDP・・・?
  • ざっと頭のなかで計算したところ、計算量がO(2^N*N)とかになってしまうのだけれど・・・
  • ・・・orz

27 まげあるどん

  • これも考察系か・・・
  • 全くわからないorz

28 ミカンの対局

  • 黒の勝ち点が分かれば白の勝ち点も計算できるけど・・・
  • 黒の石をx座標でバケツソート、各バケツの中で座標のペアをカウントして、・・・ってO(N^3)なんだよなぁ
  • 分からないorz

29 はいれーつ・おぶ・かりびあん ~クエリの泉~

  • 無理

結果

RankUsernameSolvedPenalty#24#25#26#27#28#29
11nodchip10:27-0:27 (0)----

可もなく不可もなくという結果でした。上位陣すごすぎです。

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