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

• 問題: No.5023 Airlines Optimization
• ユーザー: Keroru
• 提出日時: 2026-02-27 21:52:47
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 957 ms / 1,000 ms
• コード長: 13,938 bytes
• コンパイル時間: 5,873 ms
• コンパイル使用メモリ: 387,488 KB
• 実行使用メモリ: 7,976 KB
• スコア: 31,920,339
• 最終ジャッジ日時: 2026-02-27 21:54:38
• 合計ジャッジ時間: 107,411 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

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

ソースコード

// baseline_score_0000_0014: 4062458
// improved_score_0000_0014: 4579779
// score_improvement_0000_0014: +517321
// 方針: 人口上位都市を中心に初期解を作り、連続化評価(exp平滑)と逆順DPで高速評価しながら焼きなましで時刻表を改善する。
// 変更点: 敵(スクエア航空)の強い航路を使う初期解、ドミノ倒し修復つき近傍(時刻シフト/目的地変更/挿入/削除)、終盤の全都市厳密化を実装。

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

constexpr int START_TIME = 6 * 60;
constexpr int END_TIME = 21 * 60;
constexpr double TL_SEC = 0.95;
constexpr double SA_TEMP_START = 200000.0;
constexpr double SA_TEMP_END = 2000.0;
constexpr double SMOOTH_C_START = 40.0;
constexpr double SMOOTH_C_END = 5.0;

struct Flight {
    int a, s, b, t;
};

struct Input {
    int N, R;
    vector<int> x, y, w;
    int M;
    vector<Flight> square;
    int K;
};

struct EvalResult {
    double smooth_score;
    long long binary_score;
};

struct XorShift {
    uint64_t x = 88172645463325252ULL;
    uint64_t next() {
        x ^= x << 7;
        x ^= x >> 9;
        return x;
    }
    int next_int(int l, int r) { return l + int(next() % uint64_t(r - l + 1)); }
    double next_double() { return (next() >> 11) * (1.0 / (1ULL << 53)); }
};

static int parse_time(const string& ts) {
    return (ts[0] - '0') * 600 + (ts[1] - '0') * 60 + (ts[3] - '0') * 10 + (ts[4] - '0');
}

static string fmt_time(int t) {
    ostringstream oss;
    oss << setw(2) << setfill('0') << (t / 60) << ':' << setw(2) << setfill('0') << (t % 60);
    return oss.str();
}

static int ceil5(int t) {
    if (t % 5 == 0) return t;
    return t + (5 - t % 5);
}

struct Solver {
    const Input& in;
    vector<vector<int>> dur;
    vector<pair<int, int>> pop_order;
    vector<int> top_cities;
    vector<pair<int, int>> enemy_strong_pairs;
    vector<int> target_times;
    vector<vector<vector<int>>> sq_latest;
    vector<vector<char>> valid_pair;
    XorShift rng;

    explicit Solver(const Input& in_) : in(in_) {
        build_duration();
        build_priority();
        build_enemy_strong_pairs();
        build_targets();
        precompute_square_latest();
        build_valid_pair();
    }

    void build_duration() {
        dur.assign(in.N, vector<int>(in.N, 0));
        for (int i = 0; i < in.N; ++i) for (int j = 0; j < in.N; ++j) if (i != j) {
            double d = hypot(double(in.x[i] - in.x[j]), double(in.y[i] - in.y[j]));
            double raw = 60.0 * d / 800.0 + 40.0;
            dur[i][j] = int(ceil(raw / 5.0) * 5.0);
        }
    }

    void build_priority() {
        pop_order.clear();
        for (int i = 0; i < in.N; ++i) pop_order.push_back({in.w[i], i});
        sort(pop_order.rbegin(), pop_order.rend());
        int use = min(in.N, 15);
        top_cities.clear();
        for (int i = 0; i < use; ++i) top_cities.push_back(pop_order[i].second);
    }

