Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 238 B問題 Pizza

AtCoder ABC ABC238 B問題 200 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

円形のピザがある. このピザの半径上に固定されたナイフがある. A=(A_1, \dots, A_N) に対して, 以下のようにしてピザを分割する.

  • ナイフで切り込みを入れる.
  • i=1,2, \dots, N に対して以下を行う: A_i 度時計回りに回転させた後, ナイフで切れ込みを入れる.

一番大きいピザの中心角は何度か?

制約

  • 1 \leq N \leq 359
  • 1 \leq A_i \leq 359
  • 同じところに複数回切れ込みは入らない.

解法

i 回目に切れ込みを入れたとき, 最初から B_i 度だけ回転させた部分とする. このとき,

B_0=0, \quad B_i=(B_{i-1}+A_i) \pmod{360}

が成り立つ.

そして, C_0, C_1, C_2, \dots, C_{N+1} を B_0, B_1, B_2, \dots, B_N, 360 を昇順に並び替えた列とする. ここで, 360 が入っているのは, 0 度と 360 度は同じ部分を表しており, 最初に切れ込みを入れているからである. このとき, 求めるべき答えは \displaystyle \max_{j=1,2, \dots, N+1} (C_j-C_{j-1}) である.