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

• 問題: No.5023 Airlines Optimization
• ユーザー: tetra4
• 提出日時: 2026-02-25 23:43:52
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 991 ms / 1,000 ms
• コード長: 11,338 bytes
• コンパイル時間: 4,194 ms
• コンパイル使用メモリ: 361,008 KB
• 実行使用メモリ: 7,912 KB
• スコア: 60,907,461
• 最終ジャッジ日時: 2026-02-25 23:45:41
• 合計ジャッジ時間: 107,572 ms
• ジャッジサーバーID （参考情報）: judge7 / judge2

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

ソースコード

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

// --- 定数 ---
constexpr int N = 47, R = 1000, M = 400, K = 25;
constexpr int INF = 1e9;
constexpr int MAX_TIME_SLOTS = 182;
constexpr int MAX_FLIGHTS = 2500;

struct Flight {
    int u, s, v, t;
};

// --- 便利ツール ---
string to_time_str(int t) {
    int h = 6 + t / 12, m = (t % 12) * 5;
    char buf[10];
    snprintf(buf, sizeof(buf), "%02d:%02d", h, m);
    return string(buf);
}
// 乱数生成器
class PCG32_Fast {
    uint64_t state_{0x853c49e6748fea9bull};
    static constexpr uint64_t MULT = 6364136223846793005ull;
    inline uint32_t next() {
        uint64_t x = state_;
        unsigned count = (unsigned)(x >> 61);
        state_ = x * MULT;
        x ^= x >> 22;
        return (uint32_t)(x >> (22 + count));
    }

   public:
    using result_type = uint32_t;
    static constexpr uint32_t min() {
        return 0;
    }
    static constexpr uint32_t max() {
        return 0xFFFFFFFF;
    }
    constexpr PCG32_Fast() = default;
    inline void seed(uint64_t seed) {
        state_ = 2 * seed + 1;
        next();
    }
    inline uint32_t operator()() {
        return next();
    }
    inline uint32_t uniform(uint32_t n) {
        return (uint32_t)((uint64_t)next() * n >> 32);
    }
    inline uint32_t uniform(uint32_t l, uint32_t r) {
        return l + uniform(r - l);
    }
    inline float uniform_float() {
        return (float)next() * 2.3283064365386963e-10f;
    }
    inline float uniform_float(float l, float r) {
        return l + uniform_float() * (r - l);
    }
};
inline PCG32_Fast RNG;

// タイマー
class Timer {
    chrono::steady_clock::time_point start_time_;

   public:
    Timer() : start_time_(chrono::steady_clock::now()) {}
    inline void reset() {
        start_time_ = chrono::steady_clock::now();
    }
    [[nodiscard]] inline float elapsed() const {
        auto now = chrono::steady_clock::now();
        return chrono::duration<float>(now - start_time_).count();
    }
    [[nodiscard]] inline bool is_exceeded(float limit) const {
        return elapsed() > limit;
    }
};
inline Timer TIMER;

// --- データ管理 ---
struct Input {
    array<int, N> x, y, w;
    array<int, M> a, s, b, t;
    array<array<bool, N>, N> valid_dist{};
    array<array<long long, N>, N> weight{};
    long long total_W = 0;
    array<array<int, N>, N> dur;

    Input() {
        int _;
        cin >> _ >> _;
        for (int i = 0; i < N; ++i) cin >> x[i] >> y[i] >> w[i];
        int m_val;
        cin >> m_val;
        for (int i = 0; i < m_val; ++i) {
            string s_str, t_str;
            cin >> a[i] >> s_str >> b[i] >> t_str;
            --a[i];
            --b[i];
            s[i] = (stoi(s_str.substr(0, 2)) - 6) * 12 + stoi(s_str.substr(3, 2)) / 5;
            t[i] = (stoi(t_str.substr(0, 2)) - 6) * 12 + stoi(t_str.substr(3, 2)) / 5;
        }
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (i == j) continue;
                long long dx = x[i] - x[j], dy = y[i] - y[j];
                dur[i][j] = (int)ceil((60.0 * sqrt(dx * dx + dy * dy) / 800.0 + 40.0) / 5.0 - 1e-9);
                if (dx * dx + dy * dy >= (R * R) / 16) {
                    valid_dist[i][j] = true;
                    weight[i][j] = (long long)w[i] * w[j];
                    total_W += weight[i][j] * 21;
                }
            }
        }
    }
};

