読者です 読者をやめる 読者になる 読者になる

AOJ Problem 0517 : Longest Steps

JOI本選に向けて過去問を解きまくる。

404 Not Found

白紙が1つだけということに注目する。もしひとつじゃなかったらしゃくとり法等で解くことが必要になるが、今回の場合はそうじゃないので、解き方を簡単にした。

配列を用意する。

連続している区間をカウントしていき、途切れたらそこまでのを配列に値として追加。

2連続で穴が開いていたら0を値として追加。とまあうまくやる。

で最後に、

白紙があるなら{隣接している2つの要素同士+1で最大のものを求める。}

無いなら{値が最大の要素を1つ見つけ出力する}

という方法で最長をカウントした。出来た配列が{0}の時バグるんで、そこだけうまく処理したつもり。

#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
	int n,k;
	while( cin >> n >> k , n){
		bool no = false;
		int ret = 0;
		int data[100001] = {0};
		vector<int> t;
		
		rep(i,k){
			int c; cin >> c;
			if(!c)no = true;
			else data[c-1] = 1;
		}
		
		int c = 0;
		
		rep(i,n+1){
			if(data[i]){
				c++;
			}else{
				if(i && c == 0){	
					if(t.back() != 0)t.push_back(0);
				}else{
					ret = max(ret,c);
					t.push_back(c);
					c = 0;
				}
			}
		}
		if(no){
			if(t.size() == 1)ret = max(ret,t[0]+1);
			else rep(i,t.size()-1)ret = max(ret,t[i]+t[i+1]+1);
		}
		cout << ret << endl;
	}
}