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

• 問題: No.5023 Airlines Optimization
• ユーザー: hotpepsi
• 提出日時: 2026-02-28 16:35:11
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 10,203 bytes
• コンパイル時間: 3,940 ms
• コンパイル使用メモリ: 269,580 KB
• 実行使用メモリ: 7,848 KB
• スコア: 0
• 最終ジャッジ日時: 2026-02-28 16:38:28
• 合計ジャッジ時間: 195,867 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

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

ソースコード

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

// --- 定数 ---
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<int> target_origins[N_const];
long long weights[N_const][N_const];
std::vector<std::vector<std::vector<int>>> s_sq_table;

// 乱数生成器
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;
            }
        }
    }
}

// --- スコア計算関連 ---
int L_buf[N_const][21];
void calculate_all_latest_departures(int dest_city, const std::vector<Flight>& sorted_flights) {
    for (int i = 0; i < N_const; ++i) {
        for (int t = 0; t < 21; ++t) L_buf[i][t] = -1e9;
    }
    for (int t = 0; t < 21; ++t) L_buf[dest_city][t] = 11 * 60 + t * 30;

    for (const auto& f : sorted_flights) {
        if (L_buf[f.to][20] <= -1e9) continue;
        for (int t = 20; t >= 0; --t) {
            if (f.end_time <= L_buf[f.to][t]) {
                if (f.start_time > L_buf[f.from][t]) L_buf[f.from][t] = f.start_time;
            } else {
                break;
            }
        }
    }
}

void precompute_sq_table() {
    s_sq_table.assign(N_const, std::vector<std::vector<int>>(21, std::vector<int>(N_const)));
    std::vector<Flight> sorted_sq = square_flights;
    std::sort(sorted_sq.begin(), sorted_sq.end(), [](const Flight& a, const Flight& b){
        return a.end_time > b.end_time;
    });

    for (int j = 0; j < N_const; ++j) {
        calculate_all_latest_departures(j, sorted_sq);
        for (int t_idx = 0; t_idx < 21; ++t_idx) {
            for (int i = 0; i < N_const; ++i) {
                s_sq_table[j][t_idx][i] = L_buf[i][t_idx];
            }
        }
    }
}

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());
    }
    std::sort(all_circle_flights.begin(), all_circle_flights.end(), [](const Flight& a, const Flight& b){
        return a.end_time > b.end_time;
    });

    __int128 v_ci = 0;
    __int128 v_sq = 0;

    for (int j = 0; j < N_const; ++j) {
        if (target_origins[j].empty()) continue;
        calculate_all_latest_departures(j, all_circle_flights);

        for (int i : target_origins[j]) {
            for (int t_idx = 0; t_idx < 21; ++t_idx) {
                int s_ci = L_buf[i][t_idx];
                int s_sq = s_sq_table[j][t_idx][i];
                if (s_ci > s_sq) {
                    v_ci += weights[i][j];
                } else {
                    v_sq += weights[i][j];
                }
            }
        }
    }

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


// --- 探索アルゴリズム ---
int get_weighted_random_city() {
    // Bias towards high-population cities (smaller indices)
    static std::uniform_int_distribution<int> dist(0, N_const * (N_const + 1) / 2 - 1);
    int r = dist(rng);
    // x * (x + 1) / 2 > r  =>  x^2 > 2r  => x > sqrt(2r)
    int x = N_const - 1 - (int)(std::sqrt(2.0 * r));
    return std::clamp(x, 0, N_const - 1);
}

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 = get_weighted_random_city();
        int current_time = MIN_TIME;
        while (true) {
            int next_city = get_weighted_random_city();
            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; // Should not happen with current init
    }

    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 = get_weighted_random_city();
    while (new_to == original_from) {
        new_to = get_weighted_random_city();
    }

    // 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;
    
    std::vector<Flight> new_plane_schedule;
    for (int i = 0; i < flight_idx; ++i) {
        new_plane_schedule.push_back(new_solution[plane_idx][i]);
    }

    for (int i = flight_idx; i < (int)new_solution[plane_idx].size(); ++i) {
        int from_city = current_city;
        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) break;

        new_plane_schedule.push_back({from_city, to_city, start_t, end_t});
        current_city = to_city;
        current_time = end_t;
    }

    // If propagation shortened the schedule significantly, try to fill it
    while (current_time < MAX_TIME) {
        int next_city = get_weighted_random_city();
        if (next_city == current_city) continue;
        int travel_t = flight_times[current_city][next_city];
        if (current_time + travel_t > MAX_TIME) break;
        new_plane_schedule.push_back({current_city, next_city, current_time, current_time + travel_t});
        current_city = next_city;
        current_time += travel_t;
    }

    new_solution[plane_idx] = new_plane_schedule;
    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) {
            weights[i][j] = cities[i].w * cities[j].w;
            if (i != j && dists[i][j] >= 0.25 * R_const) {
                target_origins[j].push_back(i);
            }
        }
    }

    precompute_sq_table();

    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 = 0.005, T_end = 0.0001;
    const double time_limit_sec = 1.85;

    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;
}