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

• 問題: No.5023 Airlines Optimization
• ユーザー: shogo314
• 提出日時: 2026-02-25 21:42:52
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 912 ms / 1,000 ms
• コード長: 6,209 bytes
• コンパイル時間: 2,727 ms
• コンパイル使用メモリ: 224,784 KB
• 実行使用メモリ: 7,848 KB
• スコア: 37,099,625
• 最終ジャッジ日時: 2026-02-25 21:44:34
• 合計ジャッジ時間: 99,861 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

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

ソースコード

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

using namespace std;

// --- 定数・構造体 ---
const int MIN_TIME = 6 * 60;
const int MAX_TIME = 21 * 60;

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

// --- ユーティリティ関数 ---
int time_to_int(string s) {
    return stoi(s.substr(0, 2)) * 60 + stoi(s.substr(3, 2));
}

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

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

// --- グローバル管理 ---
int ssq[48][48][21];
int capture_count[48][48][21]; // 需要の重複を避けるためのカウント
vector<Flight> schedules[25];
int current_start_city[25];

// --- 1機分のスケジュール再構築ロジック ---
vector<Flight> rebuild_schedule(int k, int N, const vector<City>& cities) {
    vector<Flight> sch;
    int cur_city = current_start_city[k];
    int cur_time = MIN_TIME;
    
    while (cur_time < MAX_TIME) {
        int best_to = -1, best_s = -1, best_dur = -1;
        double max_val = -1e18;

        // 待機時間を考慮（最大120分）
        for (int wait = 0; wait <= 120; wait += 5) {
            int st = cur_time + wait;
            if (st > MAX_TIME - 45) break;

            for (int nxt = 1; nxt <= N; ++nxt) {
                if (cur_city == nxt) continue;
                int dur = get_travel_time(cities[cur_city-1], cities[nxt-1]);
                int arr = st + dur;
                if (arr > MAX_TIME) continue;
                
                double dx = cities[cur_city-1].x - cities[nxt-1].x;
                double dy = cities[cur_city-1].y - cities[nxt-1].y;
                if (sqrt(dx*dx + dy*dy) < 250.0) continue;

                long long score = 0;
                for (int t = 0; t < 21; ++t) {
                    // 他機がカバーしていない需要（capture_count == 0）を優先
                    if (arr <= 660 + t * 30 && capture_count[cur_city][nxt][t] == 0) {
                        if (st > ssq[cur_city][nxt][t]) {
                            score += cities[cur_city-1].w * cities[nxt-1].w;
                        }
                    }
                }

                double evaluation = (double)score;
                // 16時〜19時のピークタイム加点
                if (st >= 16 * 60 && st <= 19 * 60) evaluation *= 1.3;
                // 目的地が人口上位ならポテンシャル加点
                evaluation += (double)cities[nxt-1].w / 1e5;
                // 待機ペナルティ
                evaluation -= (double)wait * 0.5;

                if (evaluation > max_val) {
                    max_val = evaluation; best_to = nxt; best_s = st; best_dur = dur;
                }
            }
        }

        if (best_to != -1 && max_val > 0) {
            sch.push_back({cur_city, best_to, best_s, best_s + best_dur});
            cur_city = best_to; cur_time = best_s + best_dur;
        } else {
            // 有効な便がない場合はハブ(1)へ移動して終了
            int hub = 1;
            if (cur_city == hub) break;
            int dur = get_travel_time(cities[cur_city-1], cities[0]);
            if (cur_time + dur <= MAX_TIME) {
                sch.push_back({cur_city, hub, cur_time, cur_time + dur});
                cur_city = hub; cur_time += dur;
            } else break;
        }
    }
    return sch;
}

int main() {
    auto start_time = chrono::system_clock::now();
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int N, R; cin >> N >> R;
    vector<City> cities(N);
    for (int i = 0; i < N; ++i) cin >> cities[i].x >> cities[i].y >> cities[i].w;
    
    int M; cin >> M;
    for (int i = 0; i < 48; ++i) for (int j = 0; j < 48; ++j) for (int t = 0; t < 21; ++t) ssq[i][j][t] = -1;
    for (int i = 0; i < M; ++i) {
        int a, b; string s, t; cin >> a >> s >> b >> t;
        int si = time_to_int(s), ti = time_to_int(t);
        for (int k = 0; k < 21; ++k) if (ti <= 660 + k * 30) ssq[a][b][k] = max(ssq[a][b][k], si);
    }
    int K; cin >> K;

    // --- 初期解の構築 ---
    for (int k = 0; k < K; ++k) current_start_city[k] = (k % 10) + 1;
    for (int k = 0; k < K; ++k) {
        schedules[k] = rebuild_schedule(k, N, cities);
        for (auto& f : schedules[k]) {
            for (int t = 0; t < 21; ++t) {
                if (f.t <= 660 + t * 30 && f.s > ssq[f.from][f.to][t]) capture_count[f.from][f.to][t]++;
            }
        }
    }

    // --- 山登り法 ---
    int iter = 0;
    while (true) {
        iter++;
        if (iter % 20 == 0) {
            auto now = chrono::system_clock::now();
            if (chrono::duration_cast<chrono::milliseconds>(now - start_time).count() > 900) break;
        }

        int k = rand() % K;
        // 現在の機体の占有分を一旦解除
        for (auto& f : schedules[k]) {
            for (int t = 0; t < 21; ++t) {
                if (f.t <= 660 + t * 30 && f.s > ssq[f.from][f.to][t]) capture_count[f.from][f.to][t]--;
            }
        }

        // 開始都市の微調整（多様性のため）
        int old_start = current_start_city[k];
        if (rand() % 10 == 0) current_start_city[k] = (rand() % N) + 1;

        // スケジュール再構築
        schedules[k] = rebuild_schedule(k, N, cities);

        // 新しい占有を登録
        for (auto& f : schedules[k]) {
            for (int t = 0; t < 21; ++t) {
                if (f.t <= 660 + t * 30 && f.s > ssq[f.from][f.to][t]) capture_count[f.from][f.to][t]++;
            }
        }
    }

    // --- 出力 ---
    for (int k = 0; k < K; ++k) {
        cout << schedules[k].size() << "\n";
        for (auto& f : schedules[k]) {
            cout << f.from << " " << int_to_time(f.s) << " " << f.to << " " << int_to_time(f.t) << "\n";
        }
    }

    return 0;
}