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: