コンテンツにスキップ

ABC478 B - Topping

サイト
AtCoder
コンテスト
ABC478
問題
B - Topping
難易度
90

ii 番目のトッピングは価格 ii、嬉しさ WiW_i です。価格の総和が VV 以下になるように相異なる 3 種類を選ぶとき、嬉しさの総和の最大値を求める問題です(N≤100N \le 100)。

N≤100N \le 100 なので、3 つの組 i<j<ki < j < k を全部試しても (1003)≈1.6×105\binom{100}{3} \approx 1.6 \times 10^5 通りで間に合います。価格の総和 i+j+ki + j + k が VV 以下のものについて、嬉しさの総和の最大値を取ります。

コードでは添字を 00 始まりにしているので、価格の総和は i+j+k+3i + j + k + 3 になります。

Python
from itertools import combinations
N, V = map(int, input().split())
W = list(map(int, input().split()))
ans = 0
for i, j, k in combinations(range(N), r=3):
if i + j + k + 3 > V:
continue
ans = max(ans, W[i] + W[j] + W[k])
print(ans)
Uiua
/↥▽<⊙(+2∩(≡/+⧅<3)⇡):°⊟:∩(⊜⋕⊸≠@ &sc)

∩(⊜⋕⊸≠@ &sc) で 2 行を数値の配列として読み、°⊟ で 1 行目を NN と VV に分けます。⧅<3 で添字が増加する 3 つ組をすべて作り、≡/+ で各組の和を取ります。これを ∩ で添字 ⇡ NN と WW の両方に行い、添字の和(に 22 を足したもの)が VV 未満、つまり価格の総和が VV 以下の組だけを ▽ で残して、/↥ で最大値を取っています。