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

• 問題: No.5023 Airlines Optimization
• ユーザー: Shymohn _
• 提出日時: 2026-02-26 00:33:29
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 955 ms / 1,000 ms
• コード長: 18,044 bytes
• コンパイル時間: 5,747 ms
• コンパイル使用メモリ: 374,208 KB
• 実行使用メモリ: 7,844 KB
• スコア: 40,921,035
• 最終ジャッジ日時: 2026-02-26 00:35:17
• 合計ジャッジ時間: 107,509 ms
• ジャッジサーバーID （参考情報）: judge6 / judge1

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")

using ll = long long;
const int DAY_START = 6*60;   // 360
const int DAY_END   = 21*60;  // 1260
const int INF_NEG = -1000000000;

struct City { double x, y; ll w; };

struct Flight {
    int a; // 1-based city
    int dep; // minutes
    int b;
    int arr; // minutes
};

int flight_duration_min(const City &c1, const City &c2) {
    double dx = c1.x - c2.x;
    double dy = c1.y - c2.y;
    double d = sqrt(dx*dx + dy*dy);
    double raw = 60.0 * d / 800.0 + 40.0;
    int dur = (int)ceil(raw / 5.0) * 5;
    return dur;
}

string time_to_str(int m) {
    int h = m/60, mm = m%60;
    char buf[6];
    snprintf(buf, sizeof(buf), "%02d:%02d", h, mm);
    return string(buf);
}

// Remove consecutive duplicate cities from a sequence
vector<int> compress_sequence(const vector<int>& seq) {
    vector<int> out;
    out.reserve(seq.size());
    for (size_t i = 0; i < seq.size(); ++i) {
        if (i == 0 || seq[i] != seq[i-1]) out.push_back(seq[i]);
    }
    return out;
}

// Compute dp given flights sorted in descending departure order
vector<int> compute_dp_from_flights(int N, const vector<Flight>& flights_desc_dep, int v, int t) {
    vector<int> dp(N+1, INF_NEG);
    dp[v] = t;
    for (const auto &f : flights_desc_dep) {
        if (dp[f.b] >= f.arr) {
            if (f.dep > dp[f.a]) dp[f.a] = f.dep;
        }
    }
    return dp;
}

// Precompute dp for square flights for all (v,ti)
void precompute_square_dp(int N, const vector<Flight>& square_flights, const vector<int>& target_times,
                          vector<vector<int>>& dp_square_by_target) {
    vector<Flight> desc = square_flights;
    sort(desc.begin(), desc.end(), [](const Flight& A, const Flight& B){
        return A.dep > B.dep;
    });
    dp_square_by_target.clear();
    dp_square_by_target.reserve(N * (int)target_times.size());
    for (int v = 1; v <= N; ++v) {
        for (size_t ti = 0; ti < target_times.size(); ++ti) {
            int t = target_times[ti];
            vector<int> dp = compute_dp_from_flights(N, desc, v, t);
            dp_square_by_target.push_back(std::move(dp));
        }
    }
}

// Build flights (circle) from sequences: each sequence is vector<int> cities visited in order.
// Start time = DAY_START at seq[0], flights between consecutive cities. Stop if arrival > DAY_END.
// Skip legs where a == b (shouldn't occur if sequences are compressed).
vector<Flight> build_circle_flights_from_seqs(const vector<vector<int>>& seqs, const vector<City>& cities) {
    vector<Flight> res;
    for (const auto &raw_seq : seqs) {
        if (raw_seq.size() < 2) continue;
        vector<int> seq = compress_sequence(raw_seq);
        int cur_time = DAY_START;
        for (size_t i = 0; i + 1 < seq.size(); ++i) {
            int a = seq[i];
            int b = seq[i+1];
            if (a == b) continue;
            if (a < 1 || a > (int)cities.size() || b < 1 || b > (int)cities.size()) continue;
            int dur = flight_duration_min(cities[a-1], cities[b-1]);
            int depart = cur_time;
            int arrive = depart + dur;
            if (arrive > DAY_END) break;
            res.push_back({a, depart, b, arrive});
            cur_time = arrive;
            if (cur_time >= DAY_END) break;
        }
    }
    return res;
}

