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

• 問題: No.5023 Airlines Optimization
• ユーザー: てんぷら
• 提出日時: 2026-02-25 22:43:47
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 742 ms / 1,000 ms
• コード長: 17,787 bytes
• コンパイル時間: 8,302 ms
• コンパイル使用メモリ: 270,452 KB
• 実行使用メモリ: 7,848 KB
• スコア: 48,409,059
• 最終ジャッジ日時: 2026-02-25 22:45:04
• 合計ジャッジ時間: 74,781 ms
• ジャッジサーバーID （参考情報）: judge7 / judge4

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

ソースコード

#include <algorithm>
#include <array>
#include <cmath>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;

using ll = long long;

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

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

struct PlanePlan {
    vector<int> route;
    int offset = 0;
    int duration = 0;
};

struct DemandTerm {
    int src, dst;
    long double w;
    array<int, 21> sq;
};

constexpr int START_HOUR = 6;
constexpr int END_HOUR = 21;
constexpr int SLOT_MIN = 5;
constexpr int MAX_SLOT = (END_HOUR - START_HOUR) * 60 / SLOT_MIN; // 180
constexpr int TARGET_CNT = 21;
constexpr int TARGET_START = (11 - START_HOUR) * 60 / SLOT_MIN; // 60
constexpr int TARGET_STEP = 30 / SLOT_MIN;                      // 6
constexpr int NEG_INF = -1e9;

int parseTimeToSlot(const string &s) {
    auto pos = s.find(':');
    int hh = stoi(s.substr(0, pos));
    int mm = stoi(s.substr(pos + 1));
    return (hh * 60 + mm - START_HOUR * 60) / SLOT_MIN;
}

string slotToTime(int slot) {
    int total = START_HOUR * 60 + slot * SLOT_MIN;
    int hh = total / 60;
    int mm = total % 60;
    char buf[16];
    snprintf(buf, sizeof(buf), "%02d:%02d", hh, mm);
    return string(buf);
}

int calcDurationSlot(const City &c1, const City &c2) {
    double dx = double(c1.x) - double(c2.x);
    double dy = double(c1.y) - double(c2.y);
    double d = sqrt(dx * dx + dy * dy);
    double minutes = 60.0 * d / 800.0 + 40.0;
    return (int)ceil(minutes / 5.0 - 1e-12);
}

int routeDuration(const vector<int> &route, const vector<vector<int>> &dur) {
    int total = 0;
    for(int i = 1; i < (int)route.size(); ++i) {
        if(route[i - 1] == route[i])
            return MAX_SLOT + 1;
        total += dur[route[i - 1]][route[i]];
        if(total > MAX_SLOT)
            return total;
    }
    return total;
}

void normalizePlane(PlanePlan &p, const vector<vector<int>> &dur) {
    if(p.route.empty())
        p.route.push_back(0);
    vector<int> fixed;
    fixed.reserve(p.route.size());
    fixed.push_back(p.route[0]);
    for(int i = 1; i < (int)p.route.size(); ++i) {
        if(p.route[i] != p.route[i - 1])
            fixed.push_back(p.route[i]);
    }
    p.route.swap(fixed);
    if(p.route.empty())
        p.route.push_back(0);
    p.duration = routeDuration(p.route, dur);
    while(p.duration > MAX_SLOT && (int)p.route.size() > 1) {
        p.route.pop_back();
        p.duration = routeDuration(p.route, dur);
    }
    int lim = max(0, MAX_SLOT - p.duration);
    p.offset = min(max(0, p.offset), lim);
}

void appendPlaneFlights(const PlanePlan &p, const vector<vector<int>> &dur, vector<Flight> &out) {
    int tm = p.offset;
    for(int i = 1; i < (int)p.route.size(); ++i) {
        int a = p.route[i - 1];
        int b = p.route[i];
        int nt = tm + dur[a][b];
        out.push_back({a, b, tm, nt});
        tm = nt;
    }
}

