Zenn
🍎

【AtCoder】ABC134 B - Golden Apple をいろいろな方法で解いてみた

2022/11/16に公開
AtCoder
tech

はじめに

https://atcoder.jp/contests/abc134/tasks/abc134_b
この問題の制約は以下の値でもよさそうです。

  • 1 \le N \le 10^{18}
  • 1 \le D \le 10^{18}

しかし、B問題ということもあり数学が苦手な人でも解くことができるよう、いろいろな方法で解ける余地を残しているようにも感じました。そういうわけで、想定解法である数学的な解き方以外のアプローチも考えてみます。

数学的解法

まずは想定解法です。
番号 i の木に配置された監視員は、番号が i-D 以上 i+D 以下のすべての林檎の木を監視できます。よって、1 人の監視員が監視できる林檎は最大で 2D+1 個です。したがって、答えは \lceil N / (2D + 1) \rceil になります。ただし、\lceil x \rceil は実数 x 対して x 以上の最小の整数です。

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, d;
	cin >> n >> d;
	cout << (n + 2 * d) / (2 * d + 1) << endl;
}

\lceil a / b \rceil を (a + b - 1) / b で計算するテクニックを使用しています。

bit全探索

N が 20 以下とかなり小さい値しか取らないため、bit全探索 でも間に合いそうです。番号 i の木に監視員を配置するか配置しないかの 2^N の組み合わせを全探索します。

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, d;
	cin >> n >> d;

	int ans = n;
	for (int bit = 0; bit < (1 << n); ++bit) {
		vector<bool> is_monitored(n, false);
		for (int i = 0; i < n; ++i) {
			if (bit & (1 << i)) {
				for (int j = max(i - d, 0); j <= min(i + d, n - 1); ++j) {
					is_monitored[j] = true;
				}
			}
		}
		bool is_ok = true;
		for (int i = 0; i < n; ++i) {
			if (!is_monitored[i]) {
				is_ok = false;
			}
		}
		if (is_ok) {
			ans = min(ans, __builtin_popcount(bit));
		}
	}

	cout << ans << endl;
}

計算量が O(2^NND) なので一見間に合わなさそうですが、実行時間は195msでした。C++は偉大な言語です。

ちなみに木が監視されているかどうかを管理するのに配列ではなくビットを使用すると、計算量を O(2^NN) に落とすことができます。

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, d;
	cin >> n >> d;

	vector<int> st(n);

	for (int i = 0; i < n; ++i) {
		int tot = 0;
		for (int j = max(i - d, 0); j <= min(i + d, n - 1); ++j) {
			tot |= 1 << j;
		}
		st[i] = tot;
	}

	int ans = n;
	for (int bit = 0; bit < (1 << n); ++bit) {
		int parity = 0;
		for (int i = 0; i < n; ++i) {
			if (bit & (1 << i)) {
				parity |= st[i];
			}
		}
		if (__builtin_popcount(parity) == n) {
			ans = min(ans, __builtin_popcount(bit));
		}
	}

	cout << ans << endl;
}

実行時間が67msになりました。

動的計画法(DP)

組み合わせの問題なのでDPも有効です。
しかし、割り算を足し算で計算しているだけなのでやや虚無になります。

#include <bits/stdc++.h>
using namespace std;

int main(){
	int n, d;
	cin >> n >> d;

	vector<int> dp(n + 1);
	dp[0] = 0;

	for (int i = 1; i <= n; ++i) {
		if (i >= 2 * d + 1) {
			dp[i] = dp[i - (2 * d + 1)] + 1;
		}
		else {
			dp[i] = 1;
		}
	}

	cout << dp[n] << endl;
}

初期化が面倒なので貰うDPで実装しました。

おわりに

OnlineMathContest(OMC)で数学力を高めましょう。

Discussion