読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

SRM681 Div.1 Easy FleetFunding

競プロ 二分探索 貪欲法

Div.1 Easy 3題目。

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14104&rd=16651

1からmまでの番号がつけられたm種類のパーツがある。宇宙船を1隻造るにはm種類のパーツすべてが1個ずつ必要である。また、パーツを生産するn個の工場がある。工場iの生産個数の上限はk_i、生産できるパーツの種類は[a_i, b_i]である。k_iを超えない限りは、同じ工場で同じパーツを複数生産しても構わない。以上の条件で建造できる最大の宇宙船の数を求めよ。

制約

 1 \leq n \leq 50

 1 \leq m \leq 50

 1 \leq k_i \leq 10^6

 1 \leq a_i \leq b_i \leq m

解法

以下の記述は、mayokoさんの記事ととーらすさんの記事を参考にさせていただきました。

mayokoex.hatenablog.com

torus711.hatenablog.com

解法はにぶたん×貪欲。x個の宇宙船が造れると仮定してxの最適値を探します。

なぜにぶたんで解けるかというと、解が単調性を持つからです。x個の宇宙船が造れるとすればx個以下の宇宙船も作れるし、x個の宇宙船が造れないとすればx個以上の宇宙船も作れない。そのためあるxについて宇宙船が造れるか否かを判定すると解の範囲をx以下かx以上に絞り込めるわけです。

では、「x個の宇宙船が造れるか」の判定はどうすればいいでしょうか?これは区間スケジューリング問題に似ています。パーツを番号の昇順に見ていくと、あるパーツp_iについて、a_i <= p_iを満たす工場の中で、b_iが小さいものからk_iを超えないように取っていくのが最適です。この取り方ですべてのパーツがx個取れたらTrue, 1つでも足りないパーツがあればFalse。

実装についてはmapを使うとスマートに書けます。mp[i] = (種類iがあといくつ必要か)として、上記のように各パーツを作れた分だけ減らしていきます。a_i <= p_iとなるa_iはlower_bound()で求められますが、生産し終わったパーツはこの邪魔になるのでmpからeraseしておきます。

  • 解答例: C++ (ほとんどmayokoさんのを写経しましたすみません)
#include <bits/stdc++.h>
using namespace std;

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

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

// 全種類のパーツがx個以上あるか調べる
bool ok(int x, int m, vi k, vi a, vi b) {
    int n = k.size();

    // 工場(bの昇順でソート)
    vector<pair<pii, int> > P(n);
    rep(i, n) P[i] = make_pair(pii(b[i], a[i]), k[i]);
    sort(all(P));

    // mp[i] = 種類iのパーツをあといくつ作らなければならないか
    map<int, int> mp;
    FOR(i, 1, m + 1) mp[i] = x;
    rep(i, n) {
        int A = P[i].first.second, B = P[i].first.first, K = P[i].second;
        // it: mp[i] >= Aとなる最初の位置
        auto it = mp.lower_bound(A);
        // このパーツがこの工場で生産できる種類かつ、この工場にまだ生産の余裕があれば
        while (it != mp.end() && (it->first) <= B && K > 0) {
            // 生産限界と必要量のうち少ない分だけこのパーツを生産できる
            int minus = min(K, it->second);
            it->second -= minus;

            // 生産し終えたパーツはmpから削除(lower_boundの邪魔になるので)
            if (it->second == 0) {
                mp.erase(it++);
            } else {
                it++;
            }
            K -= minus;
        }
    }

    // すべてのパーツを必要量生産できたかを返す
    return mp.empty();

}

class FleetFunding {
    public:
    int maxShips(int m, vector<int> k, vector<int> a, vector<int> b) {
        int l = 0, r = 50 * 1000000 + 1; // MAX_N * MAX_K
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (ok(mid, m, k, a, b)) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return l;
    }
};


所要時間: -

正答率*1: 52.45%

半数以上が解けているようなのでこれは本番でも解けるようにしておきたい。

*1:Overall Accuracy. Success Rateはsubmission accuracyのことだったらしい