vector<Flight> flattenPlans(const vector<PlanePlan> &plans, const vector<vector<int>> &dur) {
    vector<Flight> flights;
    for(const auto &p : plans)
        appendPlaneFlights(p, dur, flights);
    return flights;
}

struct ScoreEvaluator {
    int N;
    uint64_t allMask;

    explicit ScoreEvaluator(int n) : N(n) {
        allMask = (N == 64 ? ~0ULL : ((1ULL << N) - 1));
    }

    vector<vector<Flight>> buildByStart(const vector<Flight> &flights, int target) const {
        vector<vector<Flight>> byStart(target + 1);
        for(const auto &f : flights) {
            if(f.s < 0 || f.s > target || f.t < 0 || f.t > target)
                continue;
            byStart[f.s].push_back(f);
        }
        return byStart;
    }

    vector<vector<int>> latestMatrixForTarget(const vector<vector<Flight>> &byStart, int target) const {
        vector<vector<uint64_t>> reach(target + 1, vector<uint64_t>(N, 0ULL));
        for(int c = 0; c < N; ++c)
            reach[target][c] = (1ULL << c);

        for(int tm = target - 1; tm >= 0; --tm) {
            for(int c = 0; c < N; ++c)
                reach[tm][c] = reach[tm + 1][c];
            for(const auto &f : byStart[tm]) {
                reach[tm][f.a] |= reach[f.t][f.b];
            }
        }

        vector<vector<int>> latest(N, vector<int>(N, NEG_INF));
        for(int src = 0; src < N; ++src) {
            uint64_t rem = allMask;
            for(int tm = target; tm >= 0 && rem; --tm) {
                uint64_t m = reach[tm][src] & rem;
                while(m) {
                    int dst = __builtin_ctzll(m);
                    latest[src][dst] = tm;
                    rem &= ~(1ULL << dst);
                    m &= (m - 1);
                }
            }
        }
        return latest;
    }

    vector<vector<vector<int>>> precomputeSqBest(const vector<Flight> &sqFlights) const {
        vector<vector<vector<int>>> sqBest(TARGET_CNT, vector<vector<int>>(N, vector<int>(N, NEG_INF)));
        for(int k = 0; k < TARGET_CNT; ++k) {
            int target = TARGET_START + TARGET_STEP * k;
            auto byStart = buildByStart(sqFlights, target);
            sqBest[k] = latestMatrixForTarget(byStart, target);
        }
        return sqBest;
    }

    vector<int> latestToDstByDeadline(const vector<Flight> &flights, int dst, int deadline) const {
        auto byStart = buildByStart(flights, deadline);
        vector<vector<uint64_t>> reach(deadline + 1, vector<uint64_t>(N, 0ULL));
        reach[deadline][dst] = 1ULL;
        for(int tm = deadline - 1; tm >= 0; --tm) {
            for(int c = 0; c < N; ++c)
                reach[tm][c] = reach[tm + 1][c];
            for(const auto &f : byStart[tm]) {
                if(reach[f.t][f.b] & 1ULL)
                    reach[tm][f.a] = 1ULL;
            }
        }
        vector<int> best(N, NEG_INF);
        for(int src = 0; src < N; ++src) {
            for(int tm = deadline; tm >= 0; --tm) {
                if(reach[tm][src] & 1ULL) {
                    best[src] = tm;
                    break;
                }
            }
        }
        return best;
    }

    double score(
        const vector<Flight> &ciFlights,
        const vector<DemandTerm> &demands) const {
        long double vSq = 0.0L, vCi = 0.0L;

        for(int k = 0; k < TARGET_CNT; ++k) {
            int target = TARGET_START + TARGET_STEP * k;
            auto byStart = buildByStart(ciFlights, target);
            auto latest = latestMatrixForTarget(byStart, target);

            for(const auto &d : demands) {
                if(d.sq[k] < latest[d.src][d.dst])
                    vCi += d.w;
                else
                    vSq += d.w;
            }
        }

        long double den = vSq + vCi;
        if(den <= 0.0L)
            return 0.0;
        return (double)(vCi / den);
    }
};

