らての精進日記

修行をします

aoj0517:Longest Steps

解法

連続しているカードの区間をすべて見る。もし白紙のカードを持っているなら、今見ている区間と一つ前に見た区間をつなげられるかということも考慮する。

コード

#include<bits/stdc++.h>
using namespace std;

int N,K;
bool f[100000];
void solve(){
    fill_n(f,N,false);
    bool white=false;
    for(int i=0;i<K;i++){
        int a;scanf("%d",&a);
        if(a)f[--a]=true;
        else white=true;
    }
    int ma=0;
    int prev=0,cur=0,val=0;

    while(cur<N){
        if(!f[cur]){cur++;continue;}
        int next=cur;
        while(next<N&&f[next])next++;
        int x=next-cur;
        if(white&&prev+1==cur)x+=val+1;
        ma=max(ma,x);
        val=next-cur;
        prev=next;
        cur=next;
    }

    printf("%d\n",ma);
}
int main(){
    while(scanf("%d%d",&N,&K),N||K)solve();

    return 0;
}
広告を非表示にする