B - 円形公園の街灯 / Street Lights in a Circular Park Editorial by admin
gemini-3.5-flash-thinking概要
円環上に配置された \(N\) 本の柱のうち、ベンチがある \(M\) 本の柱への「最大距離（ずれ角）」が最小となるように、街灯を設置する柱を \(1\) つ選ぶ問題です。 求める最小コストを既約分数の形式で出力します。
考察
1. 素朴なアプローチとその限界
すべての柱 \(i\) (\(1 \leq i \le N\)) について、すべてのベンチ \(S_k\) への距離の最大値を愚直に計算すると、計算量は \(O(N \times M)\) になります。 制約は \(N \le 10^9\)、\(M \le 2 \times 10^5\) であるため、この方法では実行時間制限（TLE）に間に合いません。 \(N\) が非常に大きいため、街灯を置く候補を絞り込み、効率よく最小コストを計算する必要があります。
2. 重要な観察：「ベンチのない最大の隙間」に着目する
円環上で、隣り合うベンチの間の距離（柱の個数差）を 隙間 と呼ぶことにします。 ベンチが設置されている柱を時計回りに並べたとき、隣り合うベンチ同士の間隔を \(L_1, L_2, \ldots, L_M\) とします。これらの総和は円周の長さ \(N\) に等しくなります。
ここで、「ベンチが存在しない最大の隙間」 に着目します。最大の隙間の長さを \(L_{\max}\) とします。
街灯を設置する位置として、この 最大の隙間 \(L_{\max}\) のちょうど反対側の中央 を選びます。 なぜこれが最適なのでしょうか？
具体例として、\(N = 10\) でベンチが \([2, 5, 9]\) にある場合を考えます。 * ベンチ間の隙間は、 * \(2\) と \(5\) の間：長さ \(3\) * \(5\) と \(9\) の間：長さ \(4\) （これが最大隙間 \(L_{\max} = 4\)） * \(9\) と \(2\) の間：長さ \(3\) * 最大の隙間（長さ \(4\)）の両端にあるベンチは \(5\) と \(9\) です。この隙間の反対側の中央付近である 柱 \(2\) に街灯を置きます。 * このとき、街灯からベンチ \(5\) への距離は \(3\)、ベンチ \(9\) への距離は \(3\) となり、その他のベンチ（\(2\) 自体）への距離は \(0\) です。したがって、最大距離は \(3\) に抑えられます。
一般に、最大の隙間 \(L_{\max}\) の反対側中央に街灯を置くと、その隙間の両端にあるベンチが「最も遠いベンチ」になります。その他のベンチはすべて街灯がある側の半円に密集しているため、これらよりも街灯に近くなります。 したがって、すべてのベンチへの最大距離 \(D\) は、最大の隙間の両端への距離に一致し、以下のように数式化できます。
3. 最大距離 \(D\) の数式化
円周の長さ \(N\) の偶奇によって、距離の計算がわずかに異なります（整数除算の切り捨てを考慮するため）。
\(N\) が偶数の場合 各隙間 \(L\) に対して、隙間の半分の長さ（切り捨て）の最大値を
max_valとします。 $\(\text{max\_val} = \max \left( \lfloor L / 2 \rfloor \right)\)\( このとき、街灯から最も遠いベンチまでの最小距離 \)D\( は次のようになります。 \)\(D = \frac{N}{2} - \text{max\_val}\)$\(N\) が奇数の場合 同様に、各隙間 \(L\) に対して以下のように
max_valを定義します。 $\(\text{max\_val} = \max \left( \lfloor (L - 1) / 2 \rfloor \right)\)\( このときの最小距離 \)D\( は次のようになります。 \)\(D = \frac{N - 1}{2} - \text{max\_val}\)$
4. 角度への変換と既約分数化
求めた最小距離 \(D\) に対し、実際のコスト（角度）は \(D \times \frac{360}{N}\) 度となります。 これを既約分数 \(\frac{P}{Q}\) の形で出力するため、 * 分子 \(P = D \times 360\) * 分母 \(Q = N\) とし、両者を最大公約数 \(\gcd(P, Q)\) で割ることで既約分数にします。
アルゴリズム
- ベンチの位置を表す配列 \(S\) を昇順にソートします。
- 隣り合うベンチの間隔（円環の境界をまたぐものも含む）をすべて計算し、配列 \(L\) に格納します。
- \(L_i = S_{i+1} - S_i\) （\(0 \le i < M-1\)）
- \(L_{M-1} = N + S_0 - S_{M-1}\)
- \(N\) の偶奇に応じて、各 \(L_i\) から
max_valを計算します。 max_valを用いて、最小距離 \(D\) を求めます。- \(P = D \times 360\)、\(Q = N\) とし、\(\gcd(P, Q)\) で割って既約分数
P/Qを出力します。
計算量
- 時間計算量: \(O(M \log M)\) ベンチの位置 \(S\) のソートに \(O(M \log M)\) かかります。その後の間隔の計算や最大値の探索は \(O(M)\) で行えるため、全体の時間計算量はソートがボトルネックとなり \(O(M \log M)\) となります。\(M \le 2 \times 10^5\) であるため、実行時間制限に余裕で間に合います。
- 空間計算量: \(O(M)\)
ベンチの位置と間隔を格納する動的配列（
std::vector）に \(O(M)\) のメモリを使用します。
実装のポイント
円環の境界の処理: 最後のベンチ \(S_{M-1}\) と最初のベンチ \(S_0\) の間の距離は、円環を一周することを考慮して \(N + S_0 - S_{M-1}\) と計算する必要があります。
オーバーフローの防止: \(N\) は最大で \(10^9\) になるため、分子 \(P = D \times 360\) を計算する際に、標準的な32ビット整数型（
int）ではオーバーフローする可能性があります。C++ではlong long型を使用して計算を行います。既約分数化: C++17以降で利用可能な
std::gcdを使用すると、最大公約数を簡潔かつ高速に求めることができます。ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long N;
int M;
if (!(cin >> N >> M)) return 0;
vector<long long> S(M);
for (int i = 0; i < M; ++i) {
cin >> S[i];
}
sort(S.begin(), S.end());
vector<long long> L(M);
for (int i = 0; i < M - 1; ++i) {
L[i] = S[i+1] - S[i];
}
L[M-1] = N + S[0] - S[M-1];
long long max_val = 0;
if (N % 2 == 0) {
for (long long len : L) {
max_val = max(max_val, len / 2);
}
} else {
for (long long len : L) {
max_val = max(max_val, (len - 1) / 2);
}
}
long long D;
if (N % 2 == 0) {
D = N / 2 - max_val;
} else {
D = (N - 1) / 2 - max_val;
}
long long P = D * 360;
long long Q = N;
long long g = std::gcd(P, Q);
P /= g;
Q /= g;
cout << P << "/" << Q << "\n";
return 0;
}
この解説は gemini-3.5-flash-thinking によって生成されました。
posted:
last update: