結果
| 問題 |
No.45 回転寿司
|
| ユーザー |
 arishiki
|
| 提出日時 | 2016-04-06 16:01:49 |
| 言語 | C90 (gcc 12.3.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 5,000 ms |
| コード長 | 4,661 bytes |
| コンパイル時間 | 1,299 ms |
| コンパイル使用メモリ | 24,436 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-12-27 13:05:43 |
| 合計ジャッジ時間 | 2,866 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 30 |
コンパイルメッセージ
main.c: In function ‘main’:
main.c:57:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
57 | scanf("%d", &N);
| ^~~~~~~~~~~~~~~
main.c:65:23: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
65 | for(i=2;i<=N+1;i++) scanf("%d", V+i);
| ^~~~~~~~~~~~~~~~
ソースコード
#include <stdio.h>
/* ルールの説明がわかりにくいが、
間を1個以上開けた上昇列として指定し、
和が最大になるようにする*/
/* 間は1個開けるか2個開けるかどっちか。
なぜなら、3つ以上開ける時、その真ん中にあるやつを他を変えずに取れるから。*/
/* 最初の2個のうち、どちらかはとることになる*/
/* 寿司の基本定理
-*-の方が*-*より大きい
ならば真ん中は必ず採用
*/
/*
*--*-*-*-*-*-*--*
*-*-*-*-*-*-*-*-*
2空けが2回以上出てくる時、
必ずこのパターン。
*/
/*
*-*-*--*-*-*--*
*-*-*-*-*-*-*-*
*--*-*-*--*
*-*-*-*-*-*
*--*-*--*--*
*-*-*-*-*
*--*-*--*
*-*-*-*
*--*--*
*-*-*-*-*
*--*-*--*
*/
int mymax(int a, int b);
int sum_1step(int *V, int s, int e);
int maxsushi(int *V, int s, int e);
int guchoku(int *V, int s, int e); /* guchokuは、間隔が2のものが1個以下の
区間の両端を指定すると間隔2が1個か0個と
した時（偶奇に応じて違う）の和を教えてくれる*/
int minkaku(int *K, int s, int e);
/* minkakuは、開始番号と終了番号を指定して、その間にある最初の1が入ってる
番号を返す。なければeを返す。通常はVの最初と最後には1が入っている。*/
int main(void){
int i, f1=0, f2=0, t1, t2, N, all1, two2, s1, start, end, s=0, t=0, l1=0, l2=0, tanten;
scanf("%d", &N);
int V[N+4], K[N+4]; //Kは確定した箇所を入れる。+1は確定、0は未確定。
V[0]=0;
V[1]=0;
V[N+2]=0;
V[N+3]=0;
for(i=2;i<=N+1;i++) scanf("%d", V+i);
K[0]=1;
K[N+3]=1; //最初と最後は定義より確定している。
for(i=1;i<=N+2;i++) K[i]=0;
for(i=2;i<=N+1;i++){
if(V[i]>=V[i-1]+V[i+1])
K[i]=1;
} //基本定理より確定するところは確定させる。
start=0;
tanten=minkaku(K, 1, N+3);
/* start, tanten固定。
s1とendがこの範囲で動く
t1を発見する
sに確定した部分を加える
t1, tantenを固定して
再びs1とendがこの範囲で逆向きに動く
t2を発見する
sに確定した部分を加える
t1, t2をmaxsushiに渡してsに加える
tantenをstartとして新しいtantenを設定
tantenが一番最後に達するまで続ける。
startからtantenまで一切見つからなかった場合、
maxsushiで愚直に計算する。
*/
while(tanten<=N+3 && start<N+3){
t1=start;
t2=tanten;
for(end=start+6;end<=tanten && !(end==tanten-1) && f1==0;end+=2){
for(s1=start;f1==0 && s1+6<=end;s1+=2){
all1=sum_1step(V, s1+2, end-2);
two2=sum_1step(V, s1+3, end-3);
if(two2>all1){
l1=sum_1step(V, start, s1);
t1=s1;
f1=1;
}
}
}
if(f1==1){
/* f1が1じゃないならtantenまで探索して見つかってない時であり
後ろ向きに調べる意味がない
*/
for(s1=tanten-6;t1<=s1 && !(s1==t1+1) && f2==0;s1-=2){
for(end=tanten;f2==0 && s1+6<=end;end-=2){
all1=sum_1step(V, s1+2, end-2);
two2=sum_1step(V, s1+3, end-3);
if(two2>all1){
l1+=sum_1step(V, end, tanten-2);
t2=end;
f2=1;
}
}
}
l1+=maxsushi(V, t1+2, t2-2);
}
s+=mymax(guchoku(V, start, tanten)-V[tanten], l1);
/* f1=1だとしても、ここでguchokuと比べておく必要がある。
なぜなら、f1=1だとしても、この区間で間隔２がちょうど1回の方が
大きくなるかもしれないから。*/
l1=0;
start=tanten;
tanten=minkaku(K, tanten+1, N+3);
f1=0;
f2=0;
}
printf("%d\n", s);
return 0;
}
int mymax(int a, int b){
if(a>b) return a;
else return b;
}
int sum_1step(int *V, int s, int e){
int i, sum=0;
for(i=s;i<=e;i+=2) sum+=V[i];
return sum;
}
int maxsushi(int *V, int s, int e){
int M=e-s+1; //個数
if(M<=0) return 0;
else if(M==1)
return *(V+s);
else if(M==2)
return mymax(*(V+s), *(V+e));
else if(M==3)
return mymax(*(V+s+1), (*(V+s))+*(V+e));
else
return mymax(*(V+s)+maxsushi(V, s+2, e), *(V+s+1)+maxsushi(V, s+3, e));
}
int guchoku(int *V, int s, int e){
int j, M, temp=0, t=0;
if((e-s)%2==0)
return sum_1step(V, s, e);
else{
M=(e-s+1)/2; //間に2の間隔が1個だけ挟まれる場合の両端までにある個数
for(j=1;j<=M-1;j++){ //jは間隔2の前にある個数
temp=sum_1step(V, s, s+(j-1)*2);
temp+=sum_1step(V, s+(j-1)*2+3, e);
t=mymax(t, temp);
}
return t;
}
}
int minkaku(int *K, int s, int e){
int i;
for(i=s;i<=e;i++){
if(K[i]==1)
break;
}
return i;
}