    void build_targets() {
        target_times.clear();
        for (int t = 11 * 60; t <= 21 * 60; t += 30) target_times.push_back(t);
    }

    void build_enemy_strong_pairs() {
        vector<vector<double>> score(in.N, vector<double>(in.N, 0.0));
        for (const auto& f : in.square) {
            score[f.a][f.b] += double(in.w[f.a]) * in.w[f.b];
        }

        struct Cand {
            double score;
            int u, v;
        };
        vector<Cand> cands;
        cands.reserve(in.N * (in.N - 1) / 2);
        for (int i = 0; i < in.N; ++i) {
            for (int j = i + 1; j < in.N; ++j) {
                double s = score[i][j] + score[j][i];
                if (s <= 0.0) continue;
                cands.push_back({s, i, j});
            }
        }
        sort(cands.begin(), cands.end(), [](const Cand& l, const Cand& r) { return l.score > r.score; });

        enemy_strong_pairs.clear();
        for (const auto& c : cands) enemy_strong_pairs.push_back({c.u, c.v});
    }

    vector<int> latest_departures(const vector<Flight>& sorted_desc, int target_city, int target_time) const {
        const int NEG = -1e9;
        vector<int> latest(in.N, NEG);
        latest[target_city] = target_time;
        for (const auto& f : sorted_desc) {
            if (f.t <= latest[f.b]) latest[f.a] = max(latest[f.a], f.s);
        }
        return latest;
    }

    void precompute_square_latest() {
        vector<Flight> sq = in.square;
        sort(sq.begin(), sq.end(), [](const Flight& l, const Flight& r) { return l.s > r.s; });
        int T = (int)target_times.size();
        sq_latest.assign(T, vector<vector<int>>(in.N, vector<int>(in.N, -1000000000)));
        for (int ti = 0; ti < T; ++ti) {
            for (int goal = 0; goal < in.N; ++goal) {
                sq_latest[ti][goal] = latest_departures(sq, goal, target_times[ti]);
            }
        }
    }

    void build_valid_pair() {
        valid_pair.assign(in.N, vector<char>(in.N, 0));
        const double th = 0.25 * in.R;
        for (int i = 0; i < in.N; ++i) {
            for (int j = 0; j < in.N; ++j) {
                valid_pair[i][j] = (hypot(double(in.x[i] - in.x[j]), double(in.y[i] - in.y[j])) >= th);
            }
        }
    }

    void repair_plane(vector<Flight>& p) {
        for (int i = 0; i < (int)p.size(); ++i) {
            if (i > 0) {
                p[i].a = p[i - 1].b;
                p[i].s = max(p[i].s, p[i - 1].t);
            }
            p[i].s = max(p[i].s, START_TIME);
            p[i].s = ceil5(p[i].s);
            if (p[i].a == p[i].b) p[i].b = (p[i].b + 1) % in.N;
            p[i].t = p[i].s + dur[p[i].a][p[i].b];
            if (p[i].s > END_TIME || p[i].t > END_TIME) {
                p.resize(i);
                return;
            }
        }
    }

    vector<vector<Flight>> build_initial() {
        vector<vector<Flight>> plans(in.K);

        vector<pair<int, int>> seeds = enemy_strong_pairs;
        if (seeds.empty()) {
            int hubs = min(6, (int)top_cities.size());
            for (int i = 0; i < hubs; ++i) {
                int a = top_cities[i];
                int b = top_cities[(i + 1) % hubs];
                if (a == b) b = (b + 1) % in.N;
                seeds.push_back({a, b});
            }
        }

        for (int k = 0; k < in.K; ++k) {
            auto [hub, dst] = seeds[k % (int)seeds.size()];
            int cur = START_TIME + (k % 4) * 5;
            while (true) {
                Flight f1{hub, cur, dst, 0};
                f1.t = f1.s + dur[f1.a][f1.b];
                if (f1.t > END_TIME) break;
                plans[k].push_back(f1);
                cur = f1.t;
                Flight f2{dst, cur, hub, 0};
                f2.t = f2.s + dur[f2.a][f2.b];
                if (f2.t > END_TIME) break;
                plans[k].push_back(f2);
                cur = f2.t;
            }
        }
        return plans;
    }

