#1150775 (C++14) No.5023 Airlines Optimization

• 問題: No.5023 Airlines Optimization
• ユーザー: ebicochineal
• 提出日時: 2026-02-28 19:00:20
• 言語: C++14 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 971 ms / 1,000 ms
• コード長: 7,477 bytes
• コンパイル時間: 1,914 ms
• コンパイル使用メモリ: 143,328 KB
• 実行使用メモリ: 7,848 KB
• スコア: 34,819,717
• 最終ジャッジ日時: 2026-02-28 19:02:05
• 合計ジャッジ時間: 104,447 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

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

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <random>
#include <chrono>
#include <cstdio>

using namespace std;

const int TIME_MIN = 6 * 60;
const int TIME_MAX = 21 * 60;
const int TARGET_START = 11 * 60;
const int TARGET_END = 21 * 60;
const int TARGET_STEP = 30;

struct City { int id; long long x, y, w; };
struct Flight { int from, to, s, t; };

inline int calc_dur(const City& a, const City& b) {
    double d = sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
    return (int)ceil((60.0 * d / 800.0 + 40.0) / 5.0) * 5;
}

class Solver {
    int N, M, K;
    double R;
    vector<City> cities;

    vector<int> get_latest_departure_all(const vector<Flight>& all_flights, int dst, int target) {
        vector<int> best(N, -1e9);
        best[dst] = target;
        for (int i = (int)all_flights.size() - 1; i >= 0; --i) {
            const auto& f = all_flights[i];
            if (f.t <= best[f.to] && f.s > best[f.from]) {
                best[f.from] = f.s;
            }
        }
        return best;
    }

    long long evaluate_config(const vector<Flight>& flights) {
        if (flights.empty()) return -1;
        vector<Flight> sorted_f = flights;
        sort(sorted_f.begin(), sorted_f.end(), [](const Flight& a, const Flight& b){
            return a.s < b.s;
        });

        long long total_v = 0;
        for (int dst = 0; dst < N; ++dst) {
            for (int target = TARGET_START; target <= TARGET_END; target += TARGET_STEP) {
                vector<int> ci_dep = get_latest_departure_all(sorted_f, dst, target);
                for (int src = 0; src < N; ++src) {
                    if (src == dst) continue;
                    double dx = cities[src].x - cities[dst].x, dy = cities[src].y - cities[dst].y;
                    if (sqrt(dx*dx + dy*dy) < 0.25 * R) continue;
                    if (ci_dep[src] > TIME_MIN) total_v += cities[src].w * cities[dst].w;
                }
            }
        }
        return total_v;
    }

public:
    void solve() {
        auto start_time = chrono::system_clock::now();
        if (!(cin >> N >> R)) return;
        cities.resize(N);
        for (int i = 0; i < N; ++i) { cities[i].id = i; cin >> cities[i].x >> cities[i].y >> cities[i].w; }
        cin >> M;
        for (int i = 0; i < M; ++i) {
            int a, b, sh, sm, th, tm; char c;
            cin >> a >> sh >> c >> sm >> b >> th >> c >> tm;
        }
        cin >> K;

        vector<pair<long long, int>> pop_rank;
        for(int i=0; i<N; ++i) pop_rank.push_back({cities[i].w, i});
        sort(pop_rank.rbegin(), pop_rank.rend());

        long long best_total_score = -1;
        vector<vector<Flight>> best_schedule(K);

        auto check_and_update = [&](const vector<vector<Flight>>& current_sched) {
            vector<Flight> all_f;
            for(auto& vk : current_sched) for(auto& f : vk) all_f.push_back(f);
            long long sc = evaluate_config(all_f);
            if (sc > best_total_score) {
                best_total_score = sc;
                best_schedule = current_sched;
            }
        };

        for (int i = 0; i < min(N, 4); ++i) {
            int h = pop_rank[i].second;
            vector<int> spokes;
            for(auto& p : pop_rank) {
                if(p.second == h) continue;
                double dx = cities[h].x - cities[p.second].x, dy = cities[h].y - cities[p.second].y;
                if(sqrt(dx*dx + dy*dy) >= 0.25 * R) spokes.push_back(p.second);
            }
            if (spokes.empty()) continue;
            vector<vector<Flight>> current(K);
            for (int k = 0; k < K; ++k) {
                int v = spokes[k % spokes.size()];
                int cur_t = TIME_MIN + (k % 6) * 5, cur_loc = h, d = calc_dur(cities[h], cities[v]);
                while (cur_t + d <= TIME_MAX) {
                    int dest = (cur_loc == h) ? v : h;
                    current[k].push_back({cur_loc, dest, cur_t, cur_t + d});
                    cur_t += d; cur_loc = dest;
                }
            }
            check_and_update(current);
        }

        for (int i = 0; i < min(N, 3); ++i) {
            for (int j = i + 1; j < min(N, 3); ++j) {
                int h1 = pop_rank[i].second, h2 = pop_rank[j].second;
                double dh = sqrt(pow(cities[h1].x-cities[h2].x, 2) + pow(cities[h1].y-cities[h2].y, 2));
                if(dh < 0.25 * R) continue;
                vector<vector<Flight>> current(K);
                for(int k=0; k<K; ++k){
                    int u, v;
                    if(k < 2) { u = h1; v = h2; }
                    else { u = (k % 2 == 0) ? h1 : h2; v = pop_rank[(k/2) % N].second; if(v==h1 || v==h2) v = pop_rank[(k/2+1)%N].second; }
                    int cur_t = TIME_MIN + (k%4)*5, cur_loc = u, d = calc_dur(cities[u], cities[v]);
                    while(cur_t + d <= TIME_MAX){
                        int dest = (cur_loc == u) ? v : u;
                        current[k].push_back({cur_loc, dest, cur_t, cur_t + d});
                        cur_t += d; cur_loc = dest;
                    }
                }
                check_and_update(current);
            }
        }

        for (int i = 0; i < 1; ++i) { 
            int h[3] = {pop_rank[0].second, pop_rank[1].second, pop_rank[2].second};
            vector<vector<Flight>> current(K);
            for(int k=0; k<K; ++k){
                int u, v;
                if(k < 3) { u = h[k]; v = h[(k+1)%3]; }
                else { u = h[k%3]; v = pop_rank[(k/3+3)%N].second; }
                int cur_t = TIME_MIN + (k%3)*5, cur_loc = u, d = calc_dur(cities[u], cities[v]);
                while(cur_t + d <= TIME_MAX){
                    int dest = (cur_loc == u) ? v : u;
                    current[k].push_back({cur_loc, dest, cur_t, cur_t + d});
                    cur_t += d; cur_loc = dest;
                }
            }
            check_and_update(current);
        }

        mt19937 engine(42);
        while (chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start_time).count() < 950) {
            int k = engine() % K;
            if (best_schedule[k].empty()) continue;
            int f_idx = engine() % best_schedule[k].size();
            int diff = (engine() % 2 == 0 ? 5 : -5);
            int ps = best_schedule[k][f_idx].s, pt = best_schedule[k][f_idx].t;
            int ns = ps + diff, nt = pt + diff;
            if (ns >= TIME_MIN && nt <= TIME_MAX) {
                if ((f_idx == 0 || best_schedule[k][f_idx-1].t <= ns) && (f_idx == (int)best_schedule[k].size()-1 || nt <= best_schedule[k][f_idx+1].s)) {
                    long long old_sc = best_total_score;
                    best_schedule[k][f_idx].s = ns; best_schedule[k][f_idx].t = nt;
                    vector<Flight> all_f;
                    for(auto& vk : best_schedule) for(auto& f : vk) all_f.push_back(f);
                    long long new_sc = evaluate_config(all_f);
                    if (new_sc >= old_sc) best_total_score = new_sc;
                    else { best_schedule[k][f_idx].s = ps; best_schedule[k][f_idx].t = pt; }
                }
            }
        }

        for (int k = 0; k < K; ++k) {
            printf("%d\n", (int)best_schedule[k].size());
            for (auto& f : best_schedule[k]) printf("%d %02d:%02d %d %02d:%02d\n", f.from + 1, f.s/60, f.s%60, f.to + 1, f.t/60, f.t%60);
        }
    }
};

int main() { Solver().solve(); return 0; }