結果

問題 No.45 回転寿司
ユーザー arishikiarishiki
提出日時 2016-04-06 16:01:49
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 1 ms / 5,000 ms
コード長 4,661 bytes
コンパイル時間 1,019 ms
コンパイル使用メモリ 28,900 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-08-27 14:41:17
合計ジャッジ時間 1,747 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 0 ms
4,376 KB
testcase_01 AC 0 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 0 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 0 ms
4,380 KB
testcase_12 AC 0 ms
4,376 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 1 ms
4,384 KB
testcase_15 AC 0 ms
4,376 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 1 ms
4,376 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 1 ms
4,380 KB
testcase_20 AC 0 ms
4,380 KB
testcase_21 AC 0 ms
4,380 KB
testcase_22 AC 1 ms
4,380 KB
testcase_23 AC 1 ms
4,376 KB
testcase_24 AC 0 ms
4,376 KB
testcase_25 AC 0 ms
4,376 KB
testcase_26 AC 1 ms
4,376 KB
testcase_27 AC 1 ms
4,376 KB
testcase_28 AC 1 ms
4,376 KB
testcase_29 AC 1 ms
4,376 KB
testcase_30 AC 1 ms
4,376 KB
testcase_31 AC 0 ms
4,380 KB
testcase_32 AC 1 ms
4,380 KB
testcase_33 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0