    EvalResult evaluate(const vector<vector<Flight>>& plans, double smooth_c, bool full_city) const {
        vector<Flight> all;
        all.reserve(800);
        for (const auto& p : plans) for (const auto& f : p) all.push_back(f);
        sort(all.begin(), all.end(), [](const Flight& l, const Flight& r) { return l.s > r.s; });

        vector<int> city_set;
        if (full_city) {
            city_set.resize(in.N);
            iota(city_set.begin(), city_set.end(), 0);
        } else {
            city_set = top_cities;
        }

        double smooth = 0.0;
        long long v_ci = 0, v_sq = 0;
        for (int ti = 0; ti < (int)target_times.size(); ++ti) {
            for (int goal : city_set) {
                vector<int> ci_latest = latest_departures(all, goal, target_times[ti]);
                const auto& sq = sq_latest[ti][goal];
                for (int i = 0; i < in.N; ++i) {
                    if (!valid_pair[i][goal]) continue;
                    long long w = 1LL * in.w[i] * in.w[goal];
                    int d = ci_latest[i] - sq[i];
                    if (d > 0) {
                        smooth += (double)w;
                        v_ci += w;
                    } else {
                        if (smooth_c > 1e-9) smooth += (double)w * exp((double)d / smooth_c);
                        v_sq += w;
                    }
                }
            }
        }
        long long binary = (v_ci + v_sq == 0) ? 0LL : (1000000LL * v_ci) / (v_ci + v_sq);
        return {smooth, binary};
    }

    void mutate(vector<vector<Flight>>& plans, int type) {
        int pid = rng.next_int(0, in.K - 1);
        auto& p = plans[pid];
        auto rand_city = [&]() { return top_cities[rng.next_int(0, (int)top_cities.size() - 1)]; };

        if (type == 0) {
            if (p.empty()) type = 2;
            else {
                int i = rng.next_int(0, (int)p.size() - 1);
                int d = (rng.next_int(0, 1) ? 5 : 10) * (rng.next_int(0, 1) ? 1 : -1);
                p[i].s = max(START_TIME, min(END_TIME, p[i].s + d));
            }
        }
        if (type == 1) {
            if (p.empty()) type = 2;
            else {
                int i = rng.next_int(0, (int)p.size() - 1);
                int nb = rand_city();
                if (nb == p[i].a) nb = (nb + 1) % in.N;
                p[i].b = nb;
            }
        }
        if (type == 2) {
            int pos = p.empty() ? 0 : rng.next_int(0, (int)p.size());
            Flight f{};
            if (pos == 0) {
                f.a = rand_city();
                f.s = START_TIME + 5 * rng.next_int(0, (END_TIME - START_TIME) / 5);
            } else {
                f.a = p[pos - 1].b;
                f.s = p[pos - 1].t;
            }
            f.b = rand_city();
            if (f.b == f.a) f.b = (f.b + 1) % in.N;
            f.t = f.s + dur[f.a][f.b];
            p.insert(p.begin() + pos, f);
        }
        if (type == 3) {
            if (!p.empty()) {
                int i = rng.next_int(0, (int)p.size() - 1);
                p.erase(p.begin() + i);
            }
        }
        repair_plane(p);
    }

