概要

この問題は、円環上に配置された \(N\) 本の柱のうち \(M\) 個のベンチがある位置に対して、ある柱に街灯を設置したときの「ベンチへの最大距離（角度）」を最小化する問題です。

円環上の位置関係を整理し、ベンチが配置されていない「最大の隙間」に着目することで、効率よく最小コストを求めることができます。

---

考察

1. 直感的な理解（円環を直線に引き延ばして考える）

円形の公園を、ベンチがないある1箇所で切り開いて、1本の直線として考えてみましょう。

すべてのベンチを照らすためには、ベンチが存在する範囲をカバーするように街灯を設置する必要があります。 街灯から各ベンチへの最大距離を最小にするには、ベンチが存在する範囲のちょうど中央に街灯を置くのが最適です。

例えば、ベンチが配置されている区間の左端から右端までの距離（柱の数）が \(L\) であるとき、その中央に街灯を置くと、両端のベンチへの距離はほぼ \(\frac{L}{2}\) になります。

2. 「最大の隙間」を見つける

円環において、ベンチが存在する範囲を最も狭く（コンパクトに）するためには、ベンチ同士の間隔が最も広い部分（最大の隙間）を避けて、それ以外の部分をすべてカバーするように街灯を設置すればよいです。

隣り合うベンチの間の隙間のうち、最大のものを \(G\) とします。 このとき、すべてのベンチは、円周 \(N\) から \(G\) を引いた長さ \(L = N - G\) の弧（区間）の中にすべて収まっています。

この長さ \(L\) の区間をカバーするために、区間の中央に街灯を置いたときの、端のベンチまでの最大距離 \(D\)（柱の数ベース）を考えます。

• \(L\) が偶数のとき：中央の柱に置くことで、両端への距離は \(\frac{L}{2}\) となり、最大距離は \(D = \frac{L}{2}\) です。
• \(L\) が奇数のとき：中央の2つの柱のいずれかに置くことで、遠い方の端への距離は \(\frac{L+1}{2}\) となり、最大距離は \(D = \frac{L+1}{2}\) です。

これらは、整数の切り捨て除算を用いると、いずれの場合も次のように1つの式で表せます。 $\(D = \lfloor \frac{N - G + 1}{2} \rfloor\)$

3. 具体例で考える

\(N = 10\) で、ベンチが \(1, 4\) の位置にあるとします（\(M = 2\)）。

• ベンチの間隔は以下の2つです：
  • \(1\) と \(4\) の間： \(4 - 1 = 3\)
  • \(4\) と \(1\) の間（円環のつなぎ目）： \(10 - 4 + 1 = 7\)
• 最大の隙間は \(G = 7\) です。
• ベンチが含まれる最小の区間の長さは \(L = N - G = 10 - 7 = 3\) です（ベンチ \(1\) から \(4\) までの区間）。
• この区間の中心付近である柱 \(2\) または \(3\) に街灯を置きます。
  • 街灯を \(2\) に置いたとき、ベンチ \(1\) への距離は \(1\)、ベンチ \(4\) への距離は \(2\) となり、最大距離は \(D = 2\) です。
• 式に当てはめると、 \(D = (10 - 7 + 1) // 2 = 2\) となり、一致します。

4. 角度と分数への変換

求めたいコストは、この最小の最大距離 \(D\) に \(\frac{360}{N}\) を掛けた値です。 $\(\text{コスト} = D \times \frac{360}{N} = \frac{360 \times D}{N}\)$

この値を既約分数の形で出力するため、分子 \(P' = 360 \times D\)、分母 \(Q' = N\) とし、これらの最大公約数（GCD）でそれぞれを割ることで、答えとなる P/Q を得ることができます。

---

アルゴリズム

1. 特殊なケースの処理:
   • ベンチが \(1\) つだけ（\(M = 1\)）の場合、そのベンチと同じ位置に街灯を置けばコストは \(0\) になるため、0/1 を出力して終了します。
2. ソート:
   • ベンチの位置 \(S\) を昇順にソートします。
3. 隣り合うベンチの間隔の最大値 \(G\) を計算:
   • ソートされた配列の隣り合う要素の差 \(S_{i+1} - S_i\) を計算します。
   • 円環のつなぎ目（最後のベンチ \(S_{M-1}\) と最初のベンチ \(S_0\) の間隔） \(N - S_{M-1} + S_0\) も計算します。
   • これらのうちの最大値を \(G\) とします。
4. 最小の最大距離 \(D\) を計算:
   • \(D = (N - G + 1) // 2\) を計算します。
5. 既約分数への変換と出力:
   • 分子 \(P' = 360 \times D\)、分母 \(Q' = N\) とします。
   • \(g = \gcd(P', Q')\) を求め、 \(P = P' / g\)、 \(Q = Q' / g\) として、P/Q の形式で出力します。

---

計算量

• 時間計算量: \(O(M \log M)\)

  • ベンチの位置のソートに \(O(M \log M)\) かかります。
  • 隣り合う間隔の計算は \(O(M)\)、最大公約数の計算（ユークリッドの互除法）は \(O(\log N)\) です。
  • \(M \le 2 \times 10^5\) であるため、制限時間内に十分高速に動作します。

• 空間計算量: \(O(M)\)

  • ベンチの位置を格納する配列 \(S\) のために \(O(M)\) のメモリを使用します。

---

実装のポイント

• 円環のつなぎ目の処理: ソートされた配列において、最後の要素 \(S[-1]\) と最初の要素 \(S[0]\) の間の距離は \(N - S[-1] + S[0]\) で求められます。これを忘れると、円環ではなく直線の問題になってしまうため注意が必要です。

• 最大公約数（GCD）の利用: Pythonでは math.gcd を使うことで、簡単に分数を既約分数に直すことができます。

  ソースコード

import sys
import math

def solve():
    # 入力を高速に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    S = [int(x) for x in input_data[2:]]
    
    if M == 1:
        print("0/1")
        return
    
    # ベンチの位置をソート
    S.sort()
    
    # 隣り合うベンチの最大の間隔を求める
    max_gap = 0
    for i in range(M - 1):
        gap = S[i+1] - S[i]
        if gap > max_gap:
            max_gap = gap
    # 円環のつなぎ目の間隔
    gap = N - S[-1] + S[0]
    if gap > max_gap:
        max_gap = gap
        
    # 最小の最大距離 D
    D = (N - max_gap + 1) // 2
    
    # コストは D * 360 / N
    P_prime = 360 * D
    Q_prime = N
    
    # 既約分数にする
    g = math.gcd(P_prime, Q_prime)
    P = P_prime // g
    Q = Q_prime // g
    
    print(f"{P}/{Q}")

if __name__ == '__main__':
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。