Hatena::Grouptopcoder

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

 | 

2014-11-29

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

A - 閉路グラフ

  • 2で割るだけ
int main() {
	std::ios::sync_with_stdio(false);
	int n, k;
	cin >> n >> k;
	cout << ((n / 2 >= k) ? "YES" : "NO") << endl;
}

B - ツリーグラフ

  • 通る必要のない頂点を削除して辺の数*2を求める
  • いつものARCより難しいような・・・
int main() {
	std::ios::sync_with_stdio(false);

	int n, x;
	cin >> n >> x;
	bool hs[128];
	REP(i, n) {
		int h;
		cin >> h;
		hs[i] = h != 0 || (i == x - 1);
	}

	vector<set<int> > g(n);
	REP(i, n - 1) {
		int a, b;
		cin >> a >> b;
		--a;
		--b;
		g[a].insert(b);
		g[b].insert(a);
	}

	bool updated = true;
	while (updated) {
		updated = false;
		REP(i, n) {
			if (!(g[i].size() == 1 && !hs[i])) {
				continue;
			}
			int dst = *g[i].begin();
			g[dst].erase(i);
			g[i].clear();
			updated = true;
		}
	}

	int counter = 0;
	REP(i, n) {
		counter += g[i].size();
	}
	assert(counter % 2 == 0);
	cout << counter << endl;
}

C - 有向グラフ

  • よく分からない
  • 枝刈り探索だろうか?
  • とりあえず強連結成分分解してみる
  • 強連結成分をノードとみなしてトポロジカルソートしてみる
  • 後何文字取れるかメモってみる
  • dfsしてみる
  • TLE
  • ・・・
  • 各強連結成分について文字列をソートして高速化かなぁ・・・
  • ・・・
  • 実装無理

D - グラフではない

  • RMQ的な何かを使うんだろうなぁ・・・

結果

順位ユーザ名閉路グラフツリーグラフ有向グラフグラフではない得点 / Total
31nodchip100 02:12100 09:49(1)-200 09:49

Cが解けなかったため1ページ目に入ることができませんでした。うむむ・・・。

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