Codeforces Round #433 Div.2 D / Div.1 B - Jury Meeting

http://codeforces.com/contest/854/problem/D

問題概要

(N+1)個の町があり、1~Nの町に一人ずつ人が住んでいる。また 町0 → 町(1~Nのどれか) に飛ぶ飛行機と、町(1~Nのどれか) → 町0 に飛ぶ飛行機の2種類がある。飛行機を使って1~Nの町の人を全員町0に呼び、さらに全員が集まっている状態でK日間以上過ごさせ、その後全員を元の町に送り返したい。M個の飛行機の運行情報(出発日、出発元の町、行き先の町、チケット代)が与えられるので、条件を満たすような全員分チケットの買い方のうちもっとも安く済むときの合計代金を求めよ。

1 <= N <= 105

0 <= M <= 105

解法

尺取り法っぽくやる。全員分の行きチケットを確保したとき、使える帰りチケットは行きチケットの中で一番遅い日付+K日目以降のものだけになる。逆にいえば、以降であればどれでも使えることになるので、帰りのチケットの価格はそれより後ろのチケットの価格の最小値とみなしてしまってよい。あとは行きのチケット・帰りのチケットをそれぞれ日付順に並べてキューに突っ込み、行きキューから日付を一個取り出すごとに帰りのキューから行きの日付+Kより小さいものを弾いていく。こうすると行きチケットは既にキューから取り出したものがすべて使え、帰りチケットはまだ取り出してないものがすべて使えることになる。この過程でそれぞれの番号のチケットの値を管理していけば逐次最小値を更新していくことができる。

感想

解法自体はそんなに複雑ではないが細かいところをいろいろ気を付けなければならずかなりしんどい問題だと思った。こういうのにも慣れていかないとな~~~~~~

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

immutable long INF = 1L << 59;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto K = s[2];

    auto go = new Tuple!(int, long)[][](N);
    auto back = new Tuple!(int, long)[][](N);

    foreach (_; 0..M) {
        s = readln.split.map!(to!int);
        if (s[2] == 0)
            go[s[1]-1] ~= tuple(s[0], s[3].to!long);
        else
            back[s[2]-1] ~= tuple(s[0], s[3].to!long);
    }

    foreach (i; 0..N)
        go[i].sort!"a[0] < b[0]"();
    foreach (i; 0..N)
        back[i].sort!"a[0] < b[0]"();

    if (go.map!(g => g.length == 0).any ||
        back.map!(b => b.length == 0).any) {
        writeln(-1);
        return;
    }

    foreach (i; 0..N)
        foreach (j; 1..go[i].length) 
            go[i][j][1] = min(go[i][j][1], go[i][j-1][1]);
    
    foreach (i; 0..N) 
        for (int j = back[i].length.to!int - 1; j >= 1; --j)
            back[i][j-1][1] = min(back[i][j-1][1], back[i][j][1]);


    auto q1 = new BinaryHeap!(Array!(Tuple!(int, int, long)), "a[0] > b[0]");
    auto q2 = new BinaryHeap!(Array!(Tuple!(int, int, long)), "a[0] > b[0]");
    
    foreach (i; 0..N)
        foreach (j; 0..go[i].length)
            q1.insert(tuple(go[i][j][0], i, go[i][j][1]));
    foreach (i; 0..N)
        foreach (j; 0..back[i].length)
            q2.insert(tuple(back[i][j][0], i, (j + 1 == back[i].length ? INF : back[i][j+1][1])));

    int used_cnt = 0;
    auto used = new bool[](N);
    auto ans1 = new long[](N);
    auto ans2 = new long[](N);
    foreach (i; 0..N)
        ans2[i] = back[i][0][1];
    long sum1 = 0;
    long sum2 = ans2.sum;
    long ans = INF;
    bool end = false;
    
    
    while (!q1.empty && !end) {
        auto t = q1.front;
        auto d = t[0];
        auto n = t[1];
        auto c = t[2];
        q1.removeFront;
        sum1 -= ans1[n];
        ans1[n] = c;
        sum1 += ans1[n];
        if (!used[n]) {
            used_cnt += 1;
            used[n] = true;
        }

        if (used_cnt < N)
            continue;


        while (!q2.empty && q2.front()[0] <= d + K) {
            t = q2.front;
            n = t[1];
            c = t[2];
            q2.removeFront;
            
            if (c == INF) {
                end = true;
                break;
            }
                
            sum2 -= ans2[n];
            ans2[n] = c;
            sum2 += ans2[n];
        }

        if (!end)
            ans = min(ans, sum1 + sum2);
    }

    if (ans >= INF)
        ans = -1;
    ans.writeln;
}