【ABC137】D - Summer Vacation - メモ帳がわり

解法

DPがしたくなる見た目をしているが、O(NM)になって間に合いそうにない。
あまり気が乗らないのだが、貪欲法で解けないかどうか考えてみることにする。

報酬を最大化したいので、なるべく報酬が大きい労働を優先的に選択したくなる。
かつ、報酬を受け取れるまでの日数はなるべく短い方が良い。
それから、報酬を受け取れるまでの日数が短いものはなるべくM日に近い時期に選択した方が、後々可能性が広がる。
どこにどのアルバイトを配置するかは二分探索で最適な位置を探すことができる。

他の解法

もっとわかりやすい解法もある。

drken1215.hatenablog.com

考え方は少し違うが、本質的にやっていることは変わらない気がする。

実装

実装する上で以下の記事を参考にした。
覚えておくと実装が楽になるTipsだ。

qiita.com

rsk0315.hatenablog.com

報酬は降順、日数は昇順にしてソートし、最適な配置を二分探索で決定する。

void solve(long long N, long long M, std::vector<long long> A, std::vector<long long> B){
    vector<pair<int, int>> vec(N);
    REP (i, N) vec[i] = {-B[i], A[i]};
    ALL(sort, vec);

    ll ans = 0;
    set<int> st;
    REP (i, M) st.insert(i+1);
    REP (i, N) {
        auto l = st.lower_bound(vec[i].second);
        if (l != st.end()) {
            st.erase(l);
            ans += -vec[i].first;
        }
    }

    c(ans)
}