角度に変換するために \(\frac{360}{N}\) を掛けるのは最後にやれば十分なので、\(\max_k d(i,S_k)\) の最小化を考えます。

以下、柱の添字は \(\bmod N\) で考えることにします。

\(D_i:=\max_k d(i,S_k)\) は、全てのベンチが \([i-D_i,i+D_i]\) の範囲に収まっていることを意味します。よって、\(D_i\) を最小化するには、全てのベンチを含む最小の区間が求まれば十分です。そのような区間は明らかに、円周全体から、隣り合うベンチが最も遠い区間を除いたものになります。

よって、\(S_k\) をソートしたうえで \(D'=\max_k d(S_k,S_{k+1})\) とすると、\(\min_i D_i=\left\lceil\frac{N-D'}{2}\right\rceil\) とわかります。これはソートと合わせて \(O(M\log M)\) で求めることができます。

答えを既約分数として出力するには、分子と分母をそれぞれ管理し、最後にそれらの最大公約数で割ればよいです。

実装例 (C++)

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

int main(){
  int n, m;
  cin >> n >> m;
  vector<int> s(m);
  for(int i=0; i<m; i++) cin >> s[i];
  sort(s.begin(), s.end());
  
  int ans = (s[0]+n) - s[m-1];
  for(int i=0; i<m-1; i++){
    ans = max(ans, s[i+1] - s[i]);
  }
  
  long long nume = (long long)(n - ans + 1) / 2 * 360;
  long long deno = n;
  long long g = __gcd(nume, deno);
  nume /= g;
  deno /= g;
  cout << nume << "/" << deno << endl;
}

実装例 (Python)

import math
N, M = map(int, input().split())
S = list(map(int, input().split()))
S.sort()
ans = (S[0]+N) - S[-1]
for i in range(M-1):
  ans=max(ans, S[i+1] - S[i])

nume = (N - ans + 1) // 2 * 360
deno = N
g = math.gcd(nume, deno)
nume //= g
deno //= g
print(f"{nume}/{deno}")