AtCoder 版蟻本記事で、登竜門として紹介している問題。
ずばり「半分全列挙 + 二分探索」です！

問題へのリンク

類題とか

問題概要

$N$ 個の正の整数 $P_{1}, \dots, P_{N}$ が与えられる。これらの整数のうちから重複を許して 4 個まで選んで総和をとる (1 個も選ばなくても構わない)。

総和が $M$ 以下ならば、その値が得点となる
総和が $M$ より大きいならば、得点は 0 点となる

獲得できる得点の最大値を求めよ。

制約

$1 \le N \le 1000$
$1 \le M \le 2 \times 10^{8}$
$1 \le P_{i} \le 10^{8}$

考えたこと

まず、選べる個数が 1, 2, 3, 4 個となるのが嫌なので、正の整数に 0 を付け加えて、0 も選べるようにしてしまう。そうすれば、「ちょうど 4 個を選ぶ」という設定の問題とみなせる。

さて、単純に全探索したのでは、 $O(N^{4})$ の計算量となって間に合わない。そこで、4 個まとめて考えるのではなく「2 個 + 2 個」に分けて考えることにしよう。まず、 $N+1$ 個 (0 含む) の整数から 2 個選んで和をとった値として考えられるものを列挙する。列挙された集合を $S$ とする。そうすると、問題は次のように言い換えられる。

集合 $S$ から重複を許して整数 $a, b$ を選ぶ。 $a + b$ の値のうち、 $M$ 以下である範囲での最大値を求めよ

ずいぶんと考えやすくなった。 $S$ のサイズは $O(N^{2})$ となる。

$a$ を固定して、二分探索へ

まず、 $S$ は小さい順に並び替えることにする。この作業には $O(N^{2} \log N)$ の計算量を要する ( $\log{N^{2}} = 2 \log N$ であることから、 $O(N^{2} \log N^{2}) = O(N^{2} \log N)$ であることに注意)。

さて、 $S$ から選んだ 1 つめの要素である $a$ を固定することにする。そうすると、問題はさらに次のように言い換えられる。

集合 $S$ の要素のうち、 $M-a$ 以下の範囲での最大値を求めよ

ここまで来ると簡単だ。もう二分探索 (lower_bound() などを活用する) で直接求められるところまで来ている！！！

コード

計算量は次のようになる。

$S$ を小さい順にソート： $O(N^{2} \log N)$
$a$ を 1 つ固定したときの計算量： $O(\log N)$
$a$ を動かして行ったときの計算量： $O(N^{2} \log N)$

以上より、全体の計算量は $O(N^{2} \log N)$ となる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N, M;
    cin >> N >> M;
    vector<long long> P(N);
    for (int i = 0; i < N; ++i) cin >> P[i];
    P.push_back(0);
    vector<long long> S;
    for (int i = 0; i < P.size(); ++i) 
        for (int j = 0; j < P.size(); ++j)
            S.push_back(P[i] + P[j]);
    sort(S.begin(), S.end());
    
    long long res = 0;
    for (long long a : S) {
        auto it = upper_bound(S.begin(), S.end(), M-a);
        if (it == S.begin()) continue;
        --it;
        res = max(res, a + *it);
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 本選 2008 C - ダーツ (AOJ 0529, 難易度 6)

問題概要

制約

考えたこと

$a$ を固定して、二分探索へ

コード