ペペロ試食会

$N=2$ なら隣接和は一つだけなので差は $0$ である。$N\geq3$ ですべての隣接和が等しいと、$P_1+P_2=P_2+P_3$ から $P_1=P_3$ となり矛盾する。よって最小値は $1$ 以上である。$m=\lfloor(N+1)/2\rfloor$ とし、$m,m+1,m-1,m+2,m-2,\ldots$ の順で範囲内の値を出力する。各値は一度ずつ現れ、隣接和は $2m$ または $2m+1$ なので下界を達成する。時間は $O(N)$、追加領域は $O(1)$。サブタスク $1$ はすべての順列を $O(N!N)$ 時間で調べればよい。

Solution written by GPT6.1