Hatena::Grouptopcoder

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

 | 

2014-12-07

yukicoder open 2014 22:06 yukicoder open 2014 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - yukicoder open 2014 - nodchipのTopCoder日記 yukicoder open 2014 - nodchipのTopCoder日記 のブックマークコメント

No.88 次はどっちだ

  • 空きマスの数の偶奇で場合分け
  • AC
int main() {
	std::ios::sync_with_stdio(false);

	string S;
	cin >> S;
	int empty = 0;
	REP(i, 8) {
		string row;
		cin >> row;
		empty += count(ALL(row), '.');
	}

	if (empty % 2 == 1) {
		S = (S == "oda" ? "yukiko" : "oda");
	}

	cout << S << endl;
}

No.89 どんどんドーナツどーんといこう!

  • "円環体 体積"でググって出てきた公式をそのまま実装する
  • AC
int main() {
	std::ios::sync_with_stdio(false);

	double C, a, b;
	cin >> C >> a >> b;
	double V = 0.25 * PI * PI * (a + b) * (b - a) * (b - a);
	printf("%.20f\n", V * C);
}

No.90 品物の並び替え

  • N!全通り試す
  • AC
int main() {
	std::ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;
	int scores[16][16];
	CLEAR(scores);
	REP(m, M) {
		int item1, item2, score;
		cin >> item1 >> item2 >> score;
		scores[item1][item2] = score;
	}

	vector<int> items;
	REP(n, N) {
		items.push_back(n);
	}

	int bestScore = 0;
	do {
		int score = 0;
		REP(i, N) {
			REP(j, i) {
				score += scores[items[i]][items[j]];
			}
		}
		MAX_UPDATE(bestScore, score);
	} while (next_permutation(ALL(items)));

	cout << bestScore << endl;
}

No.91 赤、緑、青の石

  • 賢い解法がありそうだけど
  • 10^7までなので貪欲法で1個ずつ試してみる
  • AC
int main() {
	std::ios::sync_with_stdio(false);

	int R, G, B;
	cin >> R >> G >> B;
	int answer = 0;
	while (R + G + B > 2) {
		if (R && G && B) {
			int add = MIN(R, MIN(G, B));
			answer += add;
			R -= add;
			G -= add;
			B -= add;
		}
		else {
			if (R < G) {
				swap(R, G);
			}
			if (G < B) {
				swap(G, B);
			}
			if (R < G) {
				swap(R, G);
			}
			R -= 2;
			B += 1;
		}
	}
	cout << answer << endl;
}

No.92 逃走経路

  • "dp[k番目][現在いる町番号]=その場所にいることができるか"のDP
  • AC
int main() {
	std::ios::sync_with_stdio(false);

	int N, M, K;
	cin >> N >> M >> K;
	vector<vector<pair<int, int> > > graph(N + 1);
	REP(m, M) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back(MP(b, c));
		graph[b].push_back(MP(a, c));
	}

	bool dp[2][128];
	CLEAR(dp);
	int front = 0;
	int back = 1;
	REP(n, N + 1) {
		dp[back][n] = 1;
	}

	REP(k, K) {
		int d;
		cin >> d;

		REP(n, N + 1) {
			dp[front][n] = false;
		}

		for (int from = 1; from <= N; ++from) {
			for (const auto& edge : graph[from]) {
				if (edge.second != d) {
					continue;
				}

				dp[front][edge.first] |= dp[back][from];
			}
		}

		swap(front, back);
	}

	vector<int> answer;
	REP(n, N) {
		if (dp[back][n + 1]) {
			answer.push_back(n + 1);
		}
	}

	cout << answer.size() << endl;
	REP(i, answer.size()) {
		if (i) {
			cout << " ";
		}
		cout << answer[i];
	}
	cout << endl;
}

No.93 ペガサス

  • 全くわからない
  • これがなぜ★×3なのだろうか・・・。

No.94 圏外です。(EASY)

  • Union Findして各集合ごとに一番遠い点同士を見つける
  • AC
