ARC082 C : Together(300)
作成日：2017.09.03
最終更新日：2017.09.03
問題概要
長さ$N$の整数列$\{a_i\}$が与えられる。
各$i$に対して$a_i$に$1,0,-1$のいずれかを加える操作を行う。
適切な操作を行った後に$X$を適切に選んだ時、$a_i = X$となる$i$の個数の最大値を求めよ。
制約
$1 \leq N \leq 10^5$
$0 \leq a_i < 10^5$
$a_i$は整数
考え方
$X$を先に決めれば$a_i = X$とできる$i$の個数は$X-1 \leq a_i \leq X+1$である個数であり、これは簡単に求められる。
よって$X$を$-1$から$10^5$まで動かしていけば答えを求めることができる。
$X$が変わるごとに数えると間に合わないが、各$a_i$において$a_i - 1 \leq X \leq a_i + 1$を満たす$X$を選んだ時の答えに$1$足していくということをすれば計算量が$O(N)$となり解ける。
ソースコード
マクロ等はこちら
const int MC = 100010;
int N;
int c[MC]; //c[i] : X = i-1 の時の答え
int main(){
scanf("%d" , &N);
repp(i,0,N){
int a;
scanf("%d" , &a);
++c[a];
++c[a+1];
++c[a+2];
}
int ans = 0;
repp(i,0,MC){
ans = max(ans , c[i]);
}
printf("%d\n" , ans);
return 0;
}解法まとめ
$a_i$それぞれにおいて$X = a_i - 1 , a_i , a_i + 1$の時の答えを$1$加える。(7-13行)
その後、すべての$X$の答えのうち最大のものを求める。(14-18行)