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

• 問題: No.5023 Airlines Optimization
• ユーザー: kurigen
• 提出日時: 2026-02-25 22:34:34
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 997 ms / 1,000 ms
• コード長: 9,094 bytes
• コンパイル時間: 5,127 ms
• コンパイル使用メモリ: 363,372 KB
• 実行使用メモリ: 7,848 KB
• スコア: 34,547,805
• 最終ジャッジ日時: 2026-02-25 22:37:17
• 合計ジャッジ時間: 109,342 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

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

ソースコード

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

struct City {
    int id;
    int x, y;
    int w;
};

struct Flight {
    int from;
    int start_time;
    int to;
    int end_time;
    bool operator<(const Flight& o) const {
        return start_time > o.start_time; 
    }
};

int N, R, M, K;
vector<City> cities;
vector<Flight> sq_flights;

// 前計算テーブル
int req_time_tbl[50][50];
vector<int> valid_from[50]; // valid_from[j] : 目的地jに対して、距離が0.25R以上の出発地iのリスト
double weight_tbl[50][50];  // weight_tbl[i][j] = w_i * w_j

// スクエア航空の最も遅い出発時刻
// sq_late[ターゲット時刻ID(0~20)][目的地j][出発地i]
int sq_late[21][50][50];

// XorShift
uint32_t xor128() {
    static uint32_t x = 123456789;
    static uint32_t y = 362436069;
    static uint32_t z = 521288629;
    static uint32_t w = 88675123;
    uint32_t t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

// "HH:MM" -> 経過分数
int time_to_int(const string& s) {
    int h = stoi(s.substr(0, 2));
    int m = stoi(s.substr(3, 2));
    return h * 60 + m;
}

// 経過分数 -> "HH:MM"
string int_to_time(int t) {
    int h = t / 60;
    int m = t % 60;
    stringstream ss;
    ss << setfill('0') << setw(2) << h << ":" << setfill('0') << setw(2) << m;
    return ss.str();
}

double calc_dist(int i, int j) {
    double dx = cities[i].x - cities[j].x;
    double dy = cities[i].y - cities[j].y;
    return sqrt(dx * dx + dy * dy);
}

int calc_req_time(int i, int j) {
    double d = calc_dist(i, j);
    double t = 60.0 * d / 800.0 + 40.0;
    return ceil(t / 5.0) * 5;
}

// 一定の時刻以降のスケジュールをランダム構築
vector<Flight> build_schedule(int cur_city, int cur_time) {
    vector<Flight> res;
    // 待機時間の候補
    int wait_opts[] = {0, 0, 0, 0, 5, 5, 10, 15, 20}; 
    
    while (cur_time < 1260) {
        int wait = wait_opts[xor128() % 9];
        cur_time += wait;
        
        vector<int> cands;
        for (int i = 0; i < N; ++i) {
            if (i == cur_city) continue;
            if (cur_time + req_time_tbl[cur_city][i] <= 1260) {
                cands.push_back(i);
            }
        }
        if (cands.empty()) break;
        
        // ランダムに2都市選び、人口の多い方を目的地として選定
        int nxt = cands[xor128() % cands.size()];
        int cand2 = cands[xor128() % cands.size()];
        if (cities[cand2].w > cities[nxt].w) nxt = cand2;

        int req = req_time_tbl[cur_city][nxt];
        res.push_back({cur_city, cur_time, nxt, cur_time + req});
        cur_city = nxt;
        cur_time += req;
    }
    return res;
}

// サークル航空のスケジュール全体を評価し、シェア率を返す
double evaluate(const vector<vector<Flight>>& schedule) {
    vector<Flight> all_f;
    for (int k = 0; k < K; ++k) {
        for (const auto& f : schedule[k]) {
            all_f.push_back(f);
        }
    }
    // 出発時刻の降順ソート
    sort(all_f.begin(), all_f.end()); 
    
    double v_ci = 0;
    double v_sq = 0;
    int dp[50];
    
    for (int t_idx = 0; t_idx < 21; ++t_idx) {
        int T = 660 + t_idx * 30;
        
        for (int j = 0; j < N; ++j) {
            for (int i = 0; i < N; ++i) dp[i] = -1;
            dp[j] = INF;
            
            // 最も遅い出発時刻を求めるDP
            for (const auto& f : all_f) {
                if (f.end_time > T) continue;
                if (dp[f.to] >= f.end_time) {
                    if (f.start_time > dp[f.from]) {
                        dp[f.from] = f.start_time;
                    }
                }
            }
            
            // スコア集計
            for (int i : valid_from[j]) {
                int s_sq = sq_late[t_idx][j][i];
                int s_ci = dp[i];
                
                if (s_sq < s_ci) {
                    v_ci += weight_tbl[i][j];
                } else {
                    v_sq += weight_tbl[i][j];
                }
            }
        }
    }
    return v_ci / (v_sq + v_ci);
}

int main() {

    auto start_time_clock = chrono::high_resolution_clock::now();

    cin >> N >> R;
    
    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;
        string s, t;
        cin >> a >> s >> b >> t;
        sq_flights.push_back({a - 1, time_to_int(s), b - 1, time_to_int(t)});
    }
    cin >> K;

    // 前計算
    double R_thres_sq = (0.25 * R) * (0.25 * R);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            req_time_tbl[i][j] = calc_req_time(i, j);
            weight_tbl[i][j] = (double)cities[i].w * cities[j].w;
            
            double dx = cities[i].x - cities[j].x;
            double dy = cities[i].y - cities[j].y;
            if (i != j && (dx*dx + dy*dy) >= R_thres_sq) {
                valid_from[j].push_back(i);
            }
        }
    }

    // スクエア航空のDP前計算
    sort(sq_flights.begin(), sq_flights.end());
    for (int t_idx = 0; t_idx < 21; ++t_idx) {
        int T = 660 + t_idx * 30;
        for (int j = 0; j < N; ++j) {
            for (int i = 0; i < N; ++i) sq_late[t_idx][j][i] = -1;
            sq_late[t_idx][j][j] = INF;
            for (const auto& f : sq_flights) {
                if (f.end_time > T) continue;
                if (sq_late[t_idx][j][f.to] >= f.end_time) {
                    if (f.start_time > sq_late[t_idx][j][f.from]) {
                        sq_late[t_idx][j][f.from] = f.start_time;
                    }
                }
            }
            sq_late[t_idx][j][j] = -1;
        }
    }

    // 初期解構築
    vector<int> sorted_cities(N);
    for (int i = 0; i < N; ++i) sorted_cities[i] = i;
    sort(sorted_cities.begin(), sorted_cities.end(), [](int a, int b) {
        return cities[a].w > cities[b].w;
    });

    vector<vector<Flight>> current_schedule(K);
    vector<int> initial_cities(K);
    for (int k = 0; k < K; ++k) {
        initial_cities[k] = sorted_cities[k % N];
        current_schedule[k] = build_schedule(initial_cities[k], 360);
    }

    double current_score = evaluate(current_schedule);
    double best_score = current_score;
    vector<vector<Flight>> best_schedule = current_schedule;

    // 焼きなまし法パラメータ
    double MAX_TIME = 0.95;
    double start_temp = 0.05;
    double end_temp = 0.00001;
    double temp = start_temp;

    int iter = 0;
    while (true) {
        if ((iter & 63) == 0) {
            auto now = chrono::high_resolution_clock::now();
            double elapsed = chrono::duration<double>(now - start_time_clock).count();
            if (elapsed > MAX_TIME) break;
            double progress = elapsed / MAX_TIME;
            temp = start_temp * pow(end_temp / start_temp, progress);
        }
        iter++;
        
        // 1. 変更する飛行機をランダムに選ぶ
        int k = xor128() % K;
        auto old_sked = current_schedule[k];
        
        // 2. 近傍操作（スケジュールの一部または全部を作り直す）
        int num_f = current_schedule[k].size();
        if (num_f == 0 || xor128() % 10 == 0) { 
            // 10%の確率で最初から作り直し
            int new_start = sorted_cities[xor128() % 10];
            current_schedule[k] = build_schedule(new_start, 360);
        } else {
            // 途中のフライトをキャンセルし、そこから作り直す
            int drop_idx = xor128() % num_f;
            int restart_city = (drop_idx == 0) ? old_sked[0].from : old_sked[drop_idx - 1].to;
            int restart_time = (drop_idx == 0) ? 360 : old_sked[drop_idx - 1].end_time;
            
            current_schedule[k].resize(drop_idx);
            auto new_part = build_schedule(restart_city, restart_time);
            for (const auto& f : new_part) current_schedule[k].push_back(f);
        }
        
        // 3. 新しい解の評価
        double new_score = evaluate(current_schedule);
        
        // 4. 受理判定
        if (new_score > current_score || 
            exp((new_score - current_score) / temp) > (double)(xor128() % 10000) / 10000.0) {
            current_score = new_score;
            if (new_score > best_score) {
                best_score = new_score;
                best_schedule = current_schedule;
            }
        } else {
            current_schedule[k] = old_sked;
        }
    }

    // 出力
    for (int k = 0; k < K; ++k) {
        cout << best_schedule[k].size() << "\n";
        for (const auto& f : best_schedule[k]) {
            cout << f.from + 1 << " " 
                 << int_to_time(f.start_time) << " " 
                 << f.to + 1 << " " 
                 << int_to_time(f.end_time) << "\n";
        }
    }

    // ログ
    cerr << "Iterations: " << iter << "\n";

    return 0;
}