struct ComputeSciWorkspace {
    array<array<int, MAX_TIME_SLOTS>, N> head;
    array<int, MAX_FLIGHTS> nxt;
    array<array<bool, MAX_TIME_SLOTS>, N> reach;
};

struct MarginalGainWorkspace {
    array<array<array<int, 21>, N>, N> current_s_ci;
    array<array<array<long long, MAX_TIME_SLOTS>, N>, N> edge_gain;
    array<array<long long, MAX_TIME_SLOTS>, N> dp;
    array<array<int, MAX_TIME_SLOTS>, N> nxt_v;
};

// 共通計算関数
void compute_s_ci(const Input& in, const vector<Flight>& flights,
                  array<array<array<int, 21>, N>, N>& s_ci, ComputeSciWorkspace& ws) {
    for (int u = 0; u < N; ++u)
        for (int dst = 0; dst < N; ++dst) s_ci[u][dst].fill(-INF);
    for (int u = 0; u < N; ++u) ws.head[u].fill(-1);
    ws.nxt.fill(-1);
    for (int i = 0; i < (int)flights.size(); ++i) {
        int u = flights[i].u, s = flights[i].s;
        ws.nxt[i] = ws.head[u][s];
        ws.head[u][s] = i;
    }
    for (int dst = 0; dst < N; ++dst) {
        for (int T_idx = 0; T_idx < 21; ++T_idx) {
            int T_target = 60 + T_idx * 6;
            for (int u = 0; u < N; ++u) ws.reach[u].fill(false);
            ws.reach[dst][T_target] = true;
            for (int t = T_target; t >= 0; --t) {
                for (int u = 0; u < N; ++u) {
                    if (t + 1 <= T_target && ws.reach[u][t + 1]) ws.reach[u][t] = true;
                    for (int e = ws.head[u][t]; e != -1; e = ws.nxt[e]) {
                        if (flights[e].t <= T_target && ws.reach[flights[e].v][flights[e].t])
                            ws.reach[u][t] = true;
                    }
                }
            }
            for (int u = 0; u < N; ++u) {
                if (u == dst || !in.valid_dist[u][dst]) continue;
                for (int t = T_target; t >= 0; --t)
                    if (ws.reach[u][t]) {
                        s_ci[u][dst][T_idx] = t;
                        break;
                    }
            }
        }
    }
}

// 辺の限界利益を計算し、最長路（最適パス）を一本見つける
vector<Flight> find_best_path(const Input& in, const array<array<array<int, 21>, N>, N>& rival_s_sq,
                              const array<array<array<int, 21>, N>, N>& current_s_ci,
                              MarginalGainWorkspace& mg_ws) {
    for (int u = 0; u < N; ++u)
        for (int v = 0; v < N; ++v) mg_ws.edge_gain[u][v].fill(0);
    for (int u = 0; u < N; ++u) {
        for (int dst = 0; dst < N; ++dst) {
            if (!in.valid_dist[u][dst]) continue;
            for (int T_idx = 0; T_idx < 21; ++T_idx) {
                int r_s = rival_s_sq[u][dst][T_idx], c_s = current_s_ci[u][dst][T_idx];
                if (c_s > r_s) continue;
                int min_s = max(0, r_s + 1), T_target = 60 + T_idx * 6;
                for (int v = 0; v < N; ++v) {
                    if (u == v) continue;
                    int max_t = (v == dst) ? T_target : current_s_ci[v][dst][T_idx];
                    if (max_t < 0) continue;
                    int max_s = min(180 - in.dur[u][v], max_t - in.dur[u][v]);
                    if (min_s <= max_s) {
                        mg_ws.edge_gain[u][v][min_s] += in.weight[u][dst];
                        if (max_s + 1 <= 180) mg_ws.edge_gain[u][v][max_s + 1] -= in.weight[u][dst];
                    }
                }
            }
        }
    }
    for (int u = 0; u < N; ++u)
        for (int v = 0; v < N; ++v) {
            long long cur = 0;
            for (int s = 0; s <= 180; ++s) {
                cur += mg_ws.edge_gain[u][v][s];
                mg_ws.edge_gain[u][v][s] = cur;
            }
        }
    for (int u = 0; u < N; ++u) {
        mg_ws.dp[u].fill(0);
        mg_ws.nxt_v[u].fill(-1);
    }
    for (int t = 180; t >= 0; --t) {
        for (int u = 0; u < N; ++u) {
            if (t + 1 <= 180) {
                mg_ws.dp[u][t] = mg_ws.dp[u][t + 1];
                mg_ws.nxt_v[u][t] = -1;
            }
            for (int v = 0; v < N; ++v) {
                if (u == v) continue;
                int nt = t + in.dur[u][v];
                if (nt <= 180) {
                    long long g = mg_ws.edge_gain[u][v][t] + mg_ws.dp[v][nt];
                    if (g > mg_ws.dp[u][t]) {
                        mg_ws.dp[u][t] = g;
                        mg_ws.nxt_v[u][t] = v;
                    }
                }
            }
        }
    }
    int cur_u = 0;
    long long best_v = -1;
    for (int u = 0; u < N; ++u)
        if (mg_ws.dp[u][0] > best_v) {
            best_v = mg_ws.dp[u][0];
            cur_u = u;
        }
    vector<Flight> path;
    int cur_t = 0;
    while (cur_t <= 180) {
        int nv = mg_ws.nxt_v[cur_u][cur_t];
        if (nv != -1) {
            path.push_back({cur_u, cur_t, nv, cur_t + in.dur[cur_u][nv]});
            cur_t += in.dur[cur_u][nv];
            cur_u = nv;
        } else cur_t++;
    }
    return path;
}

long long get_score(const Input& in, const array<array<array<int, 21>, N>, N>& r_s,
                    const array<array<array<int, 21>, N>, N>& c_s) {
    long long v_ci = 0;
    for (int u = 0; u < N; ++u)
        for (int v = 0; v < N; ++v) {
            if (!in.valid_dist[u][v]) continue;
            for (int t = 0; t < 21; ++t)
                if (c_s[u][v][t] > r_s[u][v][t]) v_ci += in.weight[u][v];
        }
    return (long long)(1000000.0 * (double)v_ci / in.total_W);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Input in;
    auto c_ws = make_unique<ComputeSciWorkspace>();
    auto mg_ws = make_unique<MarginalGainWorkspace>();

    array<array<array<int, 21>, N>, N> rival_s_sq;
    {
        vector<Flight> rf;
        rf.reserve(M);
        for (int i = 0; i < M; ++i) rf.push_back({in.a[i], in.s[i], in.b[i], in.t[i]});
        compute_s_ci(in, rf, rival_s_sq, *c_ws);
    }

    // 初期解: 逐次最長路
    array<vector<Flight>, K> current_paths;
    vector<Flight> all_flights;
    for (int k = 0; k < K; ++k) {
        array<array<array<int, 21>, N>, N> s_ci;
        compute_s_ci(in, all_flights, s_ci, *c_ws);
        current_paths[k] = find_best_path(in, rival_s_sq, s_ci, *mg_ws);
        for (auto& f : current_paths[k]) all_flights.push_back(f);
    }

    array<array<array<int, 21>, N>, N> current_s_ci;
    compute_s_ci(in, all_flights, current_s_ci, *c_ws);
    long long current_score = get_score(in, rival_s_sq, current_s_ci);

    // 破壊再構築
    int itr = 0;
    int acc = 0;
    while (TIMER.elapsed() < 0.95f) {
        int D = 1;
        array<int, K> idx;
        iota(idx.begin(), idx.end(), 0);
        shuffle(idx.begin(), idx.end(), RNG);

        auto backup_paths = current_paths;
        vector<Flight> remaining;
        for (int i = D; i < K; ++i)
            for (auto& f : current_paths[idx[i]]) remaining.push_back(f);

        vector<Flight> temp_all = remaining;
        for (int i = 0; i < D; ++i) {
            array<array<array<int, 21>, N>, N> s_ci_tmp;
            compute_s_ci(in, temp_all, s_ci_tmp, *c_ws);
            current_paths[idx[i]] = find_best_path(in, rival_s_sq, s_ci_tmp, *mg_ws);
            for (auto& f : current_paths[idx[i]]) temp_all.push_back(f);
        }

        array<array<array<int, 21>, N>, N> next_s_ci;
        compute_s_ci(in, temp_all, next_s_ci, *c_ws);
        long long next_score = get_score(in, rival_s_sq, next_s_ci);

        if (next_score >= current_score) {
            current_score = next_score;
            ++acc;
        } else {
            current_paths = backup_paths;
        }
        ++itr;
    }
    cerr << "Iteration : " << itr << "\n";
    cerr << "Accepted : " << acc << "\n";

    for (int k = 0; k < K; ++k) {
        cout << current_paths[k].size() << "\n";
        for (auto& f : current_paths[k])
            cout << f.u + 1 << " " << to_time_str(f.s) << " " << f.v + 1 << " " << to_time_str(f.t)
                 << "\n";
    }
    return 0;
}