nodchipのTopCoder日記

■ AtCoder Regular Contest #017 22:46

言い訳

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
138	nodchip	100 78:06	100 81:47	(1)	-	200 81:47

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

ツイートする