mayoko’s diary

プロコンとかいろいろ。

yukicoder No.393 2本の竹

解法

想定解とはちょっと違う解法になりました。

考察で, 「長さの短い竹をなるべく受け付ける方が良い」というのは変わりません。

なので, 配列 A をソートしておけば, 選ばれる竹は, [0, upper) というような区間を選ぶことになるはずです。この選び方が可能であるかを判定したいのですが,
dp[i] = (N1 の竹を使って合計長さが i であるような注文を受け付けることは可能か) という dp をします。すると, sum = A[0]+...+A[upper-1] として, N2 が担当しなければならない注文合計長さは sum-i になりますが, これが OK かどうかは, N2 >= sum-i が成り立つかどうかで判定できます。

結局計算量は O(N1 * m^2) です。

const int MAX = 100100;
bool dp[MAX];

// [0, upper) のものをすべて提供しても大丈夫か
bool isOK(int N1, int N2, const vi& A, int upper) {
    if (upper == 0) return true;
    int sum = 0;
    for (int i = 0; i < upper; i++)
        sum += A[i];
    if (sum > N1+N2) return false;
    memset(dp, false, sizeof(dp));
    dp[0] = true;
    for (int i = 0; i < upper; i++) {
        for (int j = MAX-1; j >= 0; j--) {
            if (dp[j]) {
                if (j+A[i] <= N1) dp[j+A[i]] = true;
            }
        }
    }
    for (int i = MAX-1; i >= 0; i--) {
        if (dp[i] && sum-i <= N2) return true;
    }
    return false;
}

void solve() {
    int N1, N2;
    cin >> N1 >> N2;
    if (N1 > N2) swap(N1, N2);
    int m;
    cin >> m;
    vector<int> A(m);
    for (int i = 0; i < m; i++)
        cin >> A[i];
    sort(A.begin(), A.end());
    for (int i = m; i >= 0; i--) {
        if (isOK(N1, N2, A, i)) {
            cout << i << endl;
            return;
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}