1. はじめに
競技プログラミングの鉄則（=鉄則本）のC02 - Two Balls の計算量を改善する。
2. 問題概要
問題 C02 - Two Balls は、N 個のボールのうち 2 つを選び、その重さの合計が最大となる値を求める問題である。
3. 想定解法1
問題の制約 $2 \le N \le 100$ から、単純に $O(N^2)$ のループを回して、解くことができる。
N = int(input())
A = list(map(int, input().split()))
answer = 0
for i in range(N - 1):
for j in range(i + 1, N):
answer = max(answer, A[i] + A[j])
print(answer)
4. 想定解法2
より単純に考えると、「最も重いボール」と「2 番目に重いボール」を選べばよい。
配列 A を降順にソートして先頭 2 つを足すことで、計算量を $O(N \log N)$ に改善できる。
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True) # 降順にソート
print(A[0] + A[1])
5. 計算量の改善
さらに、ソートを使わずに 1 回のループで「最大値」と「2 番目の値」を求めることで、計算量を $O(N)$ にできる。
N = int(input())
A = list(map(int, input().split()))
first = 0
second = 0
for a in A:
if a > first:
second = first
first = a
elif a > second:
second = a
print(first + second)
この方法は配列の並び順に依存せず、1 パスで最大 2 要素を抽出できる。
全探索・ソートのいずれよりも理論上高速な手法である。
6. まとめ
| 手法 | 計算量 | 方針 |
|---|---|---|
| 想定解法1 | $O(N^2)$ | 全探索 |
| 想定解法2 | $O(N \log N)$ | ソートして上位 2 要素を選ぶ |
| 改善解法 | $O(N)$ | 1 パスで最大 2 要素を更新 |
計算量を $O(N)$ に改善することができた。なお、問題の制約からこの改善は特に意味を持たない。自己満足の極致である。
7. 参考資料
[1]. 競技プログラミングの鉄則
[2]. 競技プログラミングの鉄則 GitHub ページ