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

• 問題: No.5023 Airlines Optimization
• ユーザー: Moegi
• 提出日時: 2026-02-25 22:27:45
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 936 ms / 1,000 ms
• コード長: 10,917 bytes
• コンパイル時間: 4,823 ms
• コンパイル使用メモリ: 369,596 KB
• 実行使用メモリ: 7,848 KB
• スコア: 40,439,393
• 最終ジャッジ日時: 2026-02-25 22:31:23
• 合計ジャッジ時間: 103,965 ms
• ジャッジサーバーID （参考情報）: judge6 / judge2

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

ソースコード

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

struct City { long long x, y, w; };

static int to_minutes(const string& hhmm){
    int h = stoi(hhmm.substr(0,2));
    int m = stoi(hhmm.substr(3,2));
    return h*60 + m;
}
static string to_hhmm(int minutes){
    int h = minutes/60, m = minutes%60;
    ostringstream oss;
    oss << setw(2) << setfill('0') << h << ":" << setw(2) << setfill('0') << m;
    return oss.str();
}

// duration = ceil( (60*d/800 + 40) /5 )*5
static int flight_duration_5min_ceil(long long x1,long long y1,long long x2,long long y2){
    long double dx=(long double)x1-x2, dy=(long double)y1-y2;
    long double dist = sqrtl(dx*dx+dy*dy);
    long double raw = 60.0L*dist/800.0L + 40.0L;
    long double units = raw/5.0L;
    long long k = (long long)ceill(units - 1e-12L);
    return (int)(k*5);
}

struct Flight {
    uint8_t u, v;
    int16_t s, t; // minutes
};

struct XorShift {
    uint64_t x=88172645463325252ULL;
    uint32_t next_u32(){
        x ^= x<<7;
        x ^= x>>9;
        return (uint32_t)x;
    }
    int next_int(int lo,int hi){ // inclusive
        return lo + (int)(next_u32() % (uint32_t)(hi-lo+1));
    }
};

static const int START = 6*60;
static const int END   = 21*60;

// 最新出発時刻 L[origin] を、destへdeadlineまでに到着できる範囲で求める（-1=到達不可）
static inline void latest_departure_to_dest(
    int N,
    const vector<Flight>& flights,
    const vector<vector<int>>& in_edges,
    int dest, int deadline,
    int16_t* L // size N+1
){
    for(int i=1;i<=N;i++) L[i] = -1;
    static uint8_t inq[64];
    for(int i=1;i<=N;i++) inq[i]=0;

    // destは deadline までに居ればOK
    L[dest] = (int16_t)deadline;
    int qbuf[64]; int qh=0, qt=0;
    qbuf[qt++] = dest; inq[dest]=1;

    while(qh<qt){
        int v = qbuf[qh++]; inq[v]=0;
        int16_t Lv = L[v];
        // v への流入便
        for(int idx: in_edges[v]){
            const Flight &f = flights[idx]; // f.u -> f.v(=v)
            if(f.t <= Lv){
                if(f.s > L[f.u]){
                    L[f.u] = f.s;
                    if(!inq[f.u]){
                        inq[f.u]=1;
                        qbuf[qt++] = f.u;
                    }
                }
            }
        }
    }
}

struct Plane {
    uint8_t dest;   // 2..N
    int16_t phase;  // 0..(something), multiple of 5
    int16_t slack;  // >=0, multiple of 5
};

static inline void build_circle_flights(
    int N,
    const vector<City>& c,
    const vector<vector<int16_t>>& dur, // [i][j]
    const vector<Plane>& planes,
    int hub,
    vector<Flight>& out_flights,
    vector<vector<int>>& in_edges
){
    out_flights.clear();
    out_flights.reserve(600);
    for(int i=1;i<=N;i++) in_edges[i].clear();

    for(const auto& p: planes){
        int d = dur[hub][p.dest];
        int t = START + p.phase;
        int cur = hub;
        while(true){
            int nxt = (cur==hub ? (int)p.dest : hub);
            int s = t;
            int a = t + d;
            if(a > END) break;

            int idx = (int)out_flights.size();
            out_flights.push_back(Flight{(uint8_t)cur,(uint8_t)nxt,(int16_t)s,(int16_t)a});
            in_edges[nxt].push_back(idx);

            t = a;
            cur = nxt;
            if(cur == hub){
                t += p.slack;
                if(t > END) break;
            }
        }
    }
}

