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

• 問題: No.5023 Airlines Optimization
• ユーザー: Shun_PI
• 提出日時: 2026-02-25 22:50:58
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 905 ms / 1,000 ms
• コード長: 11,535 bytes
• コンパイル時間: 4,587 ms
• コンパイル使用メモリ: 364,556 KB
• 実行使用メモリ: 7,848 KB
• スコア: 48,487,291
• 最終ジャッジ日時: 2026-02-25 22:52:40
• 合計ジャッジ時間: 100,813 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

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

ソースコード

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

// ========== Constants ==========
const int T_START = 360;    // 06:00 in minutes from 00:00
const int T_END   = 1260;   // 21:00
const int T_STEP  = 5;
const int NUM_TARGETS = 21; // 11:00, 11:30, ..., 21:00
const int NEG_INF = -999999;

// ========== Data Structures ==========
int N, R, M, K;
double px[50], py[50]; // 1-indexed
int pw[50];            // population

struct Flight {
    int a, b; // cities (1-indexed)
    int s, t; // departure, arrival (minutes)
};

vector<Flight> sq_flights;

double dist_tab[50][50];
int ftime_tab[50][50];       // minimum flight time
vector<int> vsrc[50];        // vsrc[j] = valid sources for destination j
int target_t[NUM_TARGETS];

// Square Airlines: precomputed latest departure
// sq_lat[j][k][i] = latest dep from city i to reach j by target_t[k]
int sq_lat[50][NUM_TARGETS][50];

// Circle Airlines state
int plane_start[26];    // 1-indexed
vector<int> route[26];  // city sequence per plane

mt19937 rng;

// Weighted city sampling (proportional to population)
long long cum_w[50]; // cumulative weights, 1-indexed
long long total_w;

int sample_city() {
    long long r = (long long)(rng() % total_w);
    // binary search: find smallest c such that cum_w[c] > r
    int lo = 1, hi = N;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (cum_w[mid] <= r) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// Sample from a candidate list, weighted by pw
int sample_from(const vector<int>& cands) {
    if (cands.size() == 1) return cands[0];
    long long s = 0;
    for (int c : cands) s += pw[c];
    long long r = (long long)(rng() % s);
    long long acc = 0;
    for (int c : cands) {
        acc += pw[c];
        if (acc > r) return c;
    }
    return cands.back();
}

// ========== Time Utilities ==========
int parse_time(const char* s) {
    int h, m;
    sscanf(s, "%d:%d", &h, &m);
    return h * 60 + m;
}

// ========== Precomputation ==========
void precompute() {
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++) {
            double dx = px[i] - px[j], dy = py[i] - py[j];
            dist_tab[i][j] = sqrt(dx * dx + dy * dy);
        }
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++) {
            if (i == j) { ftime_tab[i][j] = 0; continue; }
            double raw = 60.0 * dist_tab[i][j] / 800.0 + 40.0;
            ftime_tab[i][j] = (int)ceil(raw / 5.0) * 5;
        }
    for (int j = 1; j <= N; j++)
        for (int i = 1; i <= N; i++)
            if (i != j && dist_tab[i][j] >= 0.25 * R)
                vsrc[j].push_back(i);
    for (int k = 0; k < NUM_TARGETS; k++)
        target_t[k] = 660 + 30 * k; // 11:00 to 21:00

    // Cumulative weights for weighted city sampling
    cum_w[0] = 0;
    for (int i = 1; i <= N; i++)
        cum_w[i] = cum_w[i - 1] + pw[i];
    total_w = cum_w[N];
}

// ========== Latest Departure Computation ==========
// sorted_flights must be sorted by arrival time DESCENDING.
// Computes lat[c] = latest departure time from city c to reach dest by deadline.
// lat[c] = NEG_INF means unreachable.
void compute_latest(const vector<Flight>& sorted_flights, int dest, int deadline, int lat[]) {
    for (int c = 1; c <= N; c++) lat[c] = NEG_INF;
    lat[dest] = deadline;
    for (const auto& f : sorted_flights) {
        if (lat[f.b] != NEG_INF && f.t <= lat[f.b]) {
            if (f.s > lat[f.a]) lat[f.a] = f.s;
        }
    }
}

// ========== Precompute Square Airlines ==========
void precompute_sq() {
    vector<Flight> sorted = sq_flights;
    sort(sorted.begin(), sorted.end(), [](const Flight& a, const Flight& b) {
        return a.t > b.t;
    });
    for (int j = 1; j <= N; j++)
        for (int k = 0; k < NUM_TARGETS; k++)
            compute_latest(sorted, j, target_t[k], sq_lat[j][k]);
}

// ========== Flight Generation from Routes ==========
// Generate flights for one plane (ASAP scheduling from plane_start)
vector<Flight> gen_plane_flights(int p) {
    vector<Flight> res;
    const auto& rt = route[p];
    if ((int)rt.size() < 2) return res;
    int cur = plane_start[p];
    for (int i = 0; i + 1 < (int)rt.size(); i++) {
        int a = rt[i], b = rt[i + 1];
        int ft = ftime_tab[a][b];
        int arr = cur + ft;
        if (arr > T_END) break;
        res.push_back({a, b, cur, arr});
        cur = arr;
    }
    return res;
}

// Generate all Circle Airlines flights, sorted by arrival descending
vector<Flight> gen_all_ci_sorted() {
    vector<Flight> all;
    for (int p = 1; p <= K; p++) {
        auto fl = gen_plane_flights(p);
        for (auto& f : fl) all.push_back(f);
    }
    sort(all.begin(), all.end(), [](const Flight& a, const Flight& b) {
        return a.t > b.t;
    });
    return all;
}

// ========== Score Computation ==========
// Returns v_ci (sum of w_i*w_j for triples where Circle beats Square)
long long eval_score(const vector<Flight>& ci_sorted) {
    long long v_ci = 0;
    int lat[50];
    for (int j = 1; j <= N; j++) {
        for (int k = 0; k < NUM_TARGETS; k++) {
            compute_latest(ci_sorted, j, target_t[k], lat);
            for (int i : vsrc[j]) {
                // s_sq < s_ci => Circle wins
                if (sq_lat[j][k][i] < lat[i])
                    v_ci += (long long)pw[i] * pw[j];
            }
        }
    }
    return v_ci;
}

int main() {
    rng.seed(chrono::steady_clock::now().time_since_epoch().count());

    // ---- Input ----
    scanf("%d %d", &N, &R);
    for (int i = 1; i <= N; i++)
        scanf("%lf %lf %d", &px[i], &py[i], &pw[i]);
    scanf("%d", &M);
    sq_flights.resize(M);
    for (int i = 0; i < M; i++) {
        char ss[10], tt[10];
        scanf("%d %s %d %s", &sq_flights[i].a, ss, &sq_flights[i].b, tt);
        sq_flights[i].s = parse_time(ss);
        sq_flights[i].t = parse_time(tt);
    }
    scanf("%d", &K);

    precompute();
    precompute_sq();

    // ---- Initial Solution ----
    // Each plane: start at weighted-random city, greedily add reachable cities
    for (int p = 1; p <= K; p++) {
        plane_start[p] = T_START;
        route[p].clear();
        int city = sample_city();
        route[p].push_back(city);
        int cur = T_START;
        while (true) {
            int last = route[p].back();
            vector<int> cands;
            for (int c = 1; c <= N; c++) {
                if (c == last) continue;
                if (cur + ftime_tab[last][c] <= T_END)
                    cands.push_back(c);
            }
            if (cands.empty()) break;
            int next = sample_from(cands);
            route[p].push_back(next);
            cur += ftime_tab[last][next];
        }
    }

    // ---- Simulated Annealing ----
    auto ci_sorted = gen_all_ci_sorted();
    long long cur_score = eval_score(ci_sorted);
    long long best_score = cur_score;

    vector<int> best_route[26];
    int best_start[26];
    for (int p = 1; p <= K; p++) {
        best_route[p] = route[p];
        best_start[p] = plane_start[p];
    }

    auto t0 = chrono::steady_clock::now();
    double time_limit = 0.9;
    int iter = 0;

    while (true) {
        auto now = chrono::steady_clock::now();
        double elapsed = chrono::duration<double>(now - t0).count();
        if (elapsed >= time_limit) break;

        double progress = elapsed / time_limit;
        // Exponential temperature schedule
        double temp = 1e13 * pow(1e-4, progress); // 1e13 -> 1e9

        // Pick a random plane
        int p = rng() % K + 1;
        auto old_route = route[p];
        int old_start = plane_start[p];

        // Choose mutation type
        int mut = rng() % 6;

        if (mut == 0 && (int)route[p].size() >= 2) {
            // Change a random city in the route
            int pos = rng() % (int)route[p].size();
            int new_city = sample_city();
            route[p][pos] = new_city;
        } else if (mut == 1) {
            // Insert a random city
            int pos = rng() % ((int)route[p].size() + 1);
            int new_city = sample_city();
            route[p].insert(route[p].begin() + pos, new_city);
        } else if (mut == 2 && (int)route[p].size() >= 2) {
            // Remove a random city
            int pos = rng() % (int)route[p].size();
            route[p].erase(route[p].begin() + pos);
        } else if (mut == 3 && (int)route[p].size() >= 3) {
            // Swap two random positions
            int a = rng() % (int)route[p].size();
            int b = rng() % (int)route[p].size();
            swap(route[p][a], route[p][b]);
        } else if (mut == 4) {
            // Change start time
            int delta = ((int)(rng() % 13) - 6) * T_STEP; // -30 to +30 min
            int ns = plane_start[p] + delta;
            ns = max(T_START, min(T_END, ns));
            plane_start[p] = ns;
        } else {
            // Reinitialize this plane's route
            route[p].clear();
            int city = sample_city();
            route[p].push_back(city);
            int cur = plane_start[p];
            while (true) {
                int last = route[p].back();
                vector<int> cands;
                for (int c = 1; c <= N; c++) {
                    if (c == last) continue;
                    if (cur + ftime_tab[last][c] <= T_END)
                        cands.push_back(c);
                }
                if (cands.empty()) break;
                int next = sample_from(cands);
                route[p].push_back(next);
                cur += ftime_tab[last][next];
            }
        }

        // Validate: no consecutive duplicates, cities in range
        bool valid = true;
        for (int c : route[p])
            if (c < 1 || c > N) { valid = false; break; }
        if (valid) {
            for (int i = 0; i + 1 < (int)route[p].size(); i++)
                if (route[p][i] == route[p][i + 1]) { valid = false; break; }
        }
        if (!valid || route[p].empty()) {
            route[p] = old_route;
            plane_start[p] = old_start;
            continue;
        }

        // Evaluate
        auto new_ci = gen_all_ci_sorted();
        long long new_score = eval_score(new_ci);

        long long d = new_score - cur_score;
        bool accept = false;
        if (d >= 0) {
            accept = true;
        } else if (temp > 0) {
            double prob = exp((double)d / temp);
            if ((double)(rng() % 1000000) / 1000000.0 < prob)
                accept = true;
        }

        if (accept) {
            cur_score = new_score;
            ci_sorted = new_ci;
            if (new_score > best_score) {
                best_score = new_score;
                for (int q = 1; q <= K; q++) {
                    best_route[q] = route[q];
                    best_start[q] = plane_start[q];
                }
            }
        } else {
            route[p] = old_route;
            plane_start[p] = old_start;
        }
        iter++;
    }

    // Restore best solution
    for (int p = 1; p <= K; p++) {
        route[p] = best_route[p];
        plane_start[p] = best_start[p];
    }

    fprintf(stderr, "SA: %d iters, best_score=%lld\n", iter, best_score);

    // ---- Output ----
    for (int p = 1; p <= K; p++) {
        auto flights = gen_plane_flights(p);
        printf("%d\n", (int)flights.size());
        for (auto& f : flights) {
            printf("%d %02d:%02d %d %02d:%02d\n",
                   f.a, f.s / 60, f.s % 60,
                   f.b, f.t / 60, f.t % 60);
        }
    }

    return 0;
}