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

• 問題: No.5023 Airlines Optimization
• ユーザー: hotpepsi
• 提出日時: 2026-02-28 16:18:02
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 961 ms / 1,000 ms
• コード長: 11,966 bytes
• コンパイル時間: 7,119 ms
• コンパイル使用メモリ: 292,540 KB
• 実行使用メモリ: 7,844 KB
• スコア: 22,023,828
• 最終ジャッジ日時: 2026-02-28 16:19:51
• 合計ジャッジ時間: 107,113 ms
• ジャッジサーバーID （参考情報）: judge2 / judge7

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

ソースコード

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <random>
#include <chrono>
#include <iomanip>
#include <queue>

// --- 定数 ---
const int N_const = 47;
const int R_const = 1000;
const int M_const = 400;
const int K_const = 25;
const int MIN_TIME = 360; // 06:00
const int MAX_TIME = 1260; // 21:00

// --- 構造体 ---
struct City {
    int id;
    int x, y;
    long long w;
};

struct Flight {
    int from, to;
    int start_time, end_time;
};

// --- グローバル変数 ---
std::vector<City> cities;
std::vector<Flight> square_flights;
std::vector<std::vector<double>> dists;
std::vector<std::vector<int>> flight_times;
std::vector<std::pair<int, int>> target_pairs;
std::vector<std::vector<std::vector<int>>> s_sq_table;
std::vector<int> hubs;
std::vector<std::vector<int>> gap_adj;

// 乱数生成器
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

// 時間管理
auto start_time = std::chrono::steady_clock::now();

// --- 時間変換ユーティリティ ---
int time_to_int(const std::string& t) {
    return std::stoi(t.substr(0, 2)) * 60 + std::stoi(t.substr(3, 2));
}

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

// --- 計算ユーティリティ ---
void precompute_distances_and_times() {
    dists.assign(N_const, std::vector<double>(N_const));
    flight_times.assign(N_const, std::vector<int>(N_const));
    for (int i = 0; i < N_const; ++i) {
        for (int j = 0; j < N_const; ++j) {
            double dx = cities[i].x - cities[j].x;
            double dy = cities[i].y - cities[j].y;
            dists[i][j] = std::sqrt(dx * dx + dy * dy);
            if (i == j) {
                flight_times[i][j] = 0;
            } else {
                flight_times[i][j] = std::ceil((60.0 * dists[i][j] / 800.0 + 40.0) / 5.0) * 5;
            }
        }
    }
}

// --- スコア計算関連 ---
std::vector<int> calculate_latest_departures(int dest_city, int target_arrival, const std::vector<Flight>& flights) {
    // This function is a bottleneck. Using adjacency list for incoming flights
    // and a priority queue for Dijkstra's will speed it up.
    thread_local static std::vector<std::vector<const Flight*>> incoming_flights(N_const);
    for(int i = 0; i < N_const; ++i) incoming_flights[i].clear();
    for(const auto& f : flights) {
        incoming_flights[f.to].push_back(&f);
    }

    std::vector<int> reachable_at(N_const, -1);
    std::priority_queue<std::pair<int, int>> pq;

    reachable_at[dest_city] = target_arrival;
    pq.push({target_arrival, dest_city});

    while(!pq.empty()){
        auto [time, u] = pq.top();
        pq.pop();

        if(time < reachable_at[u]) {
            continue;
        }

        for(const Flight* f_ptr : incoming_flights[u]){
            const Flight& f = *f_ptr; 
            if (f.end_time <= time) {
                if (reachable_at[f.from] < f.start_time) {
                    reachable_at[f.from] = f.start_time;
                    pq.push({f.start_time, f.from});
                }
            }
        }
    }
    
    std::vector<int> latest_dep = reachable_at;
    for (int i = 0; i < N_const; ++i) {
        for (int k = 0; k < N_const; ++k) {
            if (reachable_at[k] != -1) {
                int dep_time = reachable_at[k] - flight_times[i][k];
                if (dep_time >= MIN_TIME) {
                    if (latest_dep[i] < dep_time) {
                        latest_dep[i] = dep_time;
                    }
                }
            }
        }
    }
    return latest_dep;
}


void precompute_sq_table() {
    s_sq_table.assign(N_const, std::vector<std::vector<int>>(21, std::vector<int>(N_const)));
    for (int j = 0; j < N_const; ++j) {
        for (int t_idx = 0; t_idx < 21; ++t_idx) {
            int target_arrival = 11 * 60 + t_idx * 30;
            s_sq_table[j][t_idx] = calculate_latest_departures(j, target_arrival, square_flights);
        }
    }
}

double calculate_score(const std::vector<std::vector<Flight>>& solution) {
    std::vector<Flight> all_circle_flights;
    for (const auto& plane_schedule : solution) {
        all_circle_flights.insert(all_circle_flights.end(), plane_schedule.begin(), plane_schedule.end());
    }

    long double v_ci = 0;
    long double v_sq = 0;

    for (const auto& p : target_pairs) {
        int i = p.first;
        int j = p.second;
        long double potential = (long double)cities[i].w * cities[j].w;

        std::vector<int> s_ci_for_dest;
        for (int t_idx = 0; t_idx < 21; ++t_idx) {
            int target_arrival = 11 * 60 + t_idx * 30;
            if (t_idx == 0 || j != p.second) { // Re-calculate only if dest changes
                 s_ci_for_dest = calculate_latest_departures(j, target_arrival, all_circle_flights);
            }
            int s_ci = s_ci_for_dest[i];
            int s_sq = s_sq_table[j][t_idx][i];
            
            if (s_ci > s_sq) {
                v_ci += potential;
            } else {
                v_sq += potential;
            }
        }
    }

    if (v_ci + v_sq == 0) return 0.0;
    return (double)(v_ci / (v_ci + v_sq));
}


// --- 探索アルゴリズム ---
std::vector<std::vector<Flight>> generate_initial_solution() {
    std::vector<std::vector<Flight>> solution(K_const);
    for (int i = 0; i < K_const; ++i) {
        int current_city = i % N_const;
        int current_time = MIN_TIME;
        while (true) {
            int next_city;
            double r = std::uniform_real_distribution<double>(0.0, 1.0)(rng);

            // Heuristic: Prefer flying to hubs
            if (r < 0.6 && !hubs.empty()) {
                next_city = hubs[rng() % hubs.size()];
            } else {
                next_city = rng() % N_const;
            }

            if (next_city == current_city) continue;

            int start_t = current_time;
            int travel_t = flight_times[current_city][next_city];
            int end_t = start_t + travel_t;

            if (end_t > MAX_TIME) break;
            
            solution[i].push_back({current_city, next_city, start_t, end_t});
            current_city = next_city;
            current_time = end_t;
        }
    }
    return solution;
}

std::vector<std::vector<Flight>> get_neighbor(const std::vector<std::vector<Flight>>& current_solution) {
    auto new_solution = current_solution;
    int plane_idx = std::uniform_int_distribution<int>(0, K_const - 1)(rng);
    
    if (new_solution[plane_idx].empty()) {
        return new_solution; // Cannot modify empty schedule
    }

    int flight_idx = std::uniform_int_distribution<int>(0, new_solution[plane_idx].size() - 1)(rng);
    
    int original_from = new_solution[plane_idx][flight_idx].from;
    int new_to;

    double r = std::uniform_real_distribution<double>(0.0, 1.0)(rng);

    if (r < 0.5 && !hubs.empty()) {
        // Strategy 1: Fly to a hub
        new_to = hubs[rng() % hubs.size()];
    } else if (r < 0.7 && !gap_adj[original_from].empty()) {
        // Strategy 2: Serve a gap route from the current location
        new_to = gap_adj[original_from][rng() % gap_adj[original_from].size()];
    } else {
        // Fallback: random city to maintain diversity
        new_to = rng() % N_const;
    }

    if (new_to == original_from) { // Ensure not flying to the same city
        new_to = (original_from + 1) % N_const;
    }

    // Apply change and propagate
    int current_city = original_from;
    int current_time = (flight_idx == 0) ? MIN_TIME : new_solution[plane_idx][flight_idx - 1].end_time;
    
    for (int i = flight_idx; i < new_solution[plane_idx].size(); ++i) {
        int from_city = current_city;
        // The first modified flight goes to our heuristically chosen `new_to`
        int to_city = (i == flight_idx) ? new_to : new_solution[plane_idx][i].to;
        
        int start_t = current_time;
        int travel_t = flight_times[from_city][to_city];
        int end_t = start_t + travel_t;

        if (end_t > MAX_TIME) { // Invalid move
            return current_solution; // Return original, move is rejected
        }

        new_solution[plane_idx][i] = {from_city, to_city, start_t, end_t};
        current_city = to_city;
        current_time = end_t;
    }

    return new_solution;
}