// Ltable[k][dest][orig] を詰める（k=0..20のdeadline）
static inline void compute_L_table(
    int N,
    const vector<Flight>& flights,
    const vector<vector<int>>& in_edges,
    const vector<int>& deadlines,
    vector<int16_t>& Ltable // size = K * (N+1)*(N+1)
){
    int K = (int)deadlines.size();
    auto idx = [&](int k,int dest,int orig){
        return (k*(N+1) + dest)*(N+1) + orig;
    };
    static int16_t Ltmp[64];

    for(int k=0;k<K;k++){
        int dl = deadlines[k];
        for(int dest=1; dest<=N; dest++){
            latest_departure_to_dest(N, flights, in_edges, dest, dl, Ltmp);
            for(int orig=1; orig<=N; orig++){
                Ltable[idx(k,dest,orig)] = Ltmp[orig];
            }
        }
    }
}

struct PairInfo {
    uint8_t i, j;
    __int128 wij;
};

static inline long double evaluate_score(
    int N,
    const vector<int>& deadlines,
    const vector<PairInfo>& pairs,
    const vector<int16_t>& Lsq,
    const vector<int16_t>& Lci
){
    int Kt = (int)deadlines.size();
    auto idx = [&](const vector<int16_t>& T, int k,int dest,int orig)->int16_t{
        return T[(k*(N+1)+dest)*(N+1)+orig];
    };

    __int128 vci = 0, vsq = 0;
    for(const auto& p: pairs){
        int i=p.i, j=p.j;
        __int128 w = p.wij;
        for(int k=0;k<Kt;k++){
            int16_t ssq = idx(Lsq,k,j,i);
            int16_t sci = idx(Lci,k,j,i);
            if(ssq < sci) vci += w;
            else          vsq += w;
        }
    }
    long double num = (long double)( (long double)vci );
    long double den = (long double)( (long double)(vci+vsq) );
    if(den <= 0) return 0.0L;
    return num/den;
}

