#1149298 (C++23) No.5023 Airlines Optimization

• 問題: No.5023 Airlines Optimization
• ユーザー: prussian_coder
• 提出日時: 2026-02-25 21:44:43
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 905 ms / 1,000 ms
• コード長: 10,129 bytes
• コンパイル時間: 4,471 ms
• コンパイル使用メモリ: 362,196 KB
• 実行使用メモリ: 7,844 KB
• スコア: 37,622,713
• 最終ジャッジ日時: 2026-02-25 21:46:25
• 合計ジャッジ時間: 101,137 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

ファイルパターン	結果
other	AC * 100

ソースコード

#include <bits/stdc++.h>
using namespace std;

const int N = 47;
const int MF = 400;
const int K = 25;
const int TMIN = 360;
const int TMAX = 1260;
const int NT = 21;
const int NINF = -1000000;

int cx[N], cy[N], cw[N];
int sqa[MF], sqb[MF], sqs[MF], sqt_[MF];
int ft[N][N];
bool vp[N][N];
int tgt[NT];
int ssq[N][N][NT];

mt19937 rng(42);

int parse_time(const char* s) {
    return (s[0]-'0')*600 + (s[1]-'0')*60 + (s[3]-'0')*10 + (s[4]-'0');
}

string fmt(int t) {
    char b[6];
    b[0]='0'+t/600; t%=600; b[1]='0'+t/60; t%=60;
    b[2]=':'; b[3]='0'+t/10; b[4]='0'+t%10; b[5]=0;
    return string(b);
}

int cft(double d) {
    return ((int)ceil((60.0*d/800.0+40.0)/5.0))*5;
}

void compute_sq() {
    struct E { int arr, dep, from; };
    vector<E> rev[N];
    for (int i = 0; i < MF; i++)
        rev[sqb[i]].push_back({sqt_[i], sqs[i], sqa[i]});
    for (int i = 0; i < N; i++)
        sort(rev[i].begin(), rev[i].end(), [](auto& a, auto& b){ return a.arr > b.arr; });

    for (int ti = 0; ti < NT; ti++) {
        int T = tgt[ti];
        for (int j = 0; j < N; j++) {
            int best[N]; fill(best, best+N, NINF);
            best[j] = T;
            priority_queue<pair<int,int>> pq;
            pq.push({T, j});
            while (!pq.empty()) {
                auto [at, c] = pq.top(); pq.pop();
                if (at < best[c]) continue;
                for (auto& e : rev[c]) {
                    if (e.arr > at) continue;
                    if (e.dep > best[e.from]) {
                        best[e.from] = e.dep;
                        pq.push({e.dep, e.from});
                    }
                }
            }
            for (int i = 0; i < N; i++) ssq[i][j][ti] = best[i];
        }
    }
}

struct Flight { int from, to, dep, arr; };
struct Plane { vector<Flight> fs; };

vector<Flight> build(const vector<int>& cities, int start) {
    vector<Flight> fs;
    int ct = start;
    for (int i = 0; i+1 < (int)cities.size(); i++) {
        int a = cities[i], b = cities[i+1];
        if (a == b) continue;
        int d = ((ct+4)/5)*5;
        if (d < TMIN) d = TMIN;
        int ar = d + ft[a][b];
        if (ar > TMAX) break;
        fs.push_back({a, b, d, ar});
        ct = ar;
    }
    return fs;
}

bool valid(const Plane& p) {
    for (int j = 0; j < (int)p.fs.size(); j++) {
        auto& f = p.fs[j];
        if (f.from == f.to || f.dep < TMIN || f.arr > TMAX) return false;
        if (f.dep%5 || f.arr%5) return false;
        if (f.arr - f.dep != ft[f.from][f.to]) return false;
        if (j > 0 && (p.fs[j-1].to != f.from || p.fs[j-1].arr > f.dep)) return false;
    }
    return true;
}

// Global circle flight list for evaluation
struct CF { int from, to, dep, arr; };
int nf_global;
CF cfs_global[500];

// Precompute: for each city, list of flights arriving there (indices into cfs_global)
int rev_idx[N][500];
int rev_cnt[N];

