mayoko’s diary

プロコンとかいろいろ。

Facebook Hacker Cup 2016 Round 1 Laundro, Matt

Facebook Hacker Cup 2016 Round 1 に参加しました。結果は x-oo で, 今回は 30pt 以上あれば良いらしいので Round 2 に行けるみたいです。やったぜ。

解法

貪欲にやっていきます。

まず, priority_queue を使って, 洗濯物が出来上がる時間を小さい順に求めていきます。
(洗濯物が出来る時間, それを作った洗濯機の種類) というようなものを pair で持っておけば, ある洗濯物が出来るタイミングおよびその洗濯機を使って次の洗濯物が出来るタイミングがわかるのでハッピーです。

で, 乾燥機は 0, 1, 2, ..., M-1, 0, 1, 2, ... というように使っていくのが良いので, L 個の洗濯物を乾燥させるまでこのサイクルで乾燥させていきます。なお, M が L より大きい時は, M = L として良いです。

本番謎に二分探索してしまったため間に合いませんでした(アホ)。

const int MAXN = 100010;
int L, N, M, D;
int W[MAXN];
ll dry[10*MAXN];

void solve(int T) {
    cin >> L >> N >> M >> D;
    ll w = 0;
    for (int i = 0; i < N; i++) {
        cin >> W[i];
        w = max<ll>(w, W[i]);
    }
    priority_queue<pli, vector<pli>, greater<pli> > que;
    for (int i = 0; i < N; i++) que.push(pli(W[i], i));
    int cur = 0, l = min(L, M), cnt = 0;
    for (int i = 0; i < l; i++) dry[i] = 0;
    ll ans = -1;
    while (1) {
        pli p = que.top(); que.pop();
        ll y = p.first;
        dry[cur] = max(dry[cur], y) + D;
        cnt++;
        if (cnt >= L) {
            ans = dry[cur];
            break;
        }
        cur = (cur+1)%l;
        int i = p.second;
        que.push(pli(y+W[i], i));
    }
    cout << "Case #" << T << ": " << ans << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) solve(t);
    return 0;
}