PlanePlan buildCyclicPlan(
    const vector<int> &cycle,
    int offset,
    const vector<vector<int>> &dur) {
    PlanePlan p;
    if(cycle.empty())
        return p;

    p.route.push_back(cycle[0]);
    p.offset = offset;

    int tm = offset;
    int cur = cycle[0];
    int idx = 1 % (int)cycle.size();

    while(true) {
        int nxt = cycle[idx];
        if(nxt == cur)
            break;
        int nt = tm + dur[cur][nxt];
        if(nt > MAX_SLOT)
            break;
        p.route.push_back(nxt);
        tm = nt;
        cur = nxt;
        idx = (idx + 1) % (int)cycle.size();
    }

    p.duration = tm - offset;
    normalizePlane(p, dur);
    return p;
}

int main() {
    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;
    vector<Flight> sqFlights(M);
    for(int i = 0; i < M; ++i) {
        int a, b;
        string ss, tt;
        cin >> a >> ss >> b >> tt;
        --a;
        --b;
        sqFlights[i] = {a, b, parseTimeToSlot(ss), parseTimeToSlot(tt)};
    }

    int K;
    cin >> K;

    vector<vector<int>> dur(N, vector<int>(N, 0));
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j)
            if(i != j)
                dur[i][j] = calcDurationSlot(cities[i], cities[j]);
    }

    vector<vector<long double>> pairWeight(N, vector<long double>(N, 0.0L));
    double threshold = 0.25 * R;
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            double dx = double(cities[i].x) - double(cities[j].x);
            double dy = double(cities[i].y) - double(cities[j].y);
            double d = sqrt(dx * dx + dy * dy);
            if(d + 1e-12 >= threshold) {
                pairWeight[i][j] = (long double)cities[i].w * (long double)cities[j].w;
            }
        }
    }

    ScoreEvaluator evaluator(N);
    auto sqBest = evaluator.precomputeSqBest(sqFlights); // [k][src][dst]

    vector<DemandTerm> demands;
    demands.reserve(N * N);
    for(int src = 0; src < N; ++src) {
        for(int dst = 0; dst < N; ++dst) {
            if(pairWeight[src][dst] == 0.0L)
                continue;
            DemandTerm d;
            d.src = src;
            d.dst = dst;
            d.w = pairWeight[src][dst];
            for(int k = 0; k < TARGET_CNT; ++k)
                d.sq[k] = sqBest[k][src][dst];
            demands.push_back(d);
        }
    }

    vector<long double> cityScore(N, 0.0L);
    for(int i = 0; i < N; ++i) {
        long double s = (long double)cities[i].w * 1e6L;
        for(int j = 0; j < N; ++j)
            s += pairWeight[i][j] + pairWeight[j][i];
        cityScore[i] = max((long double)1.0, s);
    }

    vector<int> cityOrd(N);
    iota(cityOrd.begin(), cityOrd.end(), 0);
    sort(cityOrd.begin(), cityOrd.end(), [&](int a, int b) {
        return cityScore[a] > cityScore[b];
    });

    vector<PlanePlan> plans(K);
    vector<vector<int>> routes(K);
    vector<int> headCity(K), headTime(K), legCount(K, 0);
    vector<int> cityUse(N, 0);
    vector<vector<int>> edgeUse(N, vector<int>(N, 0));

    for(int p = 0; p < K; ++p) {
        int c = cityOrd[p % N];
        routes[p].push_back(c);
        headCity[p] = c;
        headTime[p] = MAX_SLOT;
        cityUse[c]++;
    }

    long double maxCityScore = 1.0L;
    for(int i = 0; i < N; ++i)
        maxCityScore = max(maxCityScore, cityScore[i]);
    long double pairScale = 1.0L;
    {
        long double sum = 0.0L;
        int cnt = 0;
        for(int i = 0; i < N; ++i)
            for(int j = 0; j < N; ++j)
                if(i != j && pairWeight[i][j] > 0.0L) {
                    sum += pairWeight[i][j];
                    cnt++;
                }
        if(cnt > 0)
            pairScale = max((long double)1.0, sum / (long double)cnt);
    }

    vector<Flight> currentFlights;
    vector<vector<vector<int>>> curLatest(TARGET_CNT, vector<vector<int>>(N, vector<int>(N, NEG_INF)));
    for(int k = 0; k < TARGET_CNT; ++k) {
        int target = TARGET_START + TARGET_STEP * k;
        auto byStart = evaluator.buildByStart(currentFlights, target);
        curLatest[k] = evaluator.latestMatrixForTarget(byStart, target);
    }
    long double totalDen = 0.0L;
    for(const auto &d : demands)
        totalDen += d.w;
    totalDen *= (long double)TARGET_CNT;
    long double currentCi = 0.0L;
    for(int k = 0; k < TARGET_CNT; ++k) {
        for(const auto &d : demands) {
            if(d.sq[k] < curLatest[k][d.src][d.dst])
                currentCi += d.w;
        }
    }
    double currentScore = (totalDen > 0.0L ? (double)(currentCi / totalDen) : 0.0);

    int maxLegPerPlane = 14;
    int maxTotalOps = K * maxLegPerPlane;
    for(int op = 0; op < maxTotalOps; ++op) {
        for(int k = 0; k < TARGET_CNT; ++k) {
            int target = TARGET_START + TARGET_STEP * k;
            auto byStart = evaluator.buildByStart(currentFlights, target);
            curLatest[k] = evaluator.latestMatrixForTarget(byStart, target);
        }
        currentCi = 0.0L;
        for(int k = 0; k < TARGET_CNT; ++k) {
            for(const auto &d : demands) {
                if(d.sq[k] < curLatest[k][d.src][d.dst])
                    currentCi += d.w;
            }
        }
        currentScore = (totalDen > 0.0L ? (double)(currentCi / totalDen) : 0.0);

        vector<tuple<long double, int, int, int, int>> ops; // gain, plane, from, dep, arr
        ops.reserve(K * N);

        for(int p = 0; p < K; ++p) {
            if(legCount[p] >= maxLegPerPlane)
                continue;
            int b = headCity[p];
            int arr = headTime[p];

            for(int a = 0; a < N; ++a) {
                if(a == b)
                    continue;
                int dep = arr - dur[a][b];
                if(dep < 0)
                    continue;

                long double local = 0.0L;
                long double base = pairWeight[a][b];
                if(base > 0.0L) {
                    for(int k = 0; k < TARGET_CNT; ++k) {
                        int target = TARGET_START + TARGET_STEP * k;
                        if(arr <= target && dep > sqBest[k][a][b])
                            local += base;
                    }
                }

                long double gain = local / pairScale;
                if(cityUse[a] == 0)
                    gain += 0.80L;
                if(cityUse[b] == 0)
                    gain += 0.20L;
                gain += 0.25L * (cityScore[a] / maxCityScore);
                gain += 0.05L * ((long double)dep / (long double)MAX_SLOT);
                gain -= 0.35L * (long double)edgeUse[a][b];
                gain -= 0.08L * (long double)cityUse[a];
                ops.emplace_back(gain, p, a, dep, arr);
            }
        }

        if(ops.empty())
            break;
        sort(ops.begin(), ops.end(), [&](const auto &x, const auto &y) {
            return get<0>(x) > get<0>(y);
        });

        int beam = min(50, (int)ops.size());
        double bestScore = currentScore;
        long double bestGain = get<0>(ops[0]);
        long double bestDeltaCi = 0.0L;
        int bestPlane = -1, bestFrom = -1, bestDep = -1, bestArr = -1;
        unordered_map<int, vector<int>> preCache;
        preCache.reserve((size_t)beam * 2);

        for(int i = 0; i < beam; ++i) {
            auto [hgain, p, a, dep, arr] = ops[i];
            int b = headCity[p];

            int key = a * (MAX_SLOT + 1) + dep;
            auto it = preCache.find(key);
            if(it == preCache.end()) {
                it = preCache.emplace(key, evaluator.latestToDstByDeadline(currentFlights, a, dep)).first;
            }
            const vector<int> &preToA = it->second;

            long double deltaCi = 0.0L;
            for(int k = 0; k < TARGET_CNT; ++k) {
                int target = TARGET_START + TARGET_STEP * k;
                if(target < arr)
                    continue; // flight cannot be used for this deadline
                for(const auto &d : demands) {
                    if(preToA[d.src] == NEG_INF)
                        continue; // cannot reach a by dep
                    if(curLatest[k][b][d.dst] < arr)
                        continue; // cannot continue from b after arr
                    int oldCi = curLatest[k][d.src][d.dst];
                    int newCi = max(oldCi, preToA[d.src]);
                    if(d.sq[k] < newCi && !(d.sq[k] < oldCi))
                        deltaCi += d.w;
                }
            }
            double s = (totalDen > 0.0L ? (double)((currentCi + deltaCi) / totalDen) : 0.0);
            if(s > bestScore || (s == bestScore && hgain > bestGain)) {
                bestScore = s;
                bestGain = hgain;
                bestDeltaCi = deltaCi;
                bestPlane = p;
                bestFrom = a;
                bestDep = dep;
                bestArr = arr;
            }
        }

        if(bestPlane < 0) {
            auto [hgain, p, a, dep, arr] = ops[0];
            if(hgain < 0.10L)
                break;
            bestPlane = p;
            bestFrom = a;
            bestDep = dep;
            bestArr = arr;
        } else if(bestScore < currentScore + 1e-15) {
            if(bestGain < 0.10L)
                break;
        }

        int b = headCity[bestPlane];
        routes[bestPlane].insert(routes[bestPlane].begin(), bestFrom);
        headCity[bestPlane] = bestFrom;
        headTime[bestPlane] = bestDep;
        legCount[bestPlane]++;
        cityUse[bestFrom]++;
        edgeUse[bestFrom][b]++;
        currentFlights.push_back({bestFrom, b, bestDep, bestArr});
        currentCi += bestDeltaCi;
        currentScore = (totalDen > 0.0L ? (double)(currentCi / totalDen) : 0.0);
    }

    for(int p = 0; p < K; ++p) {
        PlanePlan pl;
        pl.route = routes[p];
        pl.offset = headTime[p];
        normalizePlane(pl, dur);
        plans[p] = pl;
    }

    vector<Flight> finalFlights = flattenPlans(plans, dur);
    double finalScore = evaluator.score(finalFlights, demands);
    vector<int> flownCity(N, 0);
    for(const auto &f : finalFlights) {
        flownCity[f.a] = 1;
        flownCity[f.b] = 1;
    }

    for(int i = 0; i < K; ++i) {
        const auto &p = plans[i];
        cout << max(0, (int)p.route.size() - 1) << '\n';
        int tm = p.offset;
        for(int j = 1; j < (int)p.route.size(); ++j) {
            int a = p.route[j - 1], b = p.route[j];
            int nt = tm + dur[a][b];
            cout << (a + 1) << ' ' << slotToTime(tm) << ' ' << (b + 1) << ' ' << slotToTime(nt) << '\n';
            tm = nt;
        }
    }

    cerr << fixed << setprecision(12)
         << "score=" << finalScore
         << " unique_cities=" << count(flownCity.begin(), flownCity.end(), 1)
         << " flights=" << finalFlights.size() << '\n';

    return 0;
}