piece-of-cake

解説

問題整理

• 円柱状ホールケーキ（体積 = 360）に、基準切れ込み（角度 0°）と、追加の切れ込みを基準からの角度 X_i 度の位置に入れる（重複しない）。
• すると底面は複数の扇形に分割される。円柱の高さは一定なので、各ピースの体積は扇形の中心角（度数）に等しい（全体 360 に正規化しているため）。
• 人 1 → 2 → … → M → 1 → … の順で、その時点で残っているケーキから 1 ピースずつ取ることを繰り返す。
• 各人が自分の体積総和を最大化するように行動したときの、各人の最終体積を求める。

方針（実装の流れ）

1. 角度の集合を作る
   基準 0° と 360° を番兵として追加し、X_1...X_N と合わせてソートする。
2. 扇形（ピース）サイズ列を得る
   隣接差分を取り、扇形の中心角（=体積）列 cake を得る。
3. 取り方の最適化
   その時点で取るべき最適手は「最大のピースを取る」 よって cake を降順ソートし、ans[i % M] += cake[i] とすれば、各手番で最大ピースを取っていった結果と一致する。

計算量

• ソート 2 回（角度列・ピース列）：O(N log N)
• 以降は線形：O(N + M)
• 全体の計算量が $O(NlogN + M)$ となり制約下で十分高速に動作します。

実装例は以下のようになります。