Hatena::Grouptopcoder

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

 | 

2010-06-12

Codeforces Beta Round #17 18:50 Codeforces Beta Round #17  - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Codeforces Beta Round #17  - nodchipのTopCoder日記 Codeforces Beta Round #17  - nodchipのTopCoder日記 のブックマークコメント

A. Noldbach problem

  • やるだけ
  • と思ってたらサンプル通らない・・・
  • なんか問題文勘違いしてたorz
  • やけに英語が読みにくい気がする・・・

結果:Accepted

#define MAX (1024)
int main() {
	static bool flag[MAX];
	memset(flag, -1, sizeof(flag));
	flag[0] = flag[1] = false;
	for (int i = 2; i * i < MAX; ++i){
		if (!flag[i]){
			continue;
		}
		for (int j = i * i; j < MAX; j += i){
			flag[j] = false;
		}
	}
	vector<int> primes;
	for (int i = 2; i < MAX; ++i){
		if (flag[i]){
			primes.push_back(i);
		}
	}

	vector<int> twoPrimes;
	REP(i, primes.size() - 1) {
		twoPrimes.push_back(primes[i] + primes[i + 1] + 1);
	}

	int n, k;
	cin >> n >> k;
	const int number = distance(twoPrimes.begin(), upper_bound(twoPrimes.begin(), twoPrimes.end(), k));
	vector<int> kPrime(primes.begin(), upper_bound(ALL(primes), n));
	vector<int> inter;
	set_intersection(ALL(twoPrimes), ALL(kPrime), back_inserter(inter));

	if (inter.size() >= k) {
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;
	}
}

B. Hierarchy

  • なんか最小木っぽい
  • とりあえず書いてみた
  • サンプルが通らない・・・
  • なんか勘違いしているらしい
  • チャンと考えてみた
  • これ貪欲法じゃね?

結果:Accepted

int main() {
	int n;
	cin >> n;
	vector<pair<int, int> > qs;
	for (int i = 1; i <= n; ++i) {
		int q;
		cin >> q;
		qs.push_back(make_pair(q, i));
	}
	sort(ALL(qs));

	int m;
	cin >> m;

	vector<vector<pair<int, int> > > g(n + 1);
	REP(i, m) {
		int a, b, c;
		cin >> a >> b >> c;
		g[b].push_back(make_pair(c, a));
	}

	REP(i, g.size()) {
		sort(ALL(g[i]));
	}

	int answer = 0;
	int counter = 0;
	for (vector<vector<pair<int, int> > >::iterator it = g.begin(), itEnd = g.end(); it != itEnd; ++it) {
		if (it->empty()) {
			continue;
		}
		++counter;
		answer += (*it)[0].first;
	}

	if (counter == n - 1) {
		cout << answer << endl;
	} else {
		cout << -1 << endl;
	}
}

C. Balance

  • 組み合わせっぽいようなDPっぽいようなメモつき探索っぽいような・・・
  • 分からんorz

D. Notepad

  • 問題を整理してみる
  • [tex:(b-1)b^{n-1} \mod c}が計算できればよいらしい
  • Google先生にお伺いを立てたところJavaのBigIntegerにmodPow()という物があるらしいことが分かった
  • 書いみようか・・・
  • TLE
  • 人生そんなに甘くないよね・・・

E. Palisection

  • 回文が始まるいちと終わる位置で尺取すればいい気がする
  • やってみた
  • だめだったorz
トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20100612
 |