予算内で選ぶ 2 つの商品

並べ替えと貪欲
問題 10
ふつう
目安 31 分

商品の値段の一覧から 2 つを選び、合計が予算以内でいちばん高くなる組を探す。全部の組を試さず、並べ替えと両端からの探索で答える練習です。

本番の試験は PC で受けることが多いので、PC での練習をすすめます。スマホでも、読んで、書いて、採点するところまで動きます。

入力は標準入力から読み、答えは標準出力に書きます。1 テストあたり 2 秒までです。

問題

取引先への贈り物として、店の N 個の商品から異なる 2 個を選びます。2 個の値段の合計は予算 B 円以下にしなければなりません。その中で、合計ができるだけ高くなるように選んだときの合計の金額を出力してください。予算 B 円以下になる選び方が 1 つも無いときは -1 を出力してください。

同じ値段の商品が複数あることもあります。値段が同じでも別の商品なら、その 2 個を選んでかまいません。

入力の形式

N B
p_1 p_2 ... p_N

1 行目に商品の数 N と予算 B、2 行目に N 個の商品の値段 p_i が半角の空白 1 つで区切られて並びます。値段は並べ替えられていません。

出力の形式

答えの金額 (選べないときは -1) を 1 行に出力します。

制約

N は 2 以上 200000 以下です
予算 B は 1 以上 2000000000 以下の整数です
値段 p_i は 1 以上 1000000000 以下の整数です

入力と出力の例

例 1

予算は 1000 円です。800 円と 300 円は合計 1100 円で予算を越えます。450 円と 500 円の合計 950 円が、予算以内でいちばん高い組です。

入力

5 1000
300 800 450 120 500

出力

例 2

どの 2 個を選んでも予算 500 円を越えるときです。

入力

3 500
400 300 250

出力

-1

例 3

同じ 300 円の商品が 2 個あり、合計がちょうど予算の 600 円になります。予算ちょうどは選べます。

入力

4 600
300 700 300 100

出力

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

全部のテストに通ると、解答と考え方が開きます。

先にヒントを試すと、自分で解けた手応えが残ります。どうしても詰まったときは、ここから開けます。

解答

値段を安い順に並べ替え、左端 i と右端 j から内側へ寄せていきます。p[i] + p[j] が予算以内なら答えの候補にして i を進め、越えたら j を戻します。予算以内のとき、i の相手として残っている商品はどれも p[j] 以下なので、i を使う組の中では今の合計がいちばん高く、i を外してかまいません。越えたとき、j の相手として残っている商品はどれも p[i] 以上なので、j を使う組はどれも予算を越え、j を外してかまいません。このため見落としがありません。並べ替えが O(N log N)、寄せていくのが O(N) です。

Python

import sys

data = sys.stdin.read().split()
n, budget = int(data[0]), int(data[1])
prices = sorted(map(int, data[2:2 + n]))

best = -1
i, j = 0, n - 1
while i < j:
    total = prices[i] + prices[j]
    if total <= budget:
        if total > best:
            best = total
        i += 1
    else:
        j -= 1

print(best)

JavaScript

const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
const budget = data[1];
const prices = data.slice(2, 2 + n).sort((a, b) => a - b);

let best = -1;
let i = 0;
let j = n - 1;
while (i < j) {
  const total = prices[i] + prices[j];
  if (total <= budget) {
    if (total > best) best = total;
    i++;
  } else {
    j--;
  }
}

console.log(best);

計算量

時間は O(N log N) で、ほとんどが並べ替えです。両端から寄せる部分は、1 回ごとに i か j のどちらかが 1 つ動くので、全部で N 回ほどです。全部の組を二重の for で試す書き方は O(N × N) で、N が 20 万の入力では 200 億組になり、時間切れになります。

よくある間違い

JavaScript の sort() を引数なしで呼ぶ。数ではなく文字として並ぶので、1000 が 300 より前に来ます。sort((a, b) => a - b) と書きます
同じ商品を 2 回選んでしまう。i と j が同じ位置になったら止めます (i <= j ではなく i < j)
選べないときの -1 を出し忘れて、答えの初めの値の 0 をそのまま出す
予算ちょうどの組を外してしまう。「予算以下」なので <= で比べます

解答を動かした版 Python 3.12.14Node.js 22.23.4確認日 2026/10/31

main.py

import sys

data = sys.stdin.read().split()
n, budget = int(data[0]), int(data[1])
prices = list(map(int, data[2:2 + n]))

# ここから書く

入力

5 1000
300 800 450 120 500

出力

「実行する」を押すと、ここに出力が出ます

できているか「提出して採点」を押すと、隠れたテストを全部走らせて、通ったかをここに出します