int main() {
	std::ios::sync_with_stdio(false);

	int N;
	cin >> N;
	vector<P> pos;
	REP(n, N) {
		int x, y;
		cin >> x >> y;
		pos.push_back(P(x, y));
	}

	UnionFind uf(N);
	REP(i, N) {
		REP(j, i) {
			if (abs(pos[i] - pos[j]) < 10 + EPS) {
				uf.unionSet(i, j);
			}
		}
	}

	double answer = 1.0;
	if (N) {
		answer = 2.0;
	}
	REP(i, N) {
		REP(j, i) {
			if (!uf.findSet(i, j)) {
				continue;
			}
			MAX_UPDATE(answer, abs(pos[i] - pos[j]) + 2.0);
		}
	}

	printf("%.20f\n", answer);
}

No.95 Alice and Graph

  • コインの数から頂点番号のなるだけ大きい物から取っていけば良さそう
  • 全探索かなぁ・・・?
  • 最後のサンプルがTLEした
  • それっぽい枝刈りを入れてみる
  • サンプルは通った
  • 出してみる
  • TLE
  • 幅優先探索に切り替えてみる
  • TLE
  • うむむ・・・
  • これは嘘解法を投入するべきか・・・
  • たとえば・・・
  • ビームサーチ?
  • 幅優先からビームサーチに切り替えるのは1行書き換えるだけだから簡単
  • AC
  • 通った・・・
int graph[64][64];
int K;

bool canGo(const vector<int>& path) {
	ll sum = 0;
	for (int i = 0; i + 1 < path.size(); ++i) {
		sum += graph[path[i]][path[i + 1]];
	}
	return sum <= K;
}

const int PRUNING_THRESHOLD = 1 << 16;

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

	int N, M;
	cin >> N >> M >> K;
	REP(i, 64) REP(j, 64) {
		graph[i][j] = INT_MAX / 3;
	}
	REP(m, M) {
		int u, v;
		cin >> u >> v;
		graph[u][v] = 1;
		graph[v][u] = 1;
	}

	REP(k, 64) REP(i, 64) REP(j, 64) {
		MIN_UPDATE(graph[i][j], graph[i][k] + graph[k][j]);
	}

	vector<int> initial;
	initial.push_back(1);
	
	vector<vector<int> > q;
	q.push_back(initial);
	for (int n = N; n > 1; --n) {
		vector<vector<int> > next;
		for (auto path : q) {
			for (int insertIndex = 1; insertIndex <= path.size() && next.size() < PRUNING_THRESHOLD; ++insertIndex) {
				path.insert(path.begin() + insertIndex, n);
				if (canGo(path)) {
					next.push_back(path);
				}
				path.erase(path.begin() + insertIndex);
			}

			if (next.size() == PRUNING_THRESHOLD) {
				break;
			}
		}

		if (!next.empty()) {
			swap(q, next);
		}
	}

	ll answer = 0;
	for (int k : q[0]) {
		answer += (1LL << (k - 1)) - 1;
	}
	cout << answer << endl;
}

No.96 圏外です。

  • こちらはNがでっかいやつか・・・
  • ようは連結成分の列挙と、各連結成分内で最も遠い2点の列挙を高速に行えば良さそう
  • 後者はググったら蟻本に載っていると出てきた
  • 写経してみる
  • とりあえず出してみる
  • TLE
  • 前者を高速化するの忘れてたorz
  • これはどうするんだろう
  • メッシュに区切って各セルの中でUnion Findかければいいのかな?
  • とりあえず書いてみる
  • TLE
  • うむむ・・・
  • どこで時間がかかっているんだろう?
  • 手元のワーストケースで1/10くらい処理が終わったところで無限ループっぽい動きをしている
  • Visual Studioのデバッグ実行で追いかけてみる
  • ・・・
  • なんか蟻本から写経したところで無限ループしてる!
  • 3辺が直角三角形になっているときに無限ループしているっぽい?
  • 回避策として点数が10以下の時はO(N)に切り替えてみる
  • AC
  • 通った・・・
