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

• 問題: No.5023 Airlines Optimization
• ユーザー: hotpepsi
• 提出日時: 2026-02-28 15:18:19
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 9,758 bytes
• コンパイル時間: 4,056 ms
• コンパイル使用メモリ: 267,912 KB
• 実行使用メモリ: 20,296 KB
• スコア: 0
• 最終ジャッジ日時: 2026-02-28 15:18:28
• 合計ジャッジ時間: 9,322 ms
• ジャッジサーバーID （参考情報）: judge2 / judge7

ファイルパターン	結果
other	TLE * 1 -- * 99

ソースコード

#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<std::pair<int, int>> target_pairs;
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;
            }
        }
    }
}

// --- スコア計算関連 ---
std::vector<int> calculate_latest_departures(int dest_city, int target_arrival, const std::vector<Flight>& flights) {
    std::vector<int> reachable_at(N_const, -1);
    reachable_at[dest_city] = target_arrival;

    std::vector<std::vector<std::pair<int, int>>> adj(N_const);
    for(const auto& f : flights) {
        adj[f.to].push_back({f.from, f.start_time});
    }

    std::vector<bool> visited(N_const, false);
    for (int i = 0; i < N_const; ++i) {
        int best_v = -1;
        for (int v = 0; v < N_const; ++v) {
            if (!visited[v] && (best_v == -1 || reachable_at[v] > reachable_at[best_v])) {
                best_v = v;
            }
        }

        if (best_v == -1 || reachable_at[best_v] == -1) break;
        visited[best_v] = true;
        int u = best_v;
        int t = reachable_at[u];

        for (const auto& f : flights) {
            if (f.to == u && f.end_time <= t) {
                if (reachable_at[f.from] < f.start_time) {
                    reachable_at[f.from] = f.start_time;
                }
            }
        }
    }

    std::vector<int> latest_dep(N_const, -1);
    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) {
                    latest_dep[i] = std::max(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 = 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 = rng() % N_const;
    while (new_to == original_from) {
        new_to = rng() % 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;
        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
        }

        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();

    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 = 2.8;

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