// Compute score S for given circle_flights and precomputed square dp.
// Uses dp propagation per (v,ti).
long double compute_score_S(int N, const vector<City>& cities, const vector<Flight>& square_flights,
                            const vector<vector<int>>& dp_square_by_target, const vector<int>& target_times,
                            const vector<Flight>& circle_flights) {
    vector<Flight> desc = circle_flights;
    sort(desc.begin(), desc.end(), [](const Flight& A, const Flight& B){
        return A.dep > B.dep;
    });

    long double v_circle = 0.0L;
    long double v_square = 0.0L;

    int T = (int)target_times.size();
    for (int v = 1; v <= N; ++v) {
        for (int ti = 0; ti < T; ++ti) {
            int idx = (v-1)*T + ti;
            // dp for circle flights
            vector<int> dp_circle = compute_dp_from_flights(N, desc, v, target_times[ti]);
            const vector<int>& dp_square = dp_square_by_target[idx];
            for (int i = 1; i <= N; ++i) {
                if (i == v) continue;
                long double prod = (long double)cities[i-1].w * (long double)cities[v-1].w;
                int dc = dp_circle[i];
                int ds = dp_square[i];
                if (dc <= INF_NEG/2 && ds <= INF_NEG/2) continue;
                if (dc >= ds) v_circle += prod;
                else v_square += prod;
            }
        }
    }
    long double S = 0.0L;
    long double denom = v_circle + v_square;
    if (denom > 0) S = v_circle / denom;
    return S;
}

// Extend a single sequence by adding cities (population-weighted) while time remains.
// seq is assumed to be compressed already (but we compress inside to be safe).
vector<int> extend_sequence_by_time(const vector<int>& raw_seq, const vector<City>& cities,
                                    const vector<double>& pop_weights, std::mt19937_64 &rng) {
    vector<int> seq = compress_sequence(raw_seq);
    if (seq.empty()) return seq;
    // compute cur_time by simulating existing legs
    int cur_time = DAY_START;
    for (size_t i = 0; i + 1 < seq.size(); ++i) {
        int a = seq[i];
        int b = seq[i+1];
        if (a < 1 || a > (int)cities.size() || b < 1 || b > (int)cities.size()) { cur_time = DAY_END + 1; break; }
        if (a == b) continue;
        int dur = flight_duration_min(cities[a-1], cities[b-1]);
        int arrive = cur_time + dur;
        if (arrive > DAY_END) { // truncate at this point
            seq.resize(i+1);
            cur_time = DAY_END + 1;
            break;
        }
        cur_time = arrive;
        if (cur_time >= DAY_END) break;
    }
    if (cur_time > DAY_END) {
        // truncated to beyond day end => just compress and return
        return compress_sequence(seq);
    }
    int cur_city = seq.back();
    // keep adding while we can
    while (cur_time < DAY_END) {
        // build weights excluding current city
        vector<double> weights = pop_weights;
        if (cur_city >= 1 && cur_city <= (int)weights.size()) weights[cur_city-1] = 0.0;
        double total_w = 0.0;
        for (double w : weights) total_w += w;
        if (total_w <= 0.0) break;
        discrete_distribution<int> d(weights.begin(), weights.end());
        int next_city = d(rng) + 1;
        if (next_city == cur_city) {
            // extremely unlikely due to weight zero, but guard
            break;
        }
        int dur = flight_duration_min(cities[cur_city-1], cities[next_city-1]);
        int arrive = cur_time + dur;
        if (arrive > DAY_END) break;
        seq.push_back(next_city);
        cur_time = arrive;
        cur_city = next_city;
    }
    return compress_sequence(seq);
}

