概要

ベンチがある柱すべてに対して「ずれ角（＝円周上の最短距離）」の最大値が最小になるように、街灯の正面方向（柱番号）を選ぶ問題です。
結論として「ベンチが存在しない最大の空き区間」を見つけ、その反対側の弧を半分にした値が最小コストになります。

考察

重要な気づき 1：角度ではなく「柱間距離（何本ぶん）」で考える

ずれ角は
\(d(i,j)\times \frac{360}{N}\) 度
なので、最小化すべき本質は \(d(i,S_k)\) の最大値（何本ぶん離れているか）です。最後に \(\frac{360}{N}\) を掛ければよいです。

重要な気づき 2：「全ベンチを含む最短の弧」を考える

ある柱 \(i\) を正面にして最大距離が \(r\)（本）であるとは、全ベンチが「\(i\) から左右に \(r\) 本以内」に入ることを意味します。
つまり、円周上で見れば 長さ \(2r\)（本）以内の1つの弧の中に全ベンチが収まる必要があります。

逆に、もし全ベンチがある弧（連続区間）長 \(L\)（本）に収まるなら、その弧の真ん中あたりの柱を正面に選べば最大距離はだいたい半分で済み、最小の最大距離は
\(r=\left\lceil \frac{L}{2}\right\rceil\)
になります（柱番号は整数なので切り上げが必要）。

よって問題は： - 全ベンチを含む弧の長さ \(L\) を最小化し、 - 答えを \(r=\lceil L/2\rceil\) にする

に変わります。

重要な気づき 3：最短の弧は「最大ギャップの反対側」

ベンチの位置を円周に沿ってソートし、隣り合うベンチ間の間隔（時計回り）を考えます。
このとき、ベンチが無い区間のうち 最も長い区間（最大ギャップ） を \(G\) とすると、そこを「切れ目」として円を開いた残りが、全ベンチを含む最短の弧になります。

• 円周全体の長さ：\(N\)
• 最大ギャップ：\(G\)
• 全ベンチを含む最短弧の長さ：\(L_{\min}=N-G\)

したがって最小最大距離は
\(r=\left\lceil \frac{L_{\min}}{2}\right\rceil\)

具体例

\(N=10\)、ベンチが \(\{2,4,9\}\) のとき（ソート済み）
ギャップは - \(4-2=2\) - \(9-4=5\) - 巻き戻り \(10+2-9=3\)

最大ギャップ \(G=5\)
\(L_{\min}=10-5=5\)
\(r=\lceil 5/2\rceil=3\)
よって最小ずれ角は \(3\times 360/10=108\) 度。

素朴解がダメな理由

柱の候補は \(N\) 通り（最大 \(10^9\)）あり、全探索は不可能です。
しかしベンチ数 \(M\) は最大 \(2\times 10^5\) なので、「ベンチ間のギャップ」だけを見れば \(O(M\log M)\) で解けます。

アルゴリズム

1. ベンチ位置配列 \(S\) をソートする。
2. 隣接するベンチ間のギャップ \(S[i+1]-S[i]\) を走査し最大値を取る。
3. 最後と最初の巻き戻りギャップ \(N+S[0]-S[-1]\) も比較して最大ギャップ \(G\) を得る。
4. \(L_{\min}=N-G\) とし、\(r=\lceil L_{\min}/2\rceil = (L_{\min}+1)//2\) を計算する。
5. 答えの角度は \(\dfrac{r\cdot 360}{N}\)。分数を \(\gcd\) で約分して P/Q 形式で出力する。
6. \(M=1\) のときは、正面をその柱に合わせればよいので \(r=0\)（答えは 0/1）。

計算量

• 時間計算量: \(O(M\log M)\)（ソートが支配的）
• 空間計算量: \(O(M)\)（ベンチ位置を保持）

実装のポイント

• 巻き戻りギャップ \(N+S[0]-S[-1]\) を忘れると円形が扱えず WA になります。

• 最小最大距離は整数本数なので、\(r=\lceil L/2\rceil\) を (L+1)//2 で計算します。

• 最終出力は \(\dfrac{r\cdot 360}{N}\) を必ず既約分数にします（gcd で約分）。

  ソースコード

import sys
from math import gcd

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, M = data[0], data[1]
    S = data[2:2+M]
    S.sort()

    if M == 1:
        r = 0
    else:
        max_gap = 0
        for i in range(M - 1):
            gap = S[i + 1] - S[i]
            if gap > max_gap:
                max_gap = gap
        wrap_gap = N + S[0] - S[-1]
        if wrap_gap > max_gap:
            max_gap = wrap_gap

        L_min = N - max_gap
        r = (L_min + 1) // 2  # ceil(L_min/2)

    num = r * 360
    if num == 0:
        print("0/1")
        return
    den = N
    g = gcd(num, den)
    num //= g
    den //= g
    print(f"{num}/{den}")

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。