$N$ 個のものから $1$ 個除いたものを考えるのは色々定石がある！

問題へのリンク

問題概要

$N$ 個の整数 $A_{1}, \dots, A_{N}$ が与えられる。

各 $i$ に対して、 $A_{i}$ を除外した $N-1$ 個の整数の最大値を求めよ。

制約

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

解法 (1)：アドホックに考える

まずは素朴な解法を考えてみる。たとえば $A = (3, 5, 6, 10, 8)$ とかだったとき、 $A$ から [tex 3] や $5$ を除外したとしても、残りの整数値の最大値は 10 で変わらないであろう。

一方、 $A$ から $10$ を除外する場合においては、「 $A$ の中で二番目に大きい数」を出力する必要がある。よって

$A$ の中の最大値を $M$
$A$ の中で二番目に大きい値を $m$ (最大値が複数個あるときは $M = m$ となりうる)

としたとき、

$A_{i} \neq M$ のときは $M$ を出力
$A_{i} = M$ のときは $m$ を出力

とすれば OK。

$M$ や $m$ を求めるのは、本来は $O(N)$ でできる。でも $A$ を大きい順にソートして、「先頭の要素」「二番目の要素」をみるのが早いと思う。この場合の計算量は $O(N \log N)$ となる。

コード

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

int main() {
    int N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    auto A2 = A;
    sort(A2.begin(), A2.end(), greater<long long>());
    for (int i = 0; i < N; ++i) {
        if (A[i] != A2[0]) cout << A2[0] << endl;
        else cout << A2[1] << endl;
    }
}

解法 (2)：左右から累積和

$N$ 個の要素から 1 個を除去したものを扱う問題では、

左右からの累積結果を求める

というアプローチがめちゃくちゃ有効。それで解ける類題は以下のようにたくさんある！

今回であれば

left[i] ← $A$ のうち、左から $i$ 個の最大値
right[i] ← $A$ のうち、右から $i$ 個の最大値

とする。そうすると各 $i$ に対して次のように求められる。

max(left[i], right[N-i-1]

この方法でも $O(N)$ の計算量で解ける。

コード

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

int main() {
    int N;
    cin >> N;
    vector<long long> A(N), left(N+1, 0), right(N+1, 0);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < N; ++i) {
        left[i+1] = max(left[i], A[i]);
        right[i+1] = max(right[i], A[N-i-1]);
    }
    for (int i = 0; i < N; ++i) cout << max(left[i], right[N-i-1]) << endl;
}

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

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

AtCoder ABC 134 C - Exception Handling (灰色, 300 点)

問題概要

制約

解法 (1)：アドホックに考える

コード

解法 (2)：左右から累積和

コード