解説
問題整理
- 円柱状ホールケーキ（体積 = 360）に、基準切れ込み（角度 0°）と、追加の切れ込みを基準からの角度
X_i度の位置に入れる（重複しない）。 - すると底面は複数の扇形に分割される。円柱の高さは一定なので、各ピースの体積は扇形の中心角（度数）に等しい（全体 360 に正規化しているため）。
- 人 1 → 2 → … → M → 1 → … の順で、その時点で残っているケーキから 1 ピースずつ取ることを繰り返す。
- 各人が自分の体積総和を最大化するように行動したときの、各人の最終体積を求める。
方針（実装の流れ）
- 角度の集合を作る
基準 0° と 360° を番兵として追加し、X_1...X_Nと合わせてソートする。 - 扇形（ピース）サイズ列を得る
隣接差分を取り、扇形の中心角（=体積）列cakeを得る。 - 取り方の最適化
その時点で取るべき最適手は「最大のピースを取る」 よってcakeを降順ソートし、ans[i % M] += cake[i]とすれば、各手番で最大ピースを取っていった結果と一致する。
計算量
- ソート 2 回（角度列・ピース列）：
O(N log N) - 以降は線形：
O(N + M) - 全体の計算量が となり制約下で十分高速に動作します。
実装例は以下のようになります。