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

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

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

 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;
}