ABC072C問題

解答の方針

問題はこちらから
配列内のデータ±1と等しい数字をカウント
以下は私の提出コード

ABC072C.cpp

#include <iostream>
#include <algorithm>
#define REP(i, n) for(int i=0; i<(int)(n); i++)
using namespace std;
int main(void){
  int n, i, j, max, max2;
  cin >> n;
  int a[100001] = {}, cnt[100001] = {};
  REP(i, n) cin >> a[i];
  REP(i, *max_element(a,a+n)+2){
    REP(j, n) {
      if((i == a[j]) || (i == a[j]+1) || (i == a[j]+2)) cnt[i]++;
    }
  }
  max = *max_element(cnt,cnt+100001);
  cout << max << endl;
  return 0;
}

結果と改善点

サンプルデータについては正答を得たが、for文2重ループのためTLE(time limit exceeded)となり、アクセプトされず。高速化とアルゴリズムに慣れる必要がある。
下記のように入力時にカウントをする事で簡潔に解く事ができる。

ABC072C.cpp

#include <iostream>
#include <algorithm>
#define REP(i, n) for(int i=0; i<(int)(n); i++)
using namespace std;
int main(void){
  int n, i, max;
  cin >> n;
  int a[100001] = {}, cnt[100001] = {};
  REP(i, n){
    cin >> a[i];
    cnt[a[i]  ]++;
    cnt[a[i]+1]++;
    cnt[a[i]+2]++;
  }
  max = *max_element(cnt,cnt+100001);
  cout << max << endl;
  return 0;
}