void solve() {
    precompute_distances_and_times();

    for (int i = 0; i < N_const; ++i) {
        for (int j = 0; j < N_const; ++j) {
            if (i != j && dists[i][j] >= 0.25 * R_const) {
                target_pairs.push_back({i, j});
            }
        }
    }

    precompute_sq_table();

    // --- Heuristic Strategy Setup ---
    // 1. Hub Airport Identification
    const int NUM_HUBS = 10;
    std::vector<int> city_indices(N_const);
    std::iota(city_indices.begin(), city_indices.end(), 0);
    std::sort(city_indices.begin(), city_indices.end(), [&](int a, int b){
        return cities[a].w > cities[b].w;
    });
    hubs.assign(city_indices.begin(), city_indices.begin() + NUM_HUBS);

    // 2. Underserved "Gap" Route Identification
    gap_adj.assign(N_const, std::vector<int>());
    const int GAP_THRESHOLD = 5;
    for (int i = 0; i < N_const; ++i) {
        for (int j = 0; j < N_const; ++j) {
            if (i == j) continue;
            int served_count = 0;
            for (int t_idx = 0; t_idx < 21; ++t_idx) {
                if (s_sq_table[j][t_idx][i] != -1) {
                    served_count++;
                }
            }
            if (served_count < GAP_THRESHOLD) {
                gap_adj[i].push_back(j);
            }
        }
    }
    // --- End of Heuristic Strategy Setup ---


    auto current_solution = generate_initial_solution();
    double current_score = calculate_score(current_solution);
    
    auto best_solution = current_solution;
    double best_score = current_score;

    int iter = 0;
    const double T_start = 1e-4, T_end = 1e-7;
    const double time_limit_sec = 0.95;

    while (true) {
        auto now = std::chrono::steady_clock::now();
        double elapsed_sec = std::chrono::duration<double>(now - start_time).count();
        if (elapsed_sec > time_limit_sec) break;
        
        iter++;
        
        auto new_solution = get_neighbor(current_solution);
        double new_score = calculate_score(new_solution);

        double temp = T_start + (T_end - T_start) * elapsed_sec / time_limit_sec;
        
        if (new_score > current_score || std::uniform_real_distribution<double>(0.0, 1.0)(rng) < std::exp((new_score - current_score) / temp)) {
            current_solution = new_solution;
            current_score = new_score;
        }

        if (current_score > best_score) {
            best_solution = current_solution;
            best_score = current_score;
        }
    }
    
    // Output the best solution
    for (int i = 0; i < K_const; ++i) {
        std::cout << best_solution[i].size() << std::endl;
        for (const auto& f : best_solution[i]) {
            std::cout << f.from + 1 << " " << int_to_time(f.start_time) << " " << f.to + 1 << " " << int_to_time(f.end_time) << std::endl;
        }
    }
}


int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N_in, R_in;
    std::cin >> N_in >> R_in;
    cities.resize(N_const);
    for (int i = 0; i < N_const; ++i) {
        cities[i].id = i;
        std::cin >> cities[i].x >> cities[i].y >> cities[i].w;
    }

    int M_in;
    std::cin >> M_in;
    square_flights.resize(M_const);
    for (int i = 0; i < M_const; ++i) {
        int a, b;
        std::string s, t;
        std::cin >> a >> s >> b >> t;
        square_flights[i] = {a - 1, b - 1, time_to_int(s), time_to_int(t)};
    }
    
    int K_in;
    std::cin >> K_in;

    solve();

    return 0;
}