void build_rev() {
    for (int i = 0; i < N; i++) rev_cnt[i] = 0;
    for (int i = 0; i < nf_global; i++) {
        int to = cfs_global[i].to;
        rev_idx[to][rev_cnt[to]++] = i;
    }
}

void collect_flights(const vector<Plane>& planes) {
    nf_global = 0;
    for (auto& p : planes)
        for (auto& f : p.fs)
            cfs_global[nf_global++] = {f.from, f.to, f.dep, f.arr};
    build_rev();
}

// Evaluation using Dijkstra (max-heap) for latest departure
// For each (j, ti): find latest departure from each i to reach j by tgt[ti]
long long eval_score() {
    long long v_ci = 0;

    for (int ti = 0; ti < NT; ti++) {
        int T = tgt[ti];
        for (int j = 0; j < N; j++) {
            int best[N]; fill(best, best+N, NINF);
            best[j] = T;

            // Max-heap Dijkstra: (time_at_city, city)
            priority_queue<pair<int,int>> pq;
            pq.push({T, j});

            while (!pq.empty()) {
                auto [at, c] = pq.top(); pq.pop();
                if (at < best[c]) continue;
                for (int ri = 0; ri < rev_cnt[c]; ri++) {
                    auto& e = cfs_global[rev_idx[c][ri]];
                    if (e.arr <= at && e.dep > best[e.from]) {
                        best[e.from] = e.dep;
                        pq.push({e.dep, e.from});
                    }
                }
            }

            for (int i = 0; i < N; i++) {
                if (vp[i][j] && best[i] > ssq[i][j][ti]) {
                    v_ci += (long long)cw[i]*cw[j];
                }
            }
        }
    }
    return v_ci;
}