// Clamp sequences by time (truncate legs that would exceed DAY_END), compress duplicates,
// and then extend sequences to fill remaining time by adding cities weighted by population.
// Requires pop_weights and rng for extension behavior.
vector<vector<int>> clamp_and_extend_sequences_by_time(const vector<vector<int>>& seqs, const vector<City>& cities,
                                                       const vector<double>& pop_weights, std::mt19937_64 &rng) {
    vector<vector<int>> out;
    out.reserve(seqs.size());
    for (const auto &raw : seqs) {
        // first compress & truncate legs that exceed day end
        vector<int> seq = compress_sequence(raw);
        vector<int> cur;
        if (seq.empty()) { out.push_back(cur); continue; }
        cur.push_back(seq[0]);
        int cur_time = DAY_START;
        for (size_t i = 0; i + 1 < seq.size(); ++i) {
            int a = seq[i];
            int b = seq[i+1];
            if (a == b) continue;
            if (a <1 || a > (int)cities.size() || b <1 || b >(int)cities.size()) break;
            int dur = flight_duration_min(cities[a-1], cities[b-1]);
            int arrive = cur_time + dur;
            if (arrive > DAY_END) break;
            cur.push_back(b);
            cur_time = arrive;
            if (cur_time >= DAY_END) break;
        }
        // now extend using randomness and weights
        vector<int> extended = extend_sequence_by_time(cur, cities, pop_weights, rng);
        out.push_back(compress_sequence(extended));
    }
    return out;
}

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

    auto t_start = chrono::high_resolution_clock::now();

    int N; int R;
    if (!(cin >> N >> R)) return 0;
    vector<City> cities(N);
    for (int i = 0; i < N; ++i) {
        double x,y; ll w;
        cin >> x >> y >> w;
        cities[i] = {x,y,w};
    }
    int M; cin >> M;
    vector<Flight> square_flights;
    for (int i = 0; i < M; ++i) {
        int a, b; string s_str, t_str;
        cin >> a >> s_str >> b >> t_str;
        int s = stoi(s_str.substr(0,2))*60 + stoi(s_str.substr(3,2));
        int tt = stoi(t_str.substr(0,2))*60 + stoi(t_str.substr(3,2));
        square_flights.push_back({a, s, b, tt});
    }
    int K; cin >> K;

    // Target times: 11:00,11:30,...,21:00 (21 times)
    vector<int> target_times;
    for (int h = 11; h <= 21; ++h) {
        target_times.push_back(h*60 + 0);
        if (h != 21) target_times.push_back(h*60 + 30);
    }
    int T = (int)target_times.size();

    vector<vector<int>> dp_square_by_target;
    precompute_square_dp(N, square_flights, target_times, dp_square_by_target);

    mt19937_64 rng(42);

    vector<double> pop_weights(N);
    for (int i = 0; i < N; ++i) pop_weights[i] = (double)cities[i].w;

    // initial sequences
    vector<vector<int>> seqs(K);
    discrete_distribution<int> start_dist(pop_weights.begin(), pop_weights.end());
    uniform_int_distribution<int> len_dist(1, max(1, N/4));
    for (int p = 0; p < K; ++p) {
        int len = len_dist(rng);
        vector<int> seq;
        seq.reserve(len);
        int first = start_dist(rng) + 1;
        seq.push_back(first);
        for (int j = 1; j < len; ++j) {
            discrete_distribution<int> d(pop_weights.begin(), pop_weights.end());
            int c = d(rng) + 1;
            seq.push_back(c);
        }
        seqs[p] = compress_sequence(seq);
    }

    // clamp and extend initial sequences
    seqs = clamp_and_extend_sequences_by_time(seqs, cities, pop_weights, rng);

    // build initial full circle flights & score
    vector<Flight> circle_flights = build_circle_flights_from_seqs(seqs, cities);
    long double cur_score = compute_score_S(N, cities, square_flights, dp_square_by_target, target_times, circle_flights);
    vector<vector<int>> best_seqs = seqs;
    long double best_score = cur_score;

    // parameters
    const double TIME_LIMIT_SEC = 0.95;
    const double EPS_TEMP = 1e-12;
    double global_T0 = 1.0;
    double global_Tend = 1e-4;

    // We'll iterate planes sequentially
    vector<int> iterations_per_plane(K, 0);
    vector<int> accepts_per_plane(K, 0);

    for (int p = 0; p < K; ++p) {
        // compute remaining time budget for this plane
        auto now = chrono::high_resolution_clock::now();
        double elapsed_total = chrono::duration_cast<chrono::duration<double>>(now - t_start).count();
        double remaining = TIME_LIMIT_SEC - elapsed_total;
        if (remaining <= 0.001) break; // no time left

        int remaining_planes = K - p;
        // allocate proportional budget
        double budget = remaining / remaining_planes;
        // minimum budget guard
        if (budget < 0.001) budget = remaining; // give whatever remains

        // local SA for plane p
        auto local_start = chrono::high_resolution_clock::now();
        int local_iter = 0;
        int local_accepts = 0;
        // temperature schedule per-plane (simple linear cooling across budget) - use elapsed fraction of budget
        while (true) {
            auto now_local = chrono::high_resolution_clock::now();
            double elapsed_local = chrono::duration_cast<chrono::duration<double>>(now_local - local_start).count();
            if (elapsed_local >= budget) break;
            // global time check
            auto now_total = chrono::high_resolution_clock::now();
            double elapsed_total2 = chrono::duration_cast<chrono::duration<double>>(now_total - t_start).count();
            if (elapsed_total2 >= TIME_LIMIT_SEC) break;

            // compute temperature as global-like but mapped to local progression
            double frac = elapsed_local / max(budget, 1e-9);
            double temp = global_T0 * pow(global_Tend / global_T0, frac);

            // propose neighbor only for plane p
            vector<int> new_seq = seqs[p];
            int op = (int)(rng() % 3);
            if (op == 0) { // insert
                int pos = new_seq.empty() ? 0 : (int)(rng() % ((uint64_t)new_seq.size() + 1));
                discrete_distribution<int> d(pop_weights.begin(), pop_weights.end());
                int c = d(rng) + 1;
                new_seq.insert(new_seq.begin() + pos, c);
            } else if (op == 1) { // delete
                if (!new_seq.empty()) {
                    int pos = (int)(rng() % (uint64_t)new_seq.size());
                    new_seq.erase(new_seq.begin() + pos);
                } else {
                    discrete_distribution<int> d(pop_weights.begin(), pop_weights.end());
                    int c = d(rng) + 1;
                    new_seq.push_back(c);
                }
            } else { // replace
                if (!new_seq.empty()) {
                    int pos = (int)(rng() % (uint64_t)new_seq.size());
                    discrete_distribution<int> d(pop_weights.begin(), pop_weights.end());
                    int c = d(rng) + 1;
                    new_seq[pos] = c;
                } else {
                    discrete_distribution<int> d(pop_weights.begin(), pop_weights.end());
                    int c = d(rng) + 1;
                    new_seq.push_back(c);
                }
            }

            new_seq = compress_sequence(new_seq);

            // form candidate sequences with only plane p changed
            vector<vector<int>> cand_seqs = seqs;
            cand_seqs[p] = new_seq;
            // clamp & extend candidate sequences (we allow extend here)
            cand_seqs = clamp_and_extend_sequences_by_time(cand_seqs, cities, pop_weights, rng);
            // build flights and evaluate
            vector<Flight> cand_circle_flights = build_circle_flights_from_seqs(cand_seqs, cities);
            long double cand_score = compute_score_S(N, cities, square_flights, dp_square_by_target, target_times, cand_circle_flights);

            long double delta = cand_score - cur_score;
            bool accept = false;
            if (delta >= 0) accept = true;
            else {
                double prob = exp((double)(delta) / max(EPS_TEMP, temp));
                double r = (double)(rng() % 1000000) / 1000000.0;
                if (r < prob) accept = true;
            }
            if (accept) {
                seqs = std::move(cand_seqs);
                circle_flights = std::move(cand_circle_flights);
                cur_score = cand_score;
                local_accepts++;
                if (cur_score > best_score) {
                    best_score = cur_score;
                    best_seqs = seqs;
                }
            }
            local_iter++;
        } // end local while

        iterations_per_plane[p] = local_iter;
        accepts_per_plane[p] = local_accepts;

        // plane p is now fixed (we keep seqs[p] as decided). Continue to next plane.
        // check global time; break if exhausted
        auto now_after = chrono::high_resolution_clock::now();
        double elapsed_total_after = chrono::duration_cast<chrono::duration<double>>(now_after - t_start).count();
        if (elapsed_total_after >= TIME_LIMIT_SEC) break;
    } // end loop over planes

    // Final: ensure best_seqs is used and extend/clamp for final output
    vector<vector<int>> final_seqs = clamp_and_extend_sequences_by_time(best_seqs, cities, pop_weights, rng);

    // Output per-plane flights using final_seqs
    for (int p = 0; p < K; ++p) {
        const auto &seq = final_seqs[p];
        vector<pair<pair<int,int>, pair<int,int>>> flights_print;
        if (!seq.empty()) {
            int cur_time = DAY_START;
            for (size_t i = 0; i + 1 < seq.size(); ++i) {
                int a = seq[i];
                int b = seq[i+1];
                if (a == b) continue; // safety
                int dur = flight_duration_min(cities[a-1], cities[b-1]);
                int depart = cur_time;
                int arrive = depart + dur;
                if (arrive > DAY_END) break;
                flights_print.push_back({{a, depart}, {b, arrive}});
                cur_time = arrive;
                if (cur_time >= DAY_END) break;
            }
        }
        cout << flights_print.size() << "\n";
        for (auto &fp : flights_print) {
            int a = fp.first.first;
            int dep = fp.first.second;
            int b = fp.second.first;
            int arr = fp.second.second;
            cout << a << " " << time_to_str(dep) << " " << b << " " << time_to_str(arr) << "\n";
        }
    }
    cout.flush();

    // print stats to stderr
    auto t_end = chrono::high_resolution_clock::now();
    auto elapsed_ms = chrono::duration_cast<chrono::milliseconds>(t_end - t_start).count();
    cerr << "elapsed_ms: " << elapsed_ms << "\n";
    for (int p = 0; p < K; ++p) {
        cerr << "plane " << (p+1) << " iters=" << iterations_per_plane[p] << " accepts=" << accepts_per_plane[p] << "\n";
    }
    cerr << "best_S: " << std::fixed << std::setprecision(9) << (double)best_score << "\n";
    cerr.flush();

    return 0;
}