ECR156-E I Wanna be the Team Leader - zawatinはてなブログ

問題

https://codeforces.com/contest/1886/problem/E (2400diff)

$N$ 人のプログラマーがいて、 $i$ 人目の耐久力は $a_{i}$ である。

$M$ 個のプロジェクトがあって、 $i$ 個目のプロジェクトの難易度は $b_{i}$ である。

あなたは、各プロジェクトにプログラマーを割り当てる。以下の条件を全て満たす割当てが存在するか判定し、存在する場合はそのような割当てを一つ求めよ。

各プロジェクトに最低一人のプログラマーが割り当てられる
各プログラマーは高々一つのプロジェクトに割り当てられる
$i$ 個目のプロジェクトに $k_{i}$ 人のプログラマーが割り当てられたとする。 $i$ 個目のプロジェクトに割り当てられた各プログラマーの耐久力が $\frac{b_{i}}{k_{i}}$ 以上である

制約

$1\ \le\ n\ \le\ 2\times 10^{5}$
$1\ \le\ m\ \le\ 20$
$1\ \le\ a_{i}, b_{i}\ \le\ 10^{9}$

解法

プログラマーを昇順に並べ替えたとする。各プロジェクトへのプログラマーの割当てを「前から $l$ 人目から、前から $r$ 人目までを割り当てる」として良い。すなわち、数列 $a$ から $m$ 個の区間を削除する問題になる。プロジェクト $i$ と区間の左端の組 $l$ に対して、あり得る最左の右端を前計算しておく。これを $\text{jump}_{i, l}$ とする。右端の候補が存在しないときは $\text{jump}_{i, l} = \infty$ とする。

$\text{dp}_{S}$ を「プロジェクトの集合 $S$ に対して $a$ の前から最低何人いれば割当がうまくいくか」とする。

$\text{dp}_{S\cup i} \leftarrow \min(\text{dp}_{S\cup i}, \min_{j = \text{dp}_{S}}^{n - 1}\text{jump}_{i, j})$

と遷移できる。これは $\text{jump}_{i, j}$ を後ろから累積min列を前計算しておけば効率的に計算できる。

割当を一つ求める -> dpの復元

実装

#include <bits/stdc++.h>

#include "Src/Template/IOSetting.hpp"
#include "Src/Number/IntegerDivision.hpp"
using namespace zawa;

int main() {
    SetFastIO();

    int n, m; std::cin >> n >> m;
    std::vector<std::pair<int, int>> ai(n);
    for (int i{} ; i < n ; i++) {
        std::cin >> ai[i].first;
        ai[i].second = i;
    }
    std::sort(ai.begin(), ai.end());
    std::vector<int> b(m);
    for (auto& x : b) std::cin >> x;

    const int INF{(int)1e9};
    std::vector jump(m, std::vector<int>(n, INF));
    for (int i{} ; i < m ; i++) {
        for (int j{} ; j < n ; j++) {
            int needK{DivCeil(b[i], ai[j].first)};
            jump[i][j] = j + needK;
        }
    }
    std::vector mins(m, std::vector<int>(n, INF));
    for (int i{} ; i < m ; i++) {
        mins[i][n - 1] = jump[i][n - 1];
        for (int j{n - 2} ; j >= 0 ; j--) {
            mins[i][j] = std::min(mins[i][j + 1], jump[i][j]);
        }
    }

    std::vector<std::vector<int>> ans(m);
    std::vector<int> dp((1 << m), INF);
    std::vector<int> recov((1 << m), -1);
    dp[0] = 0;
    for (int bit{} ; bit < (1 << m) ; bit++) {
        if (dp[bit] >= n) continue;
        for (int i{} ; i < m ; i++) {
            if (bit & (1 << i)) continue;
            int cur{dp[bit]};
            if (mins[i][cur] <= n and dp[bit | (1 << i)] > mins[i][cur]) {
                dp[bit | (1 << i)] = mins[i][cur];
                recov[bit | (1 << i)] = i;
            }
        }
    }

    if (dp[(1 << m) - 1] == INF) {
        std::cout << "NO" << '\n';
        return 0;
    }
    assert(dp[(1 << m) - 1] <= n);

    int now{(1 << m) - 1};
    while (recov[now] != -1) {
        int use{recov[now]};
        assert(now & (1 << use));
        int next{now ^ (1 << use)};
        assert(dp[next] < dp[now]);
        int cur{dp[next]};
        assert(cur < n);
        for (int k{1} ; ; k++) {
            int check{dp[now] - k};
            assert(0 <= check and check < n);
            ans[use].push_back(ai[check].second);
            int need{DivCeil(b[use], ai[check].first)};
            if (check + need <= dp[now]) break; 
        }
        now = next;
    }
    assert(now == 0);

    std::cout << "YES" << '\n';
    for (int i{} ; i < m ; i++) {
        std::cout << ans[i].size();
        for (auto x : ans[i]) std::cout << ' ' << x + 1;
        std::cout << '\n';
    }
}

感想

PC触れないときに $n$ 時間かけて考察 -> 詰めきれなかったので解説チラ見 -> 「計算量 $O(nm + m2^{m})$ 」という文言が見えて全てを理解
区間を抜き出す問題と言い換えるまで自力で導出できた。dpがどうしても $O(n2^{m})$ などになって困っていた。解説見てからだとどうして気づけなかったんだろうという気持ちになる
実装が下手くそで、6回ペナを出したし愚直も書いた