Hatena::Grouptopcoder

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

 | 

2014-02-09

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

言い訳

ARCがあるのをすっかり忘れており、残り15分から参加しました。

A - 素数、コンテスト、素数

  • N <= 1,000,000 なのでO(N)で書いておk
  • Accepted
bool isPrime(int N) {
	for (int i = 2; i < N; ++i) {
		if (N % i == 0) {
			return false;
		}
	}
	return true;
}

int main() {
	std::ios::sync_with_stdio(false);
	int N;
	cin >> N;
	cout << (isPrime(N) ? "YES" : "NO") << endl;
}

B - 解像度が低い。

  • 過去連続で何回上がっていたかを保持していけば良い
  • Accepted
int main() {
	std::ios::sync_with_stdio(false);
	int N, K;
	cin >> N >> K;
	int last = INT_MAX;
	int con = 0;
	int result = 0;
	REP(n, N) {
		int A;
		cin >> A;
		if (last < A) {
			++con;
		}
		else {
			con = 1;
		}
		if (K <= con) {
			++result;
		}
		last = A;
	}
	cout << result << endl;
}

C - 無駄なものが嫌いな人

  • 普通に幅優先するだけかな?
  • TLE
  • あれ・・・
  • (時間切れ)
  • 上限見誤ってたorz
  • どうしよう・・・
  • ・・・
  • 両側探索するだけか
  • Practice で Accepted
map<int, int> dp(const vector<int>& ws) {
	map<int, int> current;
	current[0] = 1;
	for (int w : ws) {
		map<int, int> next;
		for (const auto& p : current) {
			next[p.first] += p.second;
			next[p.first + w] += p.second;
		}
		swap(current, next);
	}
	return current;
}

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

	int N, X;
	cin >> N >> X;
	vector<int> w0, w1;
	REP(n, N) {
		int w;
		cin >> w;
		if (n & 1) {
			w0.push_back(w);
		}
		else {
			w1.push_back(w);
		}
	}

	map<int, int> m0 = dp(w0);
	map<int, int> m1 = dp(w1);
	int result = 0;
	for (const auto& p : m0) {
		result += m1[X - p.first] * p.second;
	}
	cout << result << endl;
}

D - ARCたんクッキー

  • 読んでいません

結果

順位ユーザ名素数、コンテスト、素数解像度が低い。無駄なものが嫌いな人ARCたんクッキー得点 / Total
138nodchip100 78:06100 81:47(1)-200 81:47

残り15分から参加という無謀なことはしばらくはやめておこうと思います。

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