ちょっとした考察が必要になる問題。

問題へのリンク

問題概要

整数からなる数列 $A_{1}, A_{2}, \dots, A_{N}$ が与えられる。数列の各要素に対して「何もしない」「1 を足す」「1 を引く」をしていく。

操作後に、整数値 $X$ を選ぶ。 $A_{i} = X$ となる $i$ の個数の最大値を求めよ。

制約

$1 \le N \le 10^{5}$
$0 \le A_{i} \le 10^{5}$

考えたこと

問題文では操作後に整数値 $X$ を選んでいるが、整数値 $X$ を先に選んでから操作しても、一向に構わない。

そこで、整数値 $X$ を仮決めしたときに、数列をどのように操作すれば良いかを考えてみよう。少し考えると、次のように結論付けられる。

$A_{i} = X$ のとき：何もしない
$A_{i} = X-1$ のとき：1 を足す
$A_{i} = X+1$ のとき：1 を引く
$A_{i}$ の値がそれ以外のとき：どうしようもない（ $X$ には一致させられない）

このことから、 $X$ を決めたときのスコアは次のようになる。

$A_{i} = X-1, X, X+1$ となるような $i$ の個数

これを効率よく求めるために、次のバケットを用意しよう（ $a_{i} \le 10^{5}$ なので、サイズは $10^{5}$ 程度で十分）。

nums[x]：数列 $A$ の中の、 $x$ の個数

これを求めておけば、上記のスコアは効率よく求められる。あとは、 $X$ の値として、 $1$ から $10^{5}$ 程度まで試していけば良い。

計算量は、 $M = \max(A_{1}, A_{2}, \dots, A_{N})$ として、 $O(N + M)$ と評価できる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    const int MAX = 110000;

    int N, a;
    cin >> N;
    vector<int> nums(MAX, 0);
    for (int i = 0; i < N; i++) {
        cin >> a;
        nums[a]++;
    }

    int res = 0;
    for (int x = 1; x+1 < MAX; x++) {
        int num = nums[x-1] + nums[x] + nums[x+1];
        res = max(res, num);
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 072 C - Together (4Q, 茶色, 300 点)

問題概要

制約

考えたこと

コード