Official

B - Pizza Editorial by physics0523


ひとまず、ピザではなく切れ込み(を入れる包丁)を回転させることを考えましょう。
「前に切れ込みを入れた場所から、ピザを時計回りに \(D\) 度回した位置に切れ込みを入れる」は「前に切れ込みを入れた場所から、包丁を反時計回りに \(D\) 度回した位置に切れ込みを入れる」と言い換えられます。
この言い換えのもとで、切れ込みの入り方は以下のようになります。

  • \(1\) つ目の切れ込みは、最初の位置から包丁を反時計回りに \(0\) 度回した位置に切れ込みが入る。
  • \(2\) つ目の切れ込みは、最初の位置から包丁を反時計回りに \(A_1\) 度回した位置に切れ込みが入る。
  • \(3\) つ目の切れ込みは、最初の位置から包丁を反時計回りに \((A_1+A_2) \% 360\) ( \(a\%b\)\(a\)\(b\) で割った余り)度回した位置に切れ込みが入る。
  • \(4\) つ目の切れ込みは、最初の位置から包丁を反時計回りに \((A_1+A_2+A_3) \% 360\) 度回した位置に切れ込みが入る。
  • \(\dots\)

これにより、「最初の位置から包丁を反時計回りに \(k\) ( \(k\)\(0\) 以上 \(360\) 未満の整数)度回した位置に切れ込みが入っているか?」という情報を求めていきます。これは例えばループと配列を使えば可能です。
その後、切り分けられたピザのそれぞれの大きさを求めていきます。例えば、 切れ込みの入っている角度が順に \(0,120,180\) であれば、 \(120-0=120\) 度のものと \(180-120=60\) 度のもの、 \(360-180=180\) 度(ここで、 \(0\) 度に入った切れ込みは「 \(360\) 度にも切れ込みが入っている」とみなせることに注意してください)のものが存在することになります。
当たり前ですが、一番最初に切れ込みを入れた場所、すなわち最初の位置から包丁を反時計回りに \(0\) 度回した位置には確実に切れ込みが入っています。なので、この位置を起点として実装をすれば実装量が削減できます。

実装例(C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<bool> fl(360,false);
  fl[0]=true;
  int p=0;
  for(int i=0;i<n;i++){
    int a;
    cin >> a;
    p+=a;p%=360;
    fl[p]=true;
  }
  int res=0,cur=0;
  for(int i=0;i<=360;i++){
    if(fl[i%360]){
      res=max(res,cur);
      cur=0;
    }
    cur++;
  }
  cout << res << '\n';
}

posted:
last update: