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

• 問題: No.5023 Airlines Optimization
• ユーザー: hitonanode
• 提出日時: 2026-02-25 23:59:52
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 18,570 bytes
• コンパイル時間: 3,756 ms
• コンパイル使用メモリ: 275,500 KB
• 実行使用メモリ: 7,968 KB
• スコア: 0
• 最終ジャッジ日時: 2026-02-26 00:04:23
• 合計ジャッジ時間: 124,197 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

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

ソースコード

#include <algorithm>
#include <chrono>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <limits>
#include <numeric>
#include <random>
#include <string>
#include <vector>

namespace {

constexpr int START_TIME = 6 * 60;
constexpr int END_TIME = 21 * 60;
constexpr int SCORE_START = 11 * 60;
constexpr int SCORE_INTERVAL = 30;
constexpr int DEADLINE_COUNT = 21;
constexpr int SOURCE_CAND_LIMIT = 46;
constexpr uint32_t RNG_SEED = 20260225u;
constexpr int DESTROY_MIN_PLANES = 2;
constexpr int DESTROY_MAX_PLANES = 4;
constexpr double REPAIR_TIME_LIMIT_SEC = 0.90;
constexpr int NEG_INF = -1'000'000'000;

struct City {
    int x = 0;
    int y = 0;
    long long w = 0;
};

struct Flight {
    int from = -1;
    int to = -1;
    int dep = -1;
    int arr = -1;
};

struct Candidate {
    bool valid = false;
    long long gain = std::numeric_limits<long long>::min();
    int from = -1;
    int to = -1;
    int dep = -1;
    int arr = -1;
};

struct PlaneBuildResult {
    std::vector<Flight> route;
    long long gain = 0;
};

int parse_time(const std::string& s) {
    return std::stoi(s.substr(0, 2)) * 60 + std::stoi(s.substr(3, 2));
}

std::string format_time(int t) {
    char buf[6];
    std::snprintf(buf, sizeof(buf), "%02d:%02d", t / 60, t % 60);
    return std::string(buf);
}

int idx3(int n, int i, int j, int k) {
    return (i * n + j) * DEADLINE_COUNT + k;
}

bool is_better_candidate(const Candidate& a, const Candidate& b) {
    if (!b.valid) {
        return true;
    }
    const int da = a.arr - a.dep;
    const int db = b.arr - b.dep;
    const __int128 lhs = static_cast<__int128>(a.gain) * static_cast<__int128>(db);
    const __int128 rhs = static_cast<__int128>(b.gain) * static_cast<__int128>(da);
    if (lhs != rhs) {
        return lhs > rhs;
    }
    if (a.gain != b.gain) {
        return a.gain > b.gain;
    }
    if (a.dep != b.dep) {
        return a.dep > b.dep;
    }
    if (a.arr != b.arr) {
        return a.arr > b.arr;
    }
    if (a.to != b.to) {
        return a.to < b.to;
    }
    return a.from < b.from;
}

bool parse_bool_token(const std::string& s, bool& out) {
    std::string v = s;
    std::transform(v.begin(), v.end(), v.begin(), [](unsigned char c) {
        return static_cast<char>(std::tolower(c));
    });
    if (v == "1" || v == "on" || v == "true") {
        out = true;
        return true;
    }
    if (v == "0" || v == "off" || v == "false") {
        out = false;
        return true;
    }
    return false;
}

long long estimate_score_like_objective(
    int n,
    const std::vector<std::vector<long long>>& weight,
    const std::vector<int>& sq_latest,
    const std::vector<int>& ci_latest
) {
    long long v_ci = 0;
    long long v_sq = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            const long long w = weight[i][j];
            if (w == 0) {
                continue;
            }
            for (int k = 0; k < DEADLINE_COUNT; ++k) {
                const int p = idx3(n, i, j, k);
                if (ci_latest[p] > sq_latest[p]) {
                    v_ci += w;
                } else {
                    v_sq += w;
                }
            }
        }
    }
    if (v_ci + v_sq == 0) {
        return 0;
    }
    return static_cast<long long>((1'000'000.0L * static_cast<long double>(v_ci)) /
                                  static_cast<long double>(v_ci + v_sq));
}

bool flight_desc_order(const Flight& a, const Flight& b) {
    if (a.dep != b.dep) {
        return a.dep > b.dep;
    }
    if (a.arr != b.arr) {
        return a.arr > b.arr;
    }
    if (a.to != b.to) {
        return a.to < b.to;
    }
    return a.from < b.from;
}

std::vector<int> compute_ci_latest_exact(
    int n,
    const std::vector<Flight>& flights_sorted,
    const std::vector<int>& deadlines
) {
    std::vector<int> ci_latest(n * n * DEADLINE_COUNT, NEG_INF);
    std::vector<int> latest(n, NEG_INF);
    for (int dest = 0; dest < n; ++dest) {
        for (int d = 0; d < DEADLINE_COUNT; ++d) {
            std::fill(latest.begin(), latest.end(), NEG_INF);
            latest[dest] = deadlines[d];
            for (const Flight& f : flights_sorted) {
                if (latest[f.to] >= f.arr && latest[f.from] < f.dep) {
                    latest[f.from] = f.dep;
                }
            }
            for (int src = 0; src < n; ++src) {
                ci_latest[idx3(n, src, dest, d)] = latest[src];
            }
        }
    }
    return ci_latest;
}

std::vector<int> compute_latest_to_target_deadline(
    int n,
    const std::vector<Flight>& flights_sorted,
    int target,
    int deadline
) {
    std::vector<int> latest(n, NEG_INF);
    latest[target] = deadline;
    for (const Flight& f : flights_sorted) {
        if (latest[f.to] >= f.arr && latest[f.from] < f.dep) {
            latest[f.from] = f.dep;
        }
    }
    return latest;
}

