ABC373 C問題の解説（Python）

はじめに

この記事では、ABC373のC問題を解説していきます。

ABC（AtCoder Beginner Contest）とは、AtCoderが開催している、競技プログラミングコンテストです。

ABC373　C – Max Ai+Bj

問題

問題

長さNの整数列A, Bが与えられます。\(A_i+B_j\) の最大値を求める問題です。

制約

• \(1 \leqq N \leqq 5×10^5 \)
• \(|A_i| \leqq 10^9 \)
• \(|B_i| \leqq 10^9 \)

思考の筋道

\(A_i+B_j\) が最大となるのは、\(A_i\) として整数列Aの最大値を選び、\(B_j\) として整数列Bの最大値を選んだときです。

つまり、max関数を用いてそれぞれの最大値を求め、それらを足すだけでOKですね。

この問題のポイントは、整数列Aの最大値と整数列Bの最大値を、それぞれ独立に求められることです。

独立に取り扱わずに、Aの要素×Bの要素を全探索すると、 5×10^5の二乗でTLE（制限時間超過）になってしまうことに注意しましょう。

C問題にしてはとても簡単で、逆にちょっと不安になる問題ですね。

コード

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

print(max(A) + max(B))

以上、ABC373のC問題の解説でした！

では、またね。

リンク