int main() {
    auto t0 = chrono::steady_clock::now();
    auto el = [&]() { return chrono::duration<double>(chrono::steady_clock::now()-t0).count(); };

    int n, r; scanf("%d%d", &n, &r);
    for (int i = 0; i < N; i++) scanf("%d%d%d", &cx[i], &cy[i], &cw[i]);

    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        if (i == j) { ft[i][j] = 0; vp[i][j] = false; continue; }
        double dx = cx[i]-cx[j], dy = cy[i]-cy[j];
        double d = sqrt(dx*dx+dy*dy);
        ft[i][j] = cft(d);
        vp[i][j] = d >= 250.0;
    }

    int m; scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        char s1[6], s2[6];
        scanf("%d%5s%d%5s", &sqa[i], s1, &sqb[i], s2);
        sqa[i]--; sqb[i]--;
        sqs[i] = parse_time(s1);
        sqt_[i] = parse_time(s2);
    }
    int k; scanf("%d", &k);
    for (int i = 0; i < NT; i++) tgt[i] = 660 + i*30;

    compute_sq();

    long long tw = 0;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
        if (vp[i][j]) tw += (long long)cw[i]*cw[j];
    tw *= NT;

    fprintf(stderr, "Precomp: %.3fs\n", el());

    vector<Plane> planes(K);

    auto shuttle = [](int hub, int spoke, int start) -> vector<Flight> {
        vector<int> route;
        int cur = hub, ct = start;
        route.push_back(cur);
        while (true) {
            int next = (cur==hub)?spoke:hub;
            int d = ((ct+4)/5)*5;
            if (d < TMIN) d = TMIN;
            if (d+ft[cur][next] > TMAX) break;
            route.push_back(next);
            ct = d+ft[cur][next];
            cur = next;
        }
        return build(route, start);
    };

    // Try multiple initial configurations, pick the best
    // Build initial solution: hub-spoke shuttles
    // 25 planes assigned to (hub, spoke) pairs covering top cities
    int asgn[][2] = {
        {0,1},{0,2},{0,3},{0,4},{0,5},{0,6},{0,7},{0,8},
        {1,0},{1,2},{1,3},{1,4},{1,5},{1,6},
        {2,0},{2,1},{2,3},{2,4},{2,5},
        {0,9},{0,10},{0,11},{0,12},{0,13},{0,14}
    };
    for (int i = 0; i < K; i++)
        planes[i].fs = shuttle(asgn[i][0], asgn[i][1], TMIN + i*12);

    collect_flights(planes);
    long long cur = eval_score();
    long long best = cur;
    vector<Plane> best_p = planes;
    fprintf(stderr, "Best init: %lld share=%.4f (%.3fs)\n", cur, (double)cur/tw, el());

    // SA
    double sa_lim = 0.90;
    double Ts = 3e13, Te = 1e9;
    int it = 0, ac = 0;

    while (el() < sa_lim) {
        double prog = el()/sa_lim;
        double T = Ts * pow(Te/Ts, prog);
        it++;

        int pi = rng() % K;
        Plane old = planes[pi];
        int op = rng() % 100;

        if (op < 40) {
            int hub, spoke;
            int r2 = rng()%10;
            hub = (r2<5)?0:(r2<8)?1:2;
            spoke = rng()%N;
            if (spoke == hub) spoke = (hub+1+rng()%(N-1))%N;
            int start = TMIN + (rng()%72)*5;
            planes[pi].fs = shuttle(hub, spoke, start);
        } else if (op < 60) {
            int shift = ((int)(rng()%9)-4)*5;
            if (!shift) shift = 5;
            bool ok = true;
            for (auto& f : planes[pi].fs) {
                f.dep += shift; f.arr += shift;
                if (f.dep < TMIN || f.arr > TMAX) { ok = false; break; }
            }
            if (!ok) { planes[pi] = old; continue; }
        } else if (op < 80) {
            int sc; int r2=rng()%10;
            sc = (r2<4)?rng()%3:(r2<7)?rng()%10:rng()%N;
            int start = TMIN + (rng()%72)*5;
            vector<int> route = {sc};
            int c = sc, ct = start;
            for (int t = 0; t < 15; t++) {
                int nx; int r3=rng()%10;
                nx = (r3<3)?rng()%3:(r3<6)?rng()%10:(r3<8)?rng()%20:rng()%N;
                if (nx == c) continue;
                int d = ((ct+4)/5)*5;
                if (d < TMIN) d = TMIN;
                if (d+ft[c][nx] > TMAX) continue;
                route.push_back(nx);
                ct = d+ft[c][nx];
                c = nx;
            }
            planes[pi].fs = build(route, start);
        } else {
            auto& fs = planes[pi].fs;
            if (fs.size() < 2) { planes[pi] = old; continue; }
            int split = 1+rng()%((int)fs.size()-1);
            int c = fs[split-1].to, ct = fs[split-1].arr;
            vector<Flight> nfs(fs.begin(), fs.begin()+split);
            for (int t = 0; t < 10; t++) {
                int nx; int r3=rng()%10;
                nx = (r3<3)?rng()%3:(r3<6)?rng()%10:rng()%N;
                if (nx == c) continue;
                int d = ((ct+4)/5)*5;
                if (d+ft[c][nx] > TMAX) break;
                nfs.push_back({c, nx, d, d+ft[c][nx]});
                ct = d+ft[c][nx]; c = nx;
            }
            planes[pi].fs = nfs;
        }

        if (!valid(planes[pi])) { planes[pi] = old; continue; }

        collect_flights(planes);
        long long ns = eval_score();
        long long delta = ns - cur;
        if (delta > 0 || exp((double)delta/T) > (double)(rng()%1000000)/1e6) {
            cur = ns; ac++;
            if (cur > best) { best = cur; best_p = planes; }
        } else {
            planes[pi] = old;
        }
    }

    planes = best_p;
    fprintf(stderr, "SA: it=%d ac=%d best=%lld share=%.4f\n", it, ac, best, (double)best/tw);

    for (int p = 0; p < K; p++) {
        printf("%d\n", (int)planes[p].fs.size());
        for (auto& f : planes[p].fs) {
            string sd = fmt(f.dep), sa2 = fmt(f.arr);
            printf("%d %s %d %s\n", f.from+1, sd.c_str(), f.to+1, sa2.c_str());
        }
    }
    fprintf(stderr, "Score: %lld\nTotal: %.3fs\n", (long long)((double)best/tw*1e6), el());
    return 0;
}