static inline vector<tuple<int,int,int,int>> make_plane_schedule(
    const vector<City>& c,
    const vector<vector<int16_t>>& dur,
    int hub,
    const Plane& p
){
    vector<tuple<int,int,int,int>> flights;
    int d = dur[hub][p.dest];
    int t = START + p.phase;
    int cur = hub;
    while(true){
        int nxt = (cur==hub ? (int)p.dest : hub);
        int s = t, a = t + d;
        if(a > END) break;
        flights.emplace_back(cur,s,nxt,a);
        t = a; cur = nxt;
        if(cur == hub){
            t += p.slack;
            if(t > END) break;
        }
    }
    return flights;
}

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

    int N; long long R;
    cin >> N >> R;
    vector<City> c(N+1);
    for(int i=1;i<=N;i++) cin >> c[i].x >> c[i].y >> c[i].w;

    int M; cin >> M;
    vector<Flight> sq_flights; sq_flights.reserve(M);
    vector<vector<int>> sq_in(N+1);
    for(int i=0;i<M;i++){
        int a,b; string s,t;
        cin >> a >> s >> b >> t;
        int sm = to_minutes(s);
        int tm = to_minutes(t);
        int idx = (int)sq_flights.size();
        sq_flights.push_back(Flight{(uint8_t)a,(uint8_t)b,(int16_t)sm,(int16_t)tm});
        sq_in[b].push_back(idx);
    }

    int K; cin >> K;

    // deadlines: 11:00,11:30,...,21:00  (21個)
    vector<int> deadlines;
    for(int t=11*60; t<=21*60; t+=30) deadlines.push_back(t);

    // 距離>=0.25R の (i,j) ペア列挙
    long long thr2 = (R*R)/16; // (0.25R)^2
    vector<PairInfo> pairs;
    pairs.reserve(N*N);
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            long long dx = c[i].x - c[j].x;
            long long dy = c[i].y - c[j].y;
            long long d2 = dx*dx + dy*dy;
            if(d2 >= thr2){
                __int128 w = (__int128)c[i].w * (__int128)c[j].w;
                pairs.push_back(PairInfo{(uint8_t)i,(uint8_t)j,w});
            }
        }
    }

    // 速度用：dur行列（circle側生成で使用）
    vector<vector<int16_t>> dur(N+1, vector<int16_t>(N+1,0));
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(i==j) continue;
            dur[i][j] = (int16_t)flight_duration_5min_ceil(c[i].x,c[i].y,c[j].x,c[j].y);
        }
    }

    // SquareのLtableを事前計算
    int Kt = (int)deadlines.size();
    vector<int16_t> Lsq((size_t)Kt*(N+1)*(N+1));
    compute_L_table(N, sq_flights, sq_in, deadlines, Lsq);

    // ===== 初期解（最初の強いやつ）=====
    int hub = 1; // 「最初の」＝人口最大が1番
    // 行き先候補：人口上位から（hub除外）
    vector<int> pool;
    for(int v=1; v<=N; v++) if(v!=hub) pool.push_back(v);
    int POOL = min((int)pool.size(), 28); // 探索範囲を絞る(強い都市優先)
    pool.resize(POOL);

    vector<Plane> cur(K);
    for(int p=0;p<K;p++){
        int dest = pool[p % POOL];
        cur[p] = Plane{(uint8_t)dest, 0, 0}; // phase=0 slack=0
    }

    vector<Flight> ci_flights;
    vector<vector<int>> ci_in(N+1);
    vector<int16_t> Lci((size_t)Kt*(N+1)*(N+1));

    auto eval = [&](const vector<Plane>& planes)->long double{
        build_circle_flights(N, c, dur, planes, hub, ci_flights, ci_in);
        compute_L_table(N, ci_flights, ci_in, deadlines, Lci);
        return evaluate_score(N, deadlines, pairs, Lsq, Lci);
    };

    long double curS = eval(cur);
    vector<Plane> best = cur;
    long double bestS = curS;

    // ===== 山登り（1秒制限内）=====
    XorShift rng;
    auto t0 = chrono::steady_clock::now();
    const double TL = 0.93; // 安全マージン

    // 近傍操作
    auto clamp_phase = [&](int dest, int ph)->int{
        // 5分刻み。day開始近辺の位相だけ使う（0..55）で十分刺さることが多い
        ph = (ph/5)*5;
        ph = max(0, min(55, ph));
        return ph;
    };

    int it = 0;
    while(true){
        it++;
        auto now = chrono::steady_clock::now();
        double sec = chrono::duration<double>(now - t0).count();
        if(sec >= TL) break;

        int type = rng.next_int(0, 9); // 0..9
        int p = rng.next_int(0, K-1);

        // backup
        Plane oldp = cur[p];
        int q = -1;
        Plane oldq;

        if(type <= 3){
            // dest変更
            int dest = pool[rng.next_int(0, POOL-1)];
            if(dest == hub) dest = pool[0];
            cur[p].dest = (uint8_t)dest;
            cur[p].phase = (int16_t)clamp_phase(dest, cur[p].phase);
        } else if(type <= 6){
            // phase変更
            int dest = cur[p].dest;
            int ph = 5 * rng.next_int(0, 11); // 0..55
            cur[p].phase = (int16_t)clamp_phase(dest, ph);
        } else if(type == 7 || type == 8){
            // slack変更（ハブ滞在。0が最強だったら自然に0へ戻る）
            int sl = 5 * rng.next_int(0, 12); // 0..60
            cur[p].slack = (int16_t)sl;
        } else {
            // swap dest
            q = rng.next_int(0, K-1);
            oldq = cur[q];
            swap(cur[p].dest, cur[q].dest);
            cur[p].phase = (int16_t)clamp_phase(cur[p].dest, cur[p].phase);
            cur[q].phase = (int16_t)clamp_phase(cur[q].dest, cur[q].phase);
        }

        long double newS = eval(cur);
        if(newS >= curS){
            curS = newS;
            if(newS > bestS){
                bestS = newS;
                best = cur;
            }
        } else {
            // revert
            cur[p] = oldp;
            if(q != -1) cur[q] = oldq;
        }
    }

    // ===== best を出力 =====
    for(int p=0;p<K;p++){
        auto fl = make_plane_schedule(c, dur, hub, best[p]);
        cout << fl.size() << "\n";
        for(auto &e: fl){
            int a,s,b,t;
            tie(a,s,b,t) = e;
            cout << a << " " << to_hhmm(s) << " " << b << " " << to_hhmm(t) << "\n";
        }
    }

    return 0;
}