int main() {
	std::ios::sync_with_stdio(false);

	int N;
	cin >> N;
	vector<int> X;
	vector<int> Y;
	vector<P> pos;
	REP(n, N) {
		int x, y;
		cin >> x >> y;
		pos.push_back(P(x, y));
		X.push_back(x);
		Y.push_back(y);
	}

	static vector<int> cells[2048][2048];
	REP(n, N) {
		int x = X[n];
		int y = Y[n];

		int cellX = (x + 10000) / 10;
		int cellY = (y + 10000) / 10;
		REP(dx, 3) REP(dy, 3) {
			cells[cellX + dx][cellY + dy].push_back(n);
		}
	}

	UnionFind uf(N);
	REP(cellX, 2048) {
		REP(cellY, 2048) {
			const auto& ps = cells[cellX][cellY];
			REP(i, ps.size()) {
				REP(j, i) {
					if ((X[ps[i]] - X[ps[j]]) * (X[ps[i]] - X[ps[j]]) + (Y[ps[i]] - Y[ps[j]]) * (Y[ps[i]] - Y[ps[j]]) <= 100) {
						uf.unionSet(ps[i], ps[j]);
					}
				}
			}
		}
	}

	map<int, vector<P> > points;
	REP(i, N) {
		points[uf.root(i)].push_back(pos[i]);
	}

	double answer = 1.0;
	//int counter = 0;
	//cerr << "points.size(): " << points.size() << endl;
	for (auto& connected : points) {
		//if (counter == 15281) {
		//	int temp = 0;
		//}
		//if (15200 <= counter && counter <= 15300) {
		//	cerr << counter << endl;
		//}
		//++counter;

		int n = connected.second.size();
		if (n == 1) {
			MAX_UPDATE(answer, 2.0);
			continue;
		}

		if (n == 2) {
			MAX_UPDATE(answer, abs(connected.second[0] - connected.second[1]) + 2.0);
			continue;
		}

		vector<P> qs = convex_hull(&connected.second[0], connected.second.size());
		n = qs.size();

		if (n < 10) {
			REP(i, n) REP(j, i) {
				MAX_UPDATE(answer, abs(qs[i] - qs[j]) + 2.0);
			}
			continue;
		}

		int i = 0;
		int j = 0;
		for (int k = 0; k < n; ++k) {
			if (!cmp_x(qs[i], qs[k])) i = k;
			if (cmp_x(qs[j], qs[k])) j = k;
		}
		int si = i, sj = j;
		while (i != sj || j != si) {
			MAX_UPDATE(answer, abs(qs[i] - qs[j]) + 2.0);
			if (cross(qs[(i + 1) % n] - qs[i], qs[(j + 1) % n] - qs[j]) < 0) {
				i = (i + 1) % n;
			}
			else {
				j = (j + 1) % n;
			}
		}
	}

	printf("%.20f\n", answer);
}

No.97 最大の値を求めるくえり

  • クエリ問題はわからないのでパス・・・

結果

順位ユーザー名次はどっちだどんどんドーナツどーんといこう!品物の並び替え赤、緑、青の石逃走経路圏外です。(EASY)Alice and Graph圏外です。最大の値を求めるくえりペガサスTotal
10nodchip23 00:07:2929 00:11:0983 00:14:5590 00:22:2176 00:32:54150 00:40:22153 02:21:41166 02:43:180 -0 -770 02:43:18

得点調整が入り最終的には10位になりました。ぎりぎり入賞とのことです。2問抱えて諦めかけていましたが、どうにかこうにか解くことが出来ました。諦めてはいけませんね。

SanneSanne2016/05/03 08:32David, ich verrate Dir, dass ich da mehrmals auftrat (meine Haare haben die Lübecker Zeitung zu einem Foto inspiriert), aber dass ich da nicht mehr auftrete, so lange dorten der Herr Dworik auf der Bühne noch mehr die Diva gibt als ich.Wehe übrigens, wenn der nich’ diese UOfsf-Frizur, sondern eine Buurmannsche Mähne hätte, der tät sich was drauf einbilden

TishTish2016/05/06 22:34better ways to earn money instead of an SBA loan.1. buy someones food stamps card for half price. for example $200.00 food stamp you buy it for $100.00 then resale it for $125 making $25.002. get 3 hoes working for you. Instead of <a href="http://jacapcosg.com">proistution</a> do stripping, pron movies, and other legal X rated stuff make $100.00 each x 3 = $300.00 per day x 30 = $,9000 per month in3.

DorothyDorothy2016/05/08 12:26I don’t suppose I’ve never learned something like this before. So good to see somebody with some authentic ideas on this subject. I really thank you for beginning it. This web site is one thing that is wanted on the web, somebody with slightly oritinaligy. http://hrqvoxgmaup.com [url=http://ojrmskmygz.com]ojrmskmygz[/url] [link=http://wmjhxsdbdru.com]wmjhxsdbdru[/link]

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