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

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

AtCoder ABC 373 C - Max Ai+Bj (5Q, 灰色, 250 点)

AtCoder AtCoder250点 ABC-C 灰色diff NoviSteps5Q 易しい計算量改善計算量改善:O(N)で求められる式に変形する数列考察テク:最大値や最小値に着目する最適化問題最大スコア

計算量改善のことを本当に知らないと、TLE に悩むかもしれない。

問題へのリンク

問題概要

長さ $N$ の 2 つの数列 $A_{1}, A_{2}, \dots, A_{N}$ 、 $B_{1}, B_{2}, \dots, B_{N}$ が与えられる。

1 以上 $N$ 以下の整数 $i, j$ を選んで、 $A_{i} + B_{j}$ の最大値を求めよ。

制約

$1 \le N \le 5 \times 10^{5}$

考えたこと

最も素直に考えると、次のように二重 for 文を用いて解きたくなるかもしれない。

long long res = 0;
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        res = max(res, A[i] + B[j]);
    }
}

しかしこの解法の計算量は $O(N^{2})$ となる。これでは TLE となってしまう。

そこで、次のように考え直そう。

数列 $A_{1}, A_{2}, \dots, A_{N}$ の最大値 max_A を求める
数列 $B_{1}, B_{2}, \dots, B_{N}$ の最大値 max_B を求める

そうすると、max_A + max_B が答えとなる。この解法は、下のコードのように一重 for 文で書くことができて、計算量は $O(N)$ となる。

コード

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

int main() {
    long long N, max_A = 0, max_B = 0;
    cin >> N;
    vector<long long> A(N), B(N);
    for (int i = 0; i < N; i++) cin >> A[i], max_A = max(max_A, A[i]);
    for (int i = 0; i < N; i++) cin >> B[i], max_B = max(max_B, B[i]);
    cout << max_A + max_B << endl;
}