PlaneBuildResult build_plane_greedy(
    bool snap_arrival_to_30,
    const std::vector<std::vector<int>>& nearest_sources,
    const std::vector<std::vector<int>>& duration,
    const std::vector<std::vector<long long>>& weight,
    const std::vector<int>& sq_latest,
    const std::vector<int>& deadlines,
    std::vector<Flight>& flights_sorted,
    std::vector<int>& ci_latest
) {
    const int n = static_cast<int>(duration.size());
    PlaneBuildResult result;
    std::vector<Flight> rev_route;
    long long plane_gain = 0;

    auto evaluate_candidate_gain = [&](int from, int to, int dep, int arr) {
        if (dep < START_TIME || arr > END_TIME) {
            return 0LL;
        }

        std::vector<std::pair<int, int>> downstream_states;
        downstream_states.reserve(n * DEADLINE_COUNT);
        for (int dest = 0; dest < n; ++dest) {
            bool used = false;
            for (int src = 0; src < n; ++src) {
                if (weight[src][dest] > 0) {
                    used = true;
                    break;
                }
            }
            if (!used) {
                continue;
            }
            for (int k = 0; k < DEADLINE_COUNT; ++k) {
                if (ci_latest[idx3(n, to, dest, k)] >= arr) {
                    downstream_states.push_back({dest, k});
                }
            }
        }
        if (downstream_states.empty()) {
            return 0LL;
        }

        const std::vector<int> latest_to_from =
            compute_latest_to_target_deadline(n, flights_sorted, from, dep);

        long long gain = 0;
        for (int src = 0; src < n; ++src) {
            const int candidate_depart = latest_to_from[src];
            if (candidate_depart <= NEG_INF / 2) {
                continue;
            }
            for (const auto& [dest, k] : downstream_states) {
                const int p = idx3(n, src, dest, k);
                if (candidate_depart > sq_latest[p] && candidate_depart > ci_latest[p]) {
                    gain += weight[src][dest];
                }
            }
        }
        return gain;
    };

    auto push_flight_and_recompute = [&](const Flight& f) {
        const auto it = std::lower_bound(flights_sorted.begin(), flights_sorted.end(), f, flight_desc_order);
        flights_sorted.insert(it, f);
        ci_latest = compute_ci_latest_exact(n, flights_sorted, deadlines);
    };

    Candidate best_init;
    const int init_arrival = END_TIME;
    for (int terminal = 0; terminal < n; ++terminal) {
        for (const int from : nearest_sources[terminal]) {
            const int dep = init_arrival - duration[from][terminal];
            if (dep < START_TIME) {
                continue;
            }
            Candidate cand;
            cand.valid = true;
            cand.from = from;
            cand.to = terminal;
            cand.dep = dep;
            cand.arr = init_arrival;
            cand.gain = evaluate_candidate_gain(cand.from, cand.to, cand.dep, cand.arr);
            if (is_better_candidate(cand, best_init)) {
                best_init = cand;
            }
        }
    }

    if (!best_init.valid || best_init.gain <= 0) {
        return result;
    }

    const Flight init_flight{best_init.from, best_init.to, best_init.dep, best_init.arr};
    push_flight_and_recompute(init_flight);
    rev_route.push_back(init_flight);
    plane_gain += best_init.gain;

    int head_city = best_init.from;
    int head_departure = best_init.dep;

    while (true) {
        if (head_departure < START_TIME) {
            break;
        }
        Candidate best_next;
        int fixed_arrival = head_departure;
        if (snap_arrival_to_30) {
            fixed_arrival = ((head_departure + 15) / 30) * 30;
            fixed_arrival = std::min(fixed_arrival, END_TIME);
            if (fixed_arrival > head_departure) {
                fixed_arrival -= 30;
            }
        }
        if (fixed_arrival < START_TIME) {
            break;
        }

        for (const int from : nearest_sources[head_city]) {
            const int dep = fixed_arrival - duration[from][head_city];
            if (dep < START_TIME) {
                continue;
            }
            Candidate cand;
            cand.valid = true;
            cand.from = from;
            cand.to = head_city;
            cand.dep = dep;
            cand.arr = fixed_arrival;
            cand.gain = evaluate_candidate_gain(cand.from, cand.to, cand.dep, cand.arr);
            if (is_better_candidate(cand, best_next)) {
                best_next = cand;
            }
        }

        if (!best_next.valid || best_next.gain <= 0) {
            break;
        }

        const Flight next_flight{best_next.from, head_city, best_next.dep, best_next.arr};
        push_flight_and_recompute(next_flight);
        rev_route.push_back(next_flight);
        plane_gain += best_next.gain;

        head_city = best_next.from;
        head_departure = best_next.dep;
    }

    std::reverse(rev_route.begin(), rev_route.end());
    result.route = std::move(rev_route);
    result.gain = plane_gain;
    return result;
}

}  // namespace

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    bool snap_arrival_to_30 = false;
    if (const char* env = std::getenv("ARRIVAL_30"); env != nullptr) {
        bool parsed = false;
        if (!parse_bool_token(env, parsed)) {
            std::cerr << "invalid ARRIVAL_30: " << env << "\n";
            return 1;
        }
        snap_arrival_to_30 = parsed;
    }

    int n = 0;
    int r = 0;
    std::cin >> n >> r;

    std::vector<City> cities(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> cities[i].x >> cities[i].y >> cities[i].w;
    }

    int m = 0;
    std::cin >> m;
    std::vector<Flight> sq_flights(m);
    for (int i = 0; i < m; ++i) {
        std::string s;
        std::string t;
        std::cin >> sq_flights[i].from >> s >> sq_flights[i].to >> t;
        --sq_flights[i].from;
        --sq_flights[i].to;
        sq_flights[i].dep = parse_time(s);
        sq_flights[i].arr = parse_time(t);
    }

    int k_plane = 0;
    std::cin >> k_plane;

    std::vector<int> deadlines(DEADLINE_COUNT);
    for (int k = 0; k < DEADLINE_COUNT; ++k) {
        deadlines[k] = SCORE_START + SCORE_INTERVAL * k;
    }

    std::vector<std::vector<int>> duration(n, std::vector<int>(n, 0));
    std::vector<std::vector<long long>> weight(n, std::vector<long long>(n, 0));
    std::vector<std::vector<int>> nearest_sources(n);
    const long double threshold = static_cast<long double>(r) * 0.25L;

    for (int dest = 0; dest < n; ++dest) {
        std::vector<std::pair<long long, int>> cand;
        cand.reserve(n - 1);
        for (int src = 0; src < n; ++src) {
            if (src == dest) {
                continue;
            }
            const long long dx = static_cast<long long>(cities[src].x) - cities[dest].x;
            const long long dy = static_cast<long long>(cities[src].y) - cities[dest].y;
            const long long d2 = dx * dx + dy * dy;
            cand.push_back({d2, src});
        }
        std::sort(cand.begin(), cand.end(), [](const auto& a, const auto& b) {
            if (a.first != b.first) {
                return a.first < b.first;
            }
            return a.second < b.second;
        });
        const int lim = std::min(SOURCE_CAND_LIMIT, static_cast<int>(cand.size()));
        nearest_sources[dest].reserve(lim);
        for (int i = 0; i < lim; ++i) {
            nearest_sources[dest].push_back(cand[i].second);
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j) {
                continue;
            }
            const long double dx = static_cast<long double>(cities[i].x - cities[j].x);
            const long double dy = static_cast<long double>(cities[i].y - cities[j].y);
            const long double dist = std::sqrt(dx * dx + dy * dy);
            const long double raw = 60.0L * dist / 800.0L + 40.0L;
            duration[i][j] = static_cast<int>(std::ceil((raw - 1e-12L) / 5.0L)) * 5;

            if (dist + 1e-12L >= threshold) {
                weight[i][j] = cities[i].w * cities[j].w;
            }
        }
    }

    std::sort(sq_flights.begin(), sq_flights.end(), [](const Flight& a, const Flight& b) {
        if (a.dep != b.dep) {
            return a.dep > b.dep;
        }
        if (a.arr != b.arr) {
            return a.arr > b.arr;
        }
        if (a.to != b.to) {
            return a.to < b.to;
        }
        return a.from < b.from;
    });

    std::vector<int> sq_latest(n * n * DEADLINE_COUNT, NEG_INF);
    std::vector<int> latest(n, NEG_INF);
    for (int dest = 0; dest < n; ++dest) {
        for (int d = 0; d < DEADLINE_COUNT; ++d) {
            std::fill(latest.begin(), latest.end(), NEG_INF);
            latest[dest] = deadlines[d];
            for (const Flight& f : sq_flights) {
                if (latest[f.to] >= f.arr && latest[f.from] < f.dep) {
                    latest[f.from] = f.dep;
                }
            }
            for (int src = 0; src < n; ++src) {
                sq_latest[idx3(n, src, dest, d)] = latest[src];
            }
        }
    }

    std::vector<Flight> current_flights_sorted;
    std::vector<int> ci_latest = compute_ci_latest_exact(n, current_flights_sorted, deadlines);
    std::vector<std::vector<Flight>> answer(k_plane);

    std::cerr << "arrival30=" << (snap_arrival_to_30 ? "on" : "off") << "\n";

    // 初期解: 全機体を通常貪欲で構築
    for (int plane_id = 0; plane_id < k_plane; ++plane_id) {
        PlaneBuildResult built = build_plane_greedy(
            snap_arrival_to_30,
            nearest_sources,
            duration,
            weight,
            sq_latest,
            deadlines,
            current_flights_sorted,
            ci_latest
        );
        answer[plane_id] = std::move(built.route);
        std::cerr << "plane " << (plane_id + 1) << ": flights=" << answer[plane_id].size()
                  << ", gain=" << built.gain
                  << ", approx_score=" << estimate_score_like_objective(n, weight, sq_latest, ci_latest)
                  << "\n";
    }

    long long current_score = estimate_score_like_objective(n, weight, sq_latest, ci_latest);
    std::cerr << "initial_score=" << current_score << "\n";

    // 破壊再構築: ランダムに 2〜4 機を白紙に戻して再貪欲
    std::mt19937 rng(RNG_SEED);
    std::uniform_int_distribution<int> destroy_cnt_dist(DESTROY_MIN_PLANES, DESTROY_MAX_PLANES);
    std::vector<int> perm(k_plane);
    std::iota(perm.begin(), perm.end(), 0);

    int iterations = 0;
    int accepted = 0;
    const auto repair_start = std::chrono::steady_clock::now();
    while (true) {
        const auto now = std::chrono::steady_clock::now();
        const double elapsed = std::chrono::duration<double>(now - repair_start).count();
        if (elapsed >= REPAIR_TIME_LIMIT_SEC) {
            break;
        }
        ++iterations;

        std::shuffle(perm.begin(), perm.end(), rng);
        const int destroy_cnt = std::min(k_plane, destroy_cnt_dist(rng));
        std::vector<int> destroyed_planes(perm.begin(), perm.begin() + destroy_cnt);
        std::vector<char> destroyed(k_plane, 0);
        for (int p : destroyed_planes) {
            destroyed[p] = 1;
        }

        std::vector<Flight> trial_flights;
        for (int plane_id = 0; plane_id < k_plane; ++plane_id) {
            if (destroyed[plane_id]) {
                continue;
            }
            for (const Flight& f : answer[plane_id]) {
                trial_flights.push_back(f);
            }
        }
        std::sort(trial_flights.begin(), trial_flights.end(), flight_desc_order);
        std::vector<int> trial_ci_latest = compute_ci_latest_exact(n, trial_flights, deadlines);

        std::vector<std::vector<Flight>> rebuilt_routes(destroy_cnt);
        for (int i = 0; i < destroy_cnt; ++i) {
            PlaneBuildResult rebuilt = build_plane_greedy(
                snap_arrival_to_30,
                nearest_sources,
                duration,
                weight,
                sq_latest,
                deadlines,
                trial_flights,
                trial_ci_latest
            );
            rebuilt_routes[i] = std::move(rebuilt.route);
        }

        const long long trial_score = estimate_score_like_objective(n, weight, sq_latest, trial_ci_latest);
        if (trial_score > current_score) {
            ++accepted;
            for (int i = 0; i < destroy_cnt; ++i) {
                answer[destroyed_planes[i]] = std::move(rebuilt_routes[i]);
            }
            current_flights_sorted = std::move(trial_flights);
            ci_latest.swap(trial_ci_latest);
            current_score = trial_score;
            std::cerr << "improve iter=" << iterations
                      << " score=" << current_score
                      << " destroy=" << destroy_cnt
                      << " accepted=" << accepted << "\n";
        }
    }

    std::cerr << "repair_done iter=" << iterations
              << " accepted=" << accepted
              << " final_score=" << current_score << "\n";

    for (int plane_id = 0; plane_id < k_plane; ++plane_id) {
        const auto& route = answer[plane_id];
        std::cout << route.size() << "\n";
        for (const Flight& f : route) {
            std::cout << (f.from + 1) << ' ' << format_time(f.dep) << ' '
                      << (f.to + 1) << ' ' << format_time(f.arr) << "\n";
        }
    }

    return 0;
}