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

提出ソース
結果

問題	No.5023 Airlines Optimization
コンテスト
ユーザー	mogura3.0
提出日時	2026-02-26 22:54:40
言語	C++23 (gcc 15.2.0 + boost 1.89.0) コンパイル: `g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_` 実行: `./a.out`
結果	TLE
実行時間	-
コード長	9,882 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	4,489 ms
コンパイル使用メモリ	360,220 KB
実行使用メモリ	19,656 KB
スコア	0
最終ジャッジ日時	2026-02-26 22:54:50
合計ジャッジ時間	9,430 ms
ジャッジサーバーID （参考情報）	judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	TLE * 1 -- * 99
権限があれば一括ダウンロードができます
ソースコード

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

// 時刻を分に変換（06:00 -> 360, 21:00 -> 1260）
int to_minutes(const string& time_str) {
    int h = stoi(time_str.substr(0, 2));
    int m = stoi(time_str.substr(3, 2));
    return h * 60 + m;
}

// 分を時刻文字列に変換（360 -> "06:00"）
string to_time_str(int minutes) {
    int h = minutes / 60;
    int m = minutes % 60;
    char buf[6];
    sprintf(buf, "%02d:%02d", h, m);
    return string(buf);
}

// 5分単位で切り上げ
int ceil5(int x) {
    return ((x + 4) / 5) * 5;
}

// 都市間の所要時間を計算（問題文の式）
int flight_time(double d) {
    // 60 * d / 800 + 40 を分単位で計算し、5分単位で切り上げ
    return ceil5(60.0 * d / 800.0 + 40.0);
}

struct City {
    int x, y, w;
    double dist(const City& other) const {
        int dx = x - other.x;
        int dy = y - other.y;
        return sqrt(dx*dx + dy*dy);
    }
};

struct Flight {
    int from, to, dep, arr; // dep, arr は分（06:00=360, 21:00=1260）
    Flight(int f, int t, int d, int a) : from(f), to(t), dep(d), arr(a) {}
};

struct SquareFlight {
    int a, b, s, t;
};

int N, R, M, K;
vector<City> cities;
vector<SquareFlight> sq_flights;
vector<vector<Flight>> planes; // planes[k] は k 機目の飛行機の便列

// 都市間距離のキャッシュ
vector<vector<double>> dist_cache;

// スコア計算用のキャッシュ（簡略版）
double v_sq = 0, v_ci = 0;

// スクエア航空会社のみでの最遅出発時刻（簡略版：直行便のみ考慮）
int get_s_sq(int i, int j, int target_arr) {
    int best = -1e9;
    for (const auto& f : sq_flights) {
        if (f.a == i && f.b == j && f.t <= target_arr) {
            best = max(best, f.s);
        }
    }
    return best;
}

// サークル航空会社のみでの最遅出発時刻（簡略版：直行便のみ考慮）
int get_s_ci(int i, int j, int target_arr) {
    int best = -1e9;
    for (const auto& plane : planes) {
        for (const auto& f : plane) {
            if (f.from == i && f.to == j && f.arr <= target_arr) {
                best = max(best, f.dep);
            }
        }
    }
    return best;
}

// スコアを再計算（簡略版：全ペアをループ）
void recalc_score() {
    v_sq = v_ci = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j) continue;
            if (dist_cache[i][j] < 0.25 * R) continue;
            for (int t_h = 11; t_h <= 21; t_h++) {
                // 11:00, 11:30, ..., 21:00
                for (int t_m : {0, 30}) {
                    if (t_h == 21 && t_m == 30) continue;
                    int target_arr = t_h * 60 + t_m;
                    int s_sq = get_s_sq(i, j, target_arr);
                    int s_ci = get_s_ci(i, j, target_arr);
                    if (s_sq == -1e9 && s_ci == -1e9) continue;
                    if (s_ci > s_sq) {
                        v_ci += cities[i].w * cities[j].w;
                    } else {
                        v_sq += cities[i].w * cities[j].w;
                    }
                }
            }
        }
    }
}

// 貪欲な初期解：各飛行機にランダムな直行便を詰める（5分刻みを守る）
void greedy_init() {
    planes.assign(K, vector<Flight>());
    int start_min = to_minutes("06:00");
    int end_min = to_minutes("21:00");
    for (int k = 0; k < K; k++) {
        int current_time = start_min;
        int current_city = rand() % N;
        while (current_time <= end_min) {
            // 次の便の候補をランダムに選ぶ
            int next_city = rand() % N;
            if (next_city == current_city) continue;
            double d = dist_cache[current_city][next_city];
            int ft = flight_time(d);
            int dep = current_time;
            int arr = dep + ft;
            if (arr > end_min) break;
            // 出発・到着時刻を5分刻みに合わせる（既に5分刻みだが明示的に）
            dep = ceil5(dep);
            arr = ceil5(arr);
            if (arr > end_min) break;
            planes[k].emplace_back(current_city, next_city, dep, arr);
            current_time = arr;
            current_city = next_city;
        }
    }
}

// 近傍探索：1便追加（ランダムな飛行機・ランダムな位置に挿入）
bool try_add_flight() {
    int k = rand() % K;
    if (planes[k].empty()) return false;
    int pos = rand() % (planes[k].size() + 1); // 先頭 or 途中 or 末尾
    int from, to;
    if (pos == 0) {
        // 先頭に追加：現在の先頭都市からランダムな都市へ
        from = planes[k][0].from;
        to = rand() % N;
        if (from == to) return false;
        double d = dist_cache[from][to];
        int ft = flight_time(d);
        int dep = to_minutes("06:00");
        int arr = dep + ft;
        if (arr > planes[k][0].dep) return false; // 次の便と衝突
        // 5分刻みに合わせる
        dep = ceil5(dep);
        arr = ceil5(arr);
        if (arr > planes[k][0].dep) return false;
        planes[k].insert(planes[k].begin(), Flight(from, to, dep, arr));
        return true;
    } else if (pos == planes[k].size()) {
        // 末尾に追加：現在の末尾都市からランダムな都市へ
        from = planes[k].back().to;
        to = rand() % N;
        if (from == to) return false;
        double d = dist_cache[from][to];
        int ft = flight_time(d);
        int dep = planes[k].back().arr;
        int arr = dep + ft;
        if (arr > to_minutes("21:00")) return false;
        // 5分刻みに合わせる
        dep = ceil5(dep);
        arr = ceil5(arr);
        if (arr > to_minutes("21:00")) return false;
        planes[k].emplace_back(from, to, dep, arr);
        return true;
    } else {
        // 途中に追加：前後の便の間に入れる
        int prev_to = planes[k][pos-1].to;
        int next_from = planes[k][pos].from;
        if (prev_to != next_from) return false; // 連結性が崩れる
        from = prev_to;
        to = rand() % N;
        if (from == to) return false;
        double d = dist_cache[from][to];
        int ft = flight_time(d);
        int dep = planes[k][pos-1].arr;
        int arr = dep + ft;
        if (arr > planes[k][pos].dep) return false; // 次の便と衝突
        // 5分刻みに合わせる
        dep = ceil5(dep);
        arr = ceil5(arr);
        if (arr > planes[k][pos].dep) return false;
        // 新しい便を挿入し、次の便の出発都市を to に変更
        planes[k].insert(planes[k].begin() + pos, Flight(from, to, dep, arr));
        planes[k][pos+1].from = to;
        return true;
    }
}

// 近傍探索：1便削除（ランダムな飛行機・ランダムな便を削除）
bool try_remove_flight() {
    int k = rand() % K;
    if (planes[k].size() < 2) return false; // 1便だけなら削除不可（連結性が崩れる）
    int pos = rand() % planes[k].size();
    if (pos == 0) {
        // 先頭を削除：次の便の出発都市を変更
        planes[k][1].from = planes[k][0].from;
        planes[k].erase(planes[k].begin());
        return true;
    } else if (pos == planes[k].size() - 1) {
        // 末尾を削除：前の便の到着都市はそのまま
        planes[k].pop_back();
        return true;
    } else {
        // 途中を削除：前後の便を連結
        int prev_to = planes[k][pos-1].to;
        int next_from = planes[k][pos+1].from;
        if (prev_to != next_from) return false; // 連結性が崩れる
        planes[k][pos+1].from = planes[k][pos-1].to;
        planes[k].erase(planes[k].begin() + pos);
        return true;
    }
}

// 近傍探索のメインループ
void local_search(int max_iter) {
    double best_score = 0;
    vector<vector<Flight>> best_planes = planes;
    for (int iter = 0; iter < max_iter; iter++) {
        // ランダムに近傍操作を選ぶ
        bool success = false;
        if (rand() % 2 == 0) {
            success = try_add_flight();
        } else {
            success = try_remove_flight();
        }
        if (!success) continue;
        // スコア再計算（簡略版）
        recalc_score();
        double S = (v_sq + v_ci == 0) ? 0 : v_ci / (v_sq + v_ci);
        if (S > best_score) {
            best_score = S;
            best_planes = planes;
        } else {
            // 悪化したらロールバック（簡略版：常にロールバック）
            planes = best_planes;
        }
    }
    planes = best_planes;
}

int main() {
    srand(time(NULL));

    // 入力読み込み（問題文の形式に合わせる）
    cin >> N >> R;
    cities.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> cities[i].x >> cities[i].y >> cities[i].w;
    }
    cin >> M;
    sq_flights.resize(M);
    for (int i = 0; i < M; i++) {
        string s_str, t_str;
        cin >> sq_flights[i].a >> s_str >> sq_flights[i].b >> t_str;
        sq_flights[i].a--; // 1-indexed -> 0-indexed
        sq_flights[i].b--;
        sq_flights[i].s = to_minutes(s_str);
        sq_flights[i].t = to_minutes(t_str);
    }
    cin >> K;

    // 距離キャッシュを計算
    dist_cache.assign(N, vector<double>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            dist_cache[i][j] = cities[i].dist(cities[j]);
        }
    }

    // 貪欲初期解
    greedy_init();

    // 近傍探索（最大反復回数は適当に設定）
    local_search(10000);

    // 出力（問題文の形式に合わせる）
    for (int k = 0; k < K; k++) {
        cout << planes[k].size() << "\n";
        for (const auto& f : planes[k]) {
            cout << f.from+1 << " " << to_time_str(f.dep) << " "
                 << f.to+1 << " " << to_time_str(f.arr) << "\n";
        }
    }

    return 0;
}
yukicoder

結果

ソースコード
