ゆらのふなびと

競プロ, Python, C++

yukicoder No.393 2本の竹

学び。

問題

竹が2本ある。長さはそれぞれ  n1, n2 である。

 m 人の客がいる。 i 番目の客は長さがちょうど  a_i の竹が欲しいと言っている。

あなたは2本の竹のいずれかから一部を切り出すことで客の注文に応えることができる。ただし異なる竹から切り出した部分どうしをつなげて1人の客に渡すことはできない。

このとき、あなたは最大何人の客の要望に応えることができるか?

制約

 1 \leq n1, n2 \leq 10^5

 1 \leq m \leq 60

 1 \leq a_i \leq 10^5

解法

竹が1本なら、注文の長さが短い順に貪欲に配っていけばよい。竹が2本の場合、どの注文をどの竹に割り当てるかは自明でないので、DPを考える。

まず注文を長さの昇順にソートしておく。先ほど言ったようにどの注文をどの竹に割り当てるかは自明でないが、注文全体としては小さい方から答えるのが最適なのでソートしてよい。

DPの状態として何を取るか? 1つ思いつくのは、 (i, r_{i1}, r_{i2}) (r_{ij} : i個目の注文までを処理したときのj本目の竹の残りの長さ) である。実際、 (i, r_{i1}, r_{i2}) さえわかっていれば、次の漸化式によりDPを行うことができる。ただし  dp[i][r_{i1}][r_{i2}] = (状態(i, r_{i1}, r_{i2})に至るまでに応えられた注文の最大数

  •  dp[i][r_{i1}][r_{i2}] = \max \{ dp[i + 1][r_{i1} - a_i][r_{i2}], dp[i + 1][r_{i1}][r_{i2} - a_i] のうち添字が負とならないもの \}

  • ↑{ }内が空のときは  0

この計算量は時間, 空間ともに  O(mL^2) (L = 10^5 は竹の長さの最大値) である。当然これではTLE, MLEになってしまう。そこで状態をさらに圧縮することを考える。

実は、 i, r_{i1} さえわかっていれば  r_{i2} は一意に定まる。具体的には  r_{i2} = n_1 + n_2 - (i番目までの注文の長さの和) - r_{i1} である。これを上の漸化式と合わせて用いると、時間空間ともに  O(mL) でこの問題を解くことができる。

以下ではループとメモ化再帰の2種類のコードを紹介する。

  • コード1: ループ
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
typedef vector<vector<int>> Graph;
const int inf = 1e9;
const int mod = 1e9 + 7;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int d;
    cin >> d;
    rep(_, d) {
        int n1, n2;
        cin >> n1 >> n2;
        int m;
        cin >> m;
        V a(m);
        rep(i, m) cin >> a[i];
        sort(all(a));
        a.emplace_back(inf);
        m++;

        const int MAX = n1 + n2 + 1;
        vector<bool> dp1(MAX);
        dp1[n1] = true;
        int sm1 = n1 + n2;
        rep(i, m) {
            vector<bool> dp2(MAX);
            bool updated = false;
            int sm2 = sm1 - a[i];
            rep(j, MAX) {
                if (!dp1[j]) continue;
                if (j - a[i] >= 0) {
                    dp2[j - a[i]] = true;
                    updated = true;
                }
                if (sm2 - j >= 0) {
                    dp2[j] = true;
                    updated = true;
                }
            }
            if (!updated) {
                cout << i << endl;
                break;
            }
            dp1 = dp2;
            sm1 = sm2;
        }
    }

}
// テンプレはコード1を参照

const int MAX_L = 1e5 + 1;
const int MAX_M = 60 + 1;

int m;
V a;
bool done[MAX_M][MAX_L];
int dfs(int i, int x, int y) {
    if (x < 0 || y < 0) return i - 1;
    if (done[i][x]) return i;
    done[i][x] = true;
    return max(dfs(i + 1, x - a[i], y), dfs(i + 1, x, y - a[i]));
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int d;
    cin >> d;
    rep(_, d) {
        int n1, n2;
        cin >> n1 >> n2;
        cin >> m;
        a.resize(m);
        rep(i, m) cin >> a[i];
        sort(all(a));
        a.emplace_back(inf);
        m++;
        rep(i, MAX_M) rep(j, MAX_L) done[i][j] = false;
        cout << dfs(0, n1, n2) << endl;
    }

}

こういう番兵の使い方好き。