Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/411-9b70d71f
この記事にトラックバックする(FC2ブログユーザー)

Aizu 0517 - Longest Steps (最長の階段) (この記事を編集する[管理者用])

Source
第7回 日本情報オリンピック本選問題 2007年02月12日
Aizu 0517

問題概要
問題文が日本語なので省略.

解法
入力の零の数zを覚えて置いて,間に入ってないカードの数がzを超えない区間の最長を尺取りメソッドで求めれば良い.

C言語によるスパゲッティなコード
#include<stdio.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main(){
  int i,j,k,l,m,n,z;
  int sum[100010],st,ed,res;

  for(;;){
    scanf("%d%d",&n,&k); if(!n)break;
    z=0;
    rep(i,n+1) sum[i]=1; sum[0]=0;
    rep(i,k){
      scanf("%d",&j);
      if(!j) z++; else sum[j]=0;
    }
    rep(i,n) sum[i+1]+=sum[i];

    res=0; st=0; ed=0;
    while(ed<=n){
      if(sum[ed]-sum[st] > z) st++;
      if(ed-st > res) res = ed-st;
      ed++;
    }

    printf("%d\n",res);
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/411-9b70d71f
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。