公式
B - 円形公園の街灯 / Street Lights in a Circular Park 解説 by admin
Claude 4.6 Opus (Thinking)概要
円形に配置された \(N\) 本の柱のうち \(M\) 本にベンチがある。円の中心に設置する街灯の正面方向を最適に選び、全ベンチに対するずれ角の最大値を最小化する問題。離散円上の1-center問題に帰着される。
考察
問題の言い換え
ずれ角は \(d(i, S_k) \times \frac{360}{N}\) で計算され、\(\frac{360}{N}\) は定数なので、本質的には以下を最小化すれば良い：
\[\min_{i} \max_{1 \leq k \leq M} d(i, S_k)\]
ここで \(d(i, j) = \min(|i-j|, N - |i-j|)\) は円上の距離。
最大ギャップに着目する
ベンチの位置を円上でソートすると、隣接するベンチ間に「ギャップ」（ベンチのない区間）が生じます。
重要な観察: 最大ギャップ \(G_{\max}\) の反対側（ベンチが密集する側）の弧の長さ \(\text{span} = N - G_{\max}\) に対して、その弧の中央に街灯を向ければ、最も遠いベンチまでの距離が最小化されます。
具体例: \(N=8\), ベンチが位置 \(0, 1, 3\)（0-indexed）にある場合。 - ギャップ: \(1, 2, 5\)。最大ギャップ \(G_{\max} = 5\)。 - \(\text{span} = 8 - 5 = 3\)。中央に置くと \(D = \lceil 3/2 \rceil = 2\)。 - 柱1に設定: \(d(1,0)=1, d(1,1)=0, d(1,3)=2\)。最大 \(= 2\)。✓
なぜ最大ギャップを使うのか
街灯から最も遠いベンチは、街灯の「反対側」にあるベンチです。最大ギャップ側を「背面」にすれば、全ベンチが最も短い弧に収まり、最大距離を最小にできます。
離散性の考慮
\(\text{span}\) が偶数なら完全に中央に置けて \(D = \text{span}/2\)。奇数ならちょうど中央に柱がないので、\(D = \lceil \text{span}/2 \rceil = (\text{span}+1)/2\) となります。
アルゴリズム
- ベンチの位置を0-indexedに変換してソート
- 隣接ベンチ間のギャップを計算（巡回的に最後→最初も含む）
- 最大ギャップ \(G_{\max}\) を求める
- \(\text{span} = N - G_{\max}\), \(D = \lceil \text{span} / 2 \rceil\)
- 答え \(= D \times \frac{360}{N} = \frac{360D}{N}\) を既約分数で出力
計算量
- 時間計算量: \(O(M \log M)\)（ソートがボトルネック）
- 空間計算量: \(O(M)\)
実装のポイント
巡回ギャップ（最後のベンチから最初のベンチへの距離 \(= N - p_{M-1} + p_0\)）を忘れずに計算する
\(\frac{360D}{N}\) を既約分数にするため、\(\gcd(360D, N)\) で割る
\(D = 0\)（\(M=1\) で街灯をそのベンチの柱に向ける場合）のとき
0/1を出力する\(N\) が最大 \(10^9\) と大きいが、計算自体は \(O(M)\) で完結するため問題なし
ソースコード
import sys
from math import gcd
def solve():
input_data = sys.stdin.buffer.read().split()
N = int(input_data[0])
M = int(input_data[1])
S = [int(input_data[i + 2]) for i in range(M)]
# Convert to 0-indexed positions on the circle
# Position of bench k is S_k - 1 (0-indexed), on a circle of size N
# d(i, j) = min(|i-j| mod N, N - |i-j| mod N) but with 0-indexed:
# d(i, j) = min((i-j) % N, (j-i) % N)
# We want to find i (0..N-1) that minimizes max over all benches of d(i, bench)
# where d(i, bench) = min((i - bench) % N, (bench - i) % N)
#
# The cost is d_max * 360 / N, so we need to minimize d_max.
# d_max = max_k min((i - s_k) % N, (s_k - i) % N) = max_k (N/2 - |((s_k - i) % N) - N/2|)
# Actually, d(i, s_k) = min((s_k - i) % N, N - (s_k - i) % N)
# which equals min(x, N-x) where x = (s_k - i) % N, and this is at most N//2.
# Sort bench positions (0-indexed)
positions = sorted([(s - 1) % N for s in S])
# For a given candidate direction i, d(i, s) = min((s-i)%N, (i-s)%N)
# We want to minimize over i: max over all s of d(i,s).
# Binary search on d_max. For a given threshold D, we need:
# For all benches s_k: d(i, s_k) <= D
# i.e., min((s_k - i) % N, (i - s_k) % N) <= D
# This means i is within distance D of s_k on the circle.
# Each bench covers an arc of positions [s_k - D, s_k + D] (mod N).
# We need the intersection of all M arcs to be non-empty.
# The intersection of arcs on a circle:
# Sort positions. Each arc is [s_k - D, s_k + D].
# The intersection is non-empty iff:
# For the sorted positions, the "spread" when looking at contiguous coverage:
# Actually, the intersection of all arcs [s_k - D, s_k + D] is non-empty iff
# there exists a point covered by all arcs.
# Equivalently, for sorted positions p_0 <= p_1 <= ... <= p_{M-1},
# we need: for some i, all positions are within distance D of i.
# This means max_k d(i, p_k) <= D.
# The optimal i minimizes max_k d(i, p_k).
# On a circle, the optimal i is the "midpoint" of the largest gap's complement.
#
# Think of it differently: sorted positions on circle.
# For each consecutive pair in sorted order (including wrap-around),
# consider the arc that does NOT contain the gap. The "radius" needed
# is ceil(arc_length / 2) where arc_length = N - gap.
#
# Actually: the minimum d_max = min over all "starting points" of
# the maximum distance. With sorted positions, consider the M arcs
# between consecutive benches. For each gap g between consecutive benches,
# the complementary arc has length N - g. The optimal point placed in
# the middle of that complementary arc needs radius ceil((N-g)/2) if integer,
# or (N-g)/2 exactly.
#
# Wait - we want the minimum of max d. The answer is:
# min over gaps of ceil_half(N - gap_size), but we can pick any i, not just integer.
# But i must be an integer (a pillar position).
#
# For sorted positions, gaps between consecutive (circular),
# the span = N - gap. The needed D = ceil((span - 1) / 2) if span > 0...
# Hmm let me think more carefully with the discrete circle.
# span of benches when gap g is the "back gap" = N - g
# We need D such that all benches fit within distance D of some integer point.
# Min D = ceil((span) / 2) where span = max circular distance among benches when optimally centered.
# Actually: for a set of points on circle, min max_d = min over all arcs containing all points of ceil(arc_length/2).
# Arc containing all points: N - max_gap. So min D_integer = ceil((N - max_gap) / 2) ... but with floor.
# The minimum of max d(i, s_k) over integer i = floor of (N - max_gap) / 2...
# Hmm, let me just think: if the max gap is G, the points span N-G around the circle.
# Place i at the midpoint: D = ceil((N-G-1)/2) if N-G >= 1...
# Actually it should be floor((N-G)/2).
# Let me reconsider. Positions sorted: p0 < p1 < ... < p_{M-1}.
# Gaps: p1-p0, p2-p1, ..., N - p_{M-1} + p_0.
# If we remove the largest gap G, the remaining arc has length N - G.
# Place i at midpoint. The farthest bench is at distance floor((N-G)/2) if we choose optimally.
# Answer D = floor((N-G)/2). But need to be careful.
# span = (last - first) on the arc = N - G - (M-1)... no.
# If gap G is between p_a and p_{a+1}, the benches on the other side span from p_{a+1} to p_a (going the other way).
# Arc length = N - G. Benches at relative positions 0, d1, d1+d2, ..., sum = N - G.
# Farthest from center of this arc: center is at relative position (N-G)/2.
# Actually no: farthest bench from any integer point i.
# The endpoints of the bench set are at relative positions 0 and N-G (on the arc).
# Wait the arc is from p_{a+1} to p_a going the short way (not through the gap).
# Leftmost bench: p_{a+1}, rightmost: p_a + N (or equivalently p_a on the other side).
# Distance from leftmost to rightmost along this arc: N - G.
# But N - G counts edges, not the benches. The "span" in terms of circle distance = N - G.
# Wait no. If gap from p_a to p_{a+1} (clockwise) is G, then going the other way from p_{a+1} to p_a is N - G.
# The first bench clockwise after the gap is p_{a+1}, the last bench before the gap is p_a.
# Clockwise distance from p_{a+1} to p_a (not through gap) = N - G.
#
# If we place i optimally, the max distance to these endpoints should be minimized.
# The two extreme benches are at clockwise distance 0 and N-G from p_{a+1}.
# Best i: at clockwise distance (N-G)/2 from p_{a+1}.
# If N-G is even, D = (N-G)/2 exactly (integer point exists).
# If N-G is odd, D = (N-G+1)/2 = ceil((N-G)/2) since we must pick integer.
# Wait: d(i, p_{a+1}) = (N-G)/2 and d(i, p_a) = (N-G)/2. But also other benches
# in between might be further? No, they're between the extremes so they're closer.
#
# But we also need i to be at distance <= D from ALL benches. The farthest ones
# from the midpoint are the two endpoints. Others are between. So D = ceil((N-G)/2)...
# Actually floor: if N-G even, D=(N-G)/2. If odd, we need (N-G+1)/2.
# Hmm: positions 0 and 5 on circle of N=10. Midpoint at 2 or 3. d(2,0)=2, d(2,5)=3. d(3,0)=3, d(3,5)=2. So D=3 = ceil(5/2).
# With (N-G)=5: ceil(5/2)=3. Yes.
# So D_min = ceil((N - G_max) / 2) where G_max is the largest gap.
# But wait, we want min over all gaps? No: we pick the largest gap to remove,
# because that minimizes N - G, hence minimizes D.
# D_min = ceil((N - G_max) / 2)
# But actually: what if there are multiple large gaps? We still remove only one (the largest).
# But couldn't we choose i to be in a position that's not the midpoint of the complement of the largest gap?
# No - the optimal is always to remove the largest gap and center.
# Hmm wait, that's actually not always true on discrete circles with M > 2. Let me reconsider...
# Actually it is: the set of benches lies in some arc. The smallest such arc is obtained
# by choosing the largest gap as the "outside". Then centering in that arc gives the minimum max distance.
# So: find the maximum gap G_max among consecutive bench pairs (circular).
# Answer D = ceil((N - G_max) / 2).
# But we could also have ties or the ceil might not give the best if there's a
# perfect centering with a smaller gap removed... Actually no, largest gap is always best.
# Wait, I realize there could be subtlety: ceil((N-G)/2) might equal the same
# for different gaps if they're close. But we want the minimum D, so we want G as large as possible.
# Let me verify with a simple example:
# N=8, M=2, benches at 1,5 (0-indexed: 0,4)
# Gaps: 4, 4. G_max = 4. N-G=4. ceil(4/2)=2. D=2.
# Cost = 2 * 360/8 = 90. That makes sense: place light at pillar 2 or 6, max dist = 2.
# N=6, M=3, benches at 1,2,4 (0-indexed: 0,1,3)
# Sorted: 0,1,3. Gaps: 1, 2, 3. G_max=3. N-G=3. ceil(3/2)=2. D=2.
# Cost = 2*360/6 = 120.
# Check: place at 1 (0-indexed). d(1,0)=1, d(1,1)=0, d(1,3)=2. Max=2. ✓
# Place at 2 (0-indexed). d(2,0)=2, d(2,1)=1, d(2,3)=1. Max=2. ✓
# So the answer cost = D_min * 360 / N where D_min = ceil((N - G_max) / 2).
#
# Let span = N - G_max.
# D_min = (span + 1) // 2 if span is odd, span // 2 if span is even.
# = (span + 1) // 2 ... wait no. ceil(span/2) = (span + 1) // 2.
#
# Hmm wait, for span=4: ceil(4/2)=2=(4+1)//2=2. For span=5: ceil(5/2)=3=(5+1)//2=3. OK.
# But actually I need to double-check: is it ceil(span/2) or floor(span/2)?
# span = N - G_max = distance from first to last bench going the short way.
# But it's the number of "edges" not "vertices" between the extreme benches.
#
# Example: benches at 0 and 4 on circle of 8. span = 8 - 4 = 4.
# Midpoint at 2. d(2, 0) = 2, d(2, 4) = 2. D = 2 = span/2. ✓
#
# Example: benches at 0 and 3 on circle of 8. Gaps: 3, 5. G_max=5. span=3.
# Midpoint: 0 + 1.5 → choose 1 or 2.
# d(1, 0)=1, d(1, 3)=2. D=2.
# d(2, 0)=2, d(2, 3)=1. D=2.
# ceil(3/2) = 2. ✓
# So answer = ceil((N - G_max) / 2) * 360 / N.
#
# But wait! I also need to consider that multiple gaps could yield the same or
# better result depending on parity. No, G_max is the unique best choice.
# Actually wait, I want to reconsider the problem more carefully.
#
# We have M bench positions. We want to choose integer i to minimize max_k d(i, S_k).
# This is equivalent to: find a point on the discrete circle that minimizes the
# maximum distance to any bench.
# This is the 1-center problem on a discrete circle.
#
# The answer is: find the largest "gap" (empty arc) between consecutive benches,
# remove it, and center in the remaining arc. The max distance is ceil(span/2)
# where span = N - gap.
# Actually, I realize I should also check: what if the optimal i coincides with one
# of the positions adjacent to the midpoint? There might be multiple gaps and
# the answer might be better with a different configuration. But no, for the
# 1-center problem on a circle, the answer is always determined by the largest gap.
# Let me also handle edge case M=1: only one bench. Then we can place i = S_1,
# and D = 0. G_max = N (the gap wrapping all the way around).
# span = N - N = 0. ceil(0/2) = 0. ✓
# And M=N: all pillars have benches. D = floor(N/2). G_max = 1 (each gap is 1).
# span = N - 1. ceil((N-1)/2). For N=4: ceil(3/2)=2. d max = 2.
# Check: N=4, benches at 0,1,2,3. Place at 0: d(0,2)=2. Yes. ✓
# OK so the algorithm is:
# 1. Sort bench positions (0-indexed).
# 2. Find the maximum gap between consecutive benches (including wrap-around).
# 3. span = N - max_gap.
# 4. D_min = ceil(span / 2) = (span + 1) // 2.
# Wait: when span is 0, D_min = 0. (span+1)//2 = 0 for span=0? No, (0+1)//2 = 0. ✓
# When span is 1 (two adjacent benches, largest gap = N-1), D_min should be...
# Wait M=2 benches adjacent: positions 0 and 1. Gaps: 1 and N-1. G_max = N-1. span = 1.
# D_min = ceil(1/2) = 1. Place at 0: d(0,0)=0, d(0,1)=1. Max=1.
# Place at 1: d(1,0)=1, d(1,1)=0. Max=1. So D=1 is correct. (1+1)//2 = 1. ✓
# Hmm wait, I realize there may be an issue. Let me reconsider.
#
# Actually, I think I might be wrong about ceil vs floor. Let me think again.
#
# benches at positions a and b on the circle (0-indexed), with a < b.
# gaps: b - a and N - (b - a). Suppose gap = N - (b - a) is larger, so G_max = N - (b-a).
# span = N - G_max = b - a.
# The benches span from a to b (clockwise).
# Optimal i: a + span/2 = a + (b-a)/2.
# If span even: i = a + span/2. d(i, a) = span/2, d(i, b) = span/2. D = span/2.
# If span odd: i = a + (span-1)/2 or a + (span+1)/2.
# For i = a + (span-1)/2: d(i,a) = (span-1)/2, d(i,b) = (span+1)/2. D = (span+1)/2.
# For i = a + (span+1)/2: d(i,a) = (span+1)/2, d(i,b) = (span-1)/2. D = (span+1)/2.
# So D = ceil(span/2). ✓
#
# But with more than 2 benches, intermediate benches are all within the span,
# so they're all within distance ceil(span/2) of the center. ✓
# Great. So answer = ceil(span / 2) * 360 / N.
# where span = N - G_max.
# Now I need to output as reduced fraction P/Q.
# answer = ceil(span/2) * 360 / N
# ceil(span/2) = (span + 1) // 2 when span is odd, span // 2 when span is even.
#
# Let D = ceil(span/2). Actually, D is an integer.
# answer = D * 360 / N = 360 * D / N.
# Reduce: g = gcd(360 * D, N). P = 360*D/g, Q = N/g.
# But simpler: g = gcd(360*D, N). Or just P = 360*D, Q = N, then reduce.
positions.sort()
# Compute gaps
max_gap = 0
for idx in range(M):
if idx + 1 < M:
gap = positions[idx + 1] - positions[idx]
else:
gap = N - positions[idx] + positions[0]
if gap > max_gap:
max_gap = gap
span = N - max_gap
D = (span + 1) // 2 # ceil(span / 2)
# Answer = 360 * D / N as a reduced fraction
P = 360 * D
Q = N
if P == 0:
print("0/1")
else:
g = gcd(P, Q)
print(f"{P // g}/{Q // g}")
solve()
この解説は claude4.6opus-thinking によって生成されました。
投稿日時:
最終更新: