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

提出ソース

結果

問題	No.5023 Airlines Optimization
コンテスト
ユーザー	mogura3.0
提出日時	2026-02-26 22:59:29
言語	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`
結果	WA
実行時間	-
コード長	7,733 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	4,425 ms
コンパイル使用メモリ	359,500 KB
実行使用メモリ	7,848 KB
スコア	0
最終ジャッジ日時	2026-02-26 22:59:39
合計ジャッジ時間	8,828 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

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

権限があれば一括ダウンロードができます

ソースコード

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;

// スコア計算は省略（TLE回避のため）
void recalc_score() {
    // 暫定版：何もしない
}

// 貪欲な初期解：各飛行機にランダムな直行便を詰める（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分刻みに合わせる
            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) {
    for (int iter = 0; iter < max_iter; iter++) {
        // ランダムに近傍操作を選ぶ
        if (rand() % 2 == 0) {
            try_add_flight();
        } else {
            try_remove_flight();
        }
        // スコア再計算は省略（TLE回避）
        // recalc_score();
    }
}

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

    // 近傍探索（反復回数を減らしてTLE回避）
    local_search(1000);

    // 出力（問題文の形式に合わせる）
    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

結果

ソースコード