AtCoder BC072 C: Together

問題

https://beta.atcoder.jp/contests/abc072/tasks/arc082_a

解法

a_iがとりうる値は、a_i-1、a_i、a_i+1の3つです。

なのでとりうる値の数をカウントする配列を用意しておき、各a_iについてa_i-1、a_i、a_i+1の3カ所を1ずつ加算していけば、その最大値が解となります。

実装

a_iが0となる場合の扱いを簡略化するため、a_iと+1、+2の箇所を加算している。最終的な解は「個数の最大値」であるためこのままでも問題無い。

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<string>
 
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007
 
using namespace std;
 
typedef long long int ll;
 
const ll INF=(ll)1e18;
 
#define MAX 99999
 
int s[MAX+3];
 
int main(){
    int N;
    cin >> N;
 
    REP(i,MAX+3)s[i]=0;
 
    REP(i,N){
        int a;
        cin >> a;
 
 
        s[a]++;
        s[a+1]++;
        s[a+2]++;
 
    }
 
    int ans = 0;
 
    REP(i,MAX+3)ans = max(ans, s[i]);
 
    cout << ans << endl;
}