    pair<long long, string> run() {
        vector<vector<Flight>> cur = build_initial();
        vector<vector<Flight>> best = cur;

        auto t0 = chrono::steady_clock::now();
        EvalResult cur_eval = evaluate(cur, SMOOTH_C_START, false);
        EvalResult best_eval = cur_eval;

        long long loops = 0;
        array<long long, 4> acc{}, tried{};
        double next_log = 0.1;

        while (true) {
            double elapsed = chrono::duration<double>(chrono::steady_clock::now() - t0).count();
            if (elapsed >= TL_SEC) break;
            double p = elapsed / TL_SEC;
            double temp = SA_TEMP_START * pow(SA_TEMP_END / SA_TEMP_START, p);
            double smooth_c = SMOOTH_C_START + (SMOOTH_C_END - SMOOTH_C_START) * p;
            bool full_city = (p > 0.88);

            int type = rng.next_int(0, 99);
            if (type < 50) type = 0;
            else if (type < 75) type = 1;
            else if (type < 90) type = 2;
            else type = 3;
            ++tried[type];

            auto nxt = cur;
            mutate(nxt, type);
            EvalResult nxt_eval = evaluate(nxt, smooth_c, full_city);

            double delta = nxt_eval.smooth_score - cur_eval.smooth_score;
            bool accept = false;
            if (delta >= 0.0) accept = true;
            else accept = (exp(delta / temp) > rng.next_double());

            if (accept) {
                ++acc[type];
                cur.swap(nxt);
                cur_eval = nxt_eval;
                if (cur_eval.smooth_score > best_eval.smooth_score) {
                    best = cur;
                    best_eval = cur_eval;
                }
            }
            ++loops;

            if (elapsed >= next_log) {
                cerr << fixed << setprecision(3)
                     << "t=" << elapsed
                     << " best_smooth=" << best_eval.smooth_score
                     << " acc=" << (tried[0] ? (double)acc[0] / tried[0] : 0.0) << ','
                     << (tried[1] ? (double)acc[1] / tried[1] : 0.0) << ','
                     << (tried[2] ? (double)acc[2] / tried[2] : 0.0) << ','
                     << (tried[3] ? (double)acc[3] / tried[3] : 0.0) << '\n';
                next_log += 0.1;
            }
        }

        EvalResult final_eval = evaluate(best, 0.0, true);

        ostringstream out;
        for (int k = 0; k < in.K; ++k) {
            out << best[k].size() << '\n';
            for (auto& f : best[k]) {
                out << (f.a + 1) << ' ' << fmt_time(f.s) << ' ' << (f.b + 1) << ' ' << fmt_time(f.t) << '\n';
            }
        }

        cerr << final_eval.binary_score << '\n';
        cerr << "TL=" << TL_SEC << " T0=" << SA_TEMP_START << " T1=" << SA_TEMP_END
             << " C0=" << SMOOTH_C_START << " C1=" << SMOOTH_C_END << '\n';
        cerr << "loops=" << loops << '\n';

        return {final_eval.binary_score, out.str()};
    }
};

pair<long long, string> solve(const Input& in) {
    Solver solver(in);
    return solver.run();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Input in;
    string n_token;
    cin >> n_token >> in.R;
    if (n_token.size() >= 3 &&
        (unsigned char)n_token[0] == 0xEF &&
        (unsigned char)n_token[1] == 0xBB &&
        (unsigned char)n_token[2] == 0xBF) {
        n_token = n_token.substr(3);
    }
    in.N = stoi(n_token);
    in.x.resize(in.N);
    in.y.resize(in.N);
    in.w.resize(in.N);
    for (int i = 0; i < in.N; ++i) cin >> in.x[i] >> in.y[i] >> in.w[i];
    cin >> in.M;
    in.square.resize(in.M);
    for (int i = 0; i < in.M; ++i) {
        string ss, tt;
        cin >> in.square[i].a >> ss >> in.square[i].b >> tt;
        --in.square[i].a;
        --in.square[i].b;
        in.square[i].s = parse_time(ss);
        in.square[i].t = parse_time(tt);
    }
    cin >> in.K;

    auto [est, output] = solve(in);
    cout << output;
    return 0;
}