第６回日本情報オリンピック 本選 「最長の階段」

ごり押しで何とかいけそうな問題。

ソートをして少し考察しましょう。

JOIの解説の通りにバケットソートを用いて解きました。

問題文の言われたとおりにやっただけなので解説は省かせてもらいます。

#include <cstdio>
#include <algorithm>

using namespace std;

int main(){

  int n,k;
  
  bool d[100002],flag = false;
  int ans = 0;
  
  scanf("%d%d",&n,&k);
  
  for(int i = 0;i < n;i++){
    d[i] = false;
  }
  
  for(int i = 0;i < k;i++){
    int t;
    scanf("%d",&t);
    d[t] = true;
  }
  
  if(d[0] == false){
    int ren = 0;
    for(int i = 1;i <= n;i++){
      if(d[i] == true){
	ren++;
      }else{
	ans = max(ans,ren);
	ren = 0;
      }
    }
    ans = max(ans,ren);
  }else{
    
    int rened = 0;
    int ren = 0;
    
    for(int i = 1;i <= n;i++){
      if(d[i] == false){
	ans = max(ans,rened+1+ren);
	rened = ren;
	ren = 0;
      }else{
	ren++;
      }
    }
    ans = max(ans,rened+1+ren);
  }
  
  printf("%d\n",ans);

  return 0;
  
}