Lunch

2 secs 1024 MB

Ang107

問題

提出

テストケース

解説

$O(NM)$ 解法

この問題は主菜、副菜の組を全探索することで正解でき、これは二重ループで実現できます。計算量は $O(NM)$ で十分高速です。

以下は Python の実装例です。

xxxxxxxxxx
 
# 入力の受け取り
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
d = list(map(int, input().split()))
ans = -float("inf")
# 主菜、副菜の組を全探索して最大値を更新する
for i in range(n):
    for j in range(m):
        if a[i] + c[j] <= k:
            ans = max(ans, b[i] + d[j])
print(ans)
​

$O(NlogN + MlogM)$ 解法

ソート & 累積 max を活用することで、上の解法より更に高速に、 $O(NlogN + MlogM)$ で正解することもできます。具体的な処理は以下のようになります。

主菜の値段と美味しさの組を、値段を基準に降順にソートします。
副菜の値段と美味しさの組を、値段を基準に昇順にソートします。
ソート後の副菜で、累積 max を取ります。これにより、「値段が $P$ 円以下の副菜の最大の美味しさ」を求めることができるようになります。
値段で降順ソートした主菜の値段と美味しさの組を順に走査します。
累積 max を記録した配列のインデックス番号を管理しながら走査することで、 $O(N)$ で答えを求めることができます。

よって、ソートがボトルネックとなり、 $O(NlogN + MlogM)$ で正解できます。以下は Python の実装例です。

xxxxxxxxxx
 
# 入力の受け取り
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
d = list(map(int, input().split()))
​
ans = -float("inf")
# 値段と美味しさをまとめたリストを作る。
ab = [(i,j) for i,j in zip(a,b)]
cd = [(i,j) for i,j in zip(c,d)]
# それぞれソート
ab.sort(reverse = True)
cd.sort()
# 累積maxの計算
pref_max = [-float("inf")]
for c,d in cd:
    pref_max.append(max(pref_max[-1],d))
# 累積maxの参照先のindex
index = 0
for a,b in ab:
    while index < m and a + cd[index][0] <= k:
        index += 1
    ans = max(ans, b + pref_max[index])
print(ans)

Lunch

O(NM)O(NM)O(NM) 解法

O(NlogN+MlogM)O(NlogN + MlogM)O(NlogN+MlogM) 解法

$O(NM)$ 解法

$O(NlogN + MlogM)$ 解法