[AtCoder] ABC 184 F – Programming Contest

2020年11月23日2020年12月12日

問題

方針

半分全列挙

\( n = \min(20, N) \) として、問題を \( n \) と \( N – n \) 個に分けて考えます。前半の問題の集合を \( A \) とし、後半を \( B \) とします。\( A \) の \( n \) 個の問題から選んで \( T \) 分以下となる時間の総和は、\( 2^n \) 通りあることが分かります。これは、ビット全探索を用いて列挙できます。

\( A \)、\( B \) のそれぞれの時間の総和を昇順に並び替え、\( A \) からある時間 \( x \) を選んだとき、\( B \) の時間の総和 \( y \) として、\( x + y \leq T \) を満たす最大の \( y \) を探索します。これは、二分探索で実現できます。

分枝限定法

この問題はいわゆる 0-1 ナップサック問題において、価値と重さが等しいものであると解釈できるのできます。したがって、分枝限定法によって解くことができます。

コード

半分全列挙

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

int main() {
    int N;
    cin >> N;
    ll T, A[N];
    cin >> T;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    int n = min(20, N);
    int m = N - n;
    vector<ll> v1, v2;
    v1.push_back(0);
    v2.push_back(0);
    int k1 = 1<<n;
    int k2 = 1<<m;
    for (int i = 1; i < k1; i++) {
        ll t = 0;
        for (int j = 0; j < n; j++) {
            if (((1<<j) & i) != 0) {
                t += A[j];
            }
        }
        if (t <= T) {
            v1.push_back(t);
        }
    }
    for (int i = 1; i < k2; i++) {
        ll t = 0;
        for (int j = n; j < N; j++) {
            if (((1<<(j - n)) & i) != 0) {
                t += A[j];
            }
        }
        if (t <= T) {
            v2.push_back(t);
        }
    }
    sort(v2.begin(), v2.end());
    ll ans = 0;
    for (ll i : v1) {
        int l = -1;
        int r = v2.size();
        while (r - l > 1) {
            int m = l + (r - l) / 2;
            if (i + v2[m] <= T) {
                l = m;
            } else {
                r = m;
            }
        }
        if (ans < i + v2[l]) {
            ans = i + v2[l];
        }
    }
    cout << ans << "\n";
    return 0;
}

分枝限定法

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

int N;
ll T;
ll best = 0;
ll A[40];
ll s_A[41]{};

// A_l + ... + A_{r - 1}
ll sum_v(int l, int r) {
    return s_A[r] - s_A[l];
}

void dfs(int n, ll t) {
    if (t <= T) {
        best = max(best, t);
    }
    if (n == N || t >= T) return;
    ll _t = t;
    int idx = -1;
    for (int i = n; i < N; i++) {
        if (_t + A[i] <= T) {
            _t += A[i];
        } else {
            idx = i;
        }
    }
    best = max(best , _t);
    if (idx == -1) {
        return;
    } else {
        _t = _t * A[idx] + (T - _t) * A[idx];
        if (_t <= best * A[idx]) return;
    }
    if (_t == T) {
        best = T;
        return;
    }
    dfs(n + 1, t + A[n]);
    dfs(n + 1, t);
}

int main() {
    cin >> N >> T;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A, A + N, greater<ll>());
    dfs(0, 0);
    cout << best << "\n";
    return 0;
}