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

• 問題: No.5023 Airlines Optimization
• ユーザー: kurigen
• 提出日時: 2026-02-26 00:32:05
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 960 ms / 1,000 ms
• コード長: 18,769 bytes
• コンパイル時間: 6,558 ms
• コンパイル使用メモリ: 388,348 KB
• 実行使用メモリ: 7,844 KB
• スコア: 51,834,955
• 最終ジャッジ日時: 2026-02-26 00:33:55
• 合計ジャッジ時間: 108,519 ms
• ジャッジサーバーID （参考情報）: judge7 / judge2

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

ソースコード

// コンパイラ最適化
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

const int16_t INF = 30000;

// 都市情報
struct City {
    int16_t id;    // 都市ID
    int16_t x, y;  // 座標
    int32_t w;     // 人口
};

// フライト情報
struct Flight {
    int16_t start_time; // 出発時刻 (06:00からの経過分数)
    int16_t end_time;   // 到着時刻
    int8_t from;        // 出発都市ID
    int8_t to;          // 到着都市ID
    int8_t start_t;     // 評価関数用キャッシュ
    int8_t pad;         // パディング
    
    bool operator<(const Flight& o) const {
        return start_time > o.start_time; 
    }
};

// 1機の飛行機の1日のスケジュール
struct Schedule {
    Flight flights[50]; // 拡張サイズ
    int8_t count;       // 実際のフライト数
    int8_t pad[3];      // パディング
};

// 到達可能性履歴
struct HistoryEntry {
    int16_t time;
    uint64_t reach[24];
};

struct CityHistory {
    HistoryEntry entries[182];
    int count;
};

// ----- グローバル変数群 -----
int N, R, M, K;
City cities[50];

Flight sq_flights[400];       // スクエア航空のフライト情報
int sq_flights_count = 0;

int16_t req_time_tbl[50][50]; // 都市iからjへの所要時間
double weight_tbl[50][50];    // 都市iとjの人口の積
double TOTAL_WEIGHT = 0;      // シェア率の計算式の分母

// 距離条件(0.25R以上)を満たす目的地のbitマスク
uint64_t valid_to_mask[50];

// スクエア航空の最遅出発時刻
int16_t sq_late[50][24][50]; 
int8_t start_t_tbl[1500];

// 乱数生成器 (Xorshift32)
inline uint32_t xorshift32() {
    static uint32_t y = 2463534242;
    y ^= (y << 13);
    y ^= (y >> 17);
    y ^= (y << 5);
    return y;
}

// "HH:MM" を 00:00からの経過分数 に変換
int time_to_int(const string& s) {
    int h = stoi(s.substr(0, 2));
    int m = stoi(s.substr(3, 2));
    return h * 60 + m;
}

// 経過分数を "HH:MM" に変換
string int_to_time(int t) {
    int h = t / 60;
    int m = t % 60;
    stringstream ss;
    ss << setfill('0') << setw(2) << h << ":" << setfill('0') << setw(2) << m;
    return ss.str();
}

// ユークリッド距離
double calc_dist(int i, int j) {
    double dx = cities[i].x - cities[j].x;
    double dy = cities[i].y - cities[j].y;
    return sqrt(dx * dx + dy * dy);
}

// フライト所要時間
int16_t calc_req_time(int i, int j) {
    double d = calc_dist(i, j);
    double t = 60.0 * d / 800.0 + 40.0;
    return ceil(t / 5.0) * 5;
}

// 1機分の初期スケジュールを構築
void build_schedule(int8_t cur_city, int16_t cur_time, Schedule& sked, int8_t start_idx = 0) {
    sked.count = start_idx;
    
    int8_t cands[50];
    int8_t cands_count;
    
    while (cur_time < 1260 && sked.count < 49) { 
        cands_count = 0;
        for (int8_t i = 0; i < N; ++i) {
            if (i == cur_city) continue;
            if (cur_time + req_time_tbl[cur_city][i] <= 1260) {
                cands[cands_count++] = i;
            }
        }
        if (cands_count == 0) break;
        
        int8_t nxt = cands[xorshift32() % cands_count];
        int8_t cand2 = cands[xorshift32() % cands_count];
        if (cities[cand2].w > cities[nxt].w) nxt = cand2;

        int16_t req = req_time_tbl[cur_city][nxt];
        int16_t et = cur_time + req;
        
        Flight& f = sked.flights[sked.count++];
        f.from = cur_city;
        f.start_time = cur_time;
        f.to = nxt;
        f.end_time = et;
        f.start_t = start_t_tbl[et];
        
        cur_city = nxt;
        cur_time = et;
    }
}

// 全機体の評価関数
double evaluate_all(const Schedule* schedule) {
    static Flight all_f[1500]; 
    
    int counts[182] = {0};
    for (int k = 0; k < K; ++k) {
        for (int i = 0; i < schedule[k].count; ++i) {
            int idx = (schedule[k].flights[i].start_time - 360) / 5;
            counts[idx]++;
        }
    }
    
    int offsets[182];
    offsets[181] = 0;
    for (int i = 180; i >= 0; --i) {
        offsets[i] = offsets[i+1] + counts[i];
    }
    
    int all_f_count = offsets[0];
    for (int k = 0; k < K; ++k) {
        for (int i = 0; i < schedule[k].count; ++i) {
            const Flight& f = schedule[k].flights[i];
            int idx = (f.start_time - 360) / 5;
            all_f[offsets[idx+1]++] = f; 
        }
    }

    uint64_t reached_flags[50][24];
    memset(reached_flags, 0, sizeof(reached_flags));
    
    static CityHistory history[50];
    for(int i = 0; i < N; ++i) {
        history[i].count = 1;
        history[i].entries[0].time = INF;
        memset(history[i].entries[0].reach, 0, 192);
    }

    double v_ci = 0;
    
    for (int idx = 0; idx < all_f_count; ++idx) {
        const Flight& f = all_f[idx];
        int8_t i = f.from;
        int8_t k = f.to;
        int16_t s = f.start_time;
        int16_t e = f.end_time;
        int8_t st = f.start_t;
        
        const CityHistory& ch = history[k];
        int h_idx = ch.count - 1;
        while(ch.entries[h_idx].time < e) {
            h_idx--;
        }
        const uint64_t* base_reach = ch.entries[h_idx].reach;
        
        CityHistory& ih = history[i];
        bool same_time = (ih.entries[ih.count - 1].time == s);
        int c = same_time ? ih.count - 1 : ih.count;
        
        if (!same_time) {
            ih.entries[c].time = s;
            for(int t = 0; t < st; ++t) {
                ih.entries[c].reach[t] = ih.entries[c-1].reach[t];
            }
        }
        
        for(int t = st; t < 21; ++t) {
            uint64_t rt = base_reach[t] | (1ULL << k);
            
            if (same_time) {
                ih.entries[c].reach[t] |= rt;
            } else {
                ih.entries[c].reach[t] = ih.entries[c-1].reach[t] | rt;
            }
            
            uint64_t new_reach = rt & ~reached_flags[i][t];
            
            if (new_reach) {
                reached_flags[i][t] |= new_reach; 
                uint64_t temp = new_reach & valid_to_mask[i];
                const int16_t* sq_ptr = sq_late[i][t];
                
                while(temp) {
                    int j = __builtin_ctzll(temp);
                    temp &= temp - 1;
                    if (s > sq_ptr[j]) {
                        v_ci += weight_tbl[i][j];
                    }
                }
            }
        }
        if (!same_time) ih.count++;
    }
    
    return v_ci / TOTAL_WEIGHT; 
}

// 差分マージDP
double evaluate_k(const Schedule& sked, const Flight* other_f, int other_f_count) {
    uint64_t reached_flags[50][24];
    memset(reached_flags, 0, sizeof(reached_flags));
    
    static CityHistory history[50];
    for(int i = 0; i < N; ++i) {
        history[i].count = 1;
        history[i].entries[0].time = INF;
        memset(history[i].entries[0].reach, 0, 192);
    }

    double v_ci = 0;
    
    int idx_other = 0;
    int idx_sked = sked.count - 1;

    int total_flights = other_f_count + sked.count;
    
    for (int step = 0; step < total_flights; ++step) {
        Flight f;
        if (idx_other < other_f_count && idx_sked >= 0) {
            if (other_f[idx_other].start_time > sked.flights[idx_sked].start_time) {
                f = other_f[idx_other++];
            } else {
                f = sked.flights[idx_sked--];
            }
        } else if (idx_other < other_f_count) {
            f = other_f[idx_other++];
        } else {
            f = sked.flights[idx_sked--];
        }
        
        int8_t i = f.from;
        int8_t to_k = f.to;
        int16_t s = f.start_time;
        int16_t e = f.end_time;
        int8_t st = f.start_t;
        
        const CityHistory& ch = history[to_k];
        int h_idx = ch.count - 1;
        while(ch.entries[h_idx].time < e) {
            h_idx--;
        }
        const uint64_t* base_reach = ch.entries[h_idx].reach;
        
        CityHistory& ih = history[i];
        bool same_time = (ih.entries[ih.count - 1].time == s);
        int c = same_time ? ih.count - 1 : ih.count;
        
        if (!same_time) {
            ih.entries[c].time = s;
            for(int t = 0; t < st; ++t) {
                ih.entries[c].reach[t] = ih.entries[c-1].reach[t];
            }
        }
        
        for(int t = st; t < 21; ++t) {
            uint64_t rt = base_reach[t] | (1ULL << to_k);
            
            if (same_time) {
                ih.entries[c].reach[t] |= rt;
            } else {
                ih.entries[c].reach[t] = ih.entries[c-1].reach[t] | rt;
            }
            
            uint64_t new_reach = rt & ~reached_flags[i][t];
            
            if (new_reach) {
                reached_flags[i][t] |= new_reach; 
                
                uint64_t temp = new_reach & valid_to_mask[i];
                const int16_t* sq_ptr = sq_late[i][t];
                
                while(temp) {
                    int j = __builtin_ctzll(temp);
                    temp &= temp - 1;
                    
                    if (s > sq_ptr[j]) {
                        v_ci += weight_tbl[i][j];
                    }
                }
            }
        }
        if (!same_time) ih.count++;
    }
    
    return v_ci / TOTAL_WEIGHT; 
}


int main() {
    auto start_time_clock = chrono::high_resolution_clock::now();

    for(int et = 0; et <= 1440; ++et) {
        start_t_tbl[et] = max(0, (et - 660 + 29) / 30);
    }

    if (!(cin >> N >> R)) return 0;
    
    for (int i = 0; i < N; ++i) {
        cities[i].id = i;
        cin >> cities[i].x >> cities[i].y >> cities[i].w;
        valid_to_mask[i] = 0;
    }
    
    cin >> M;
    for (int i = 0; i < M; ++i) {
        int a, b;
        string s, t;
        cin >> a >> s >> b >> t;
        int16_t st_int = time_to_int(s);
        int16_t et_int = time_to_int(t);
        sq_flights[sq_flights_count++] = {st_int, et_int, (int8_t)(a - 1), (int8_t)(b - 1), start_t_tbl[et_int], 0};
    }
    cin >> K;

    double R_thres_sq = (0.25 * R) * (0.25 * R); 
    TOTAL_WEIGHT = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            req_time_tbl[i][j] = calc_req_time(i, j);
            weight_tbl[i][j] = (double)cities[i].w * cities[j].w;
            
            double dx = cities[i].x - cities[j].x;
            double dy = cities[i].y - cities[j].y;
            if (i != j && (dx*dx + dy*dy) >= R_thres_sq) {
                valid_to_mask[i] |= (1ULL << j);
                TOTAL_WEIGHT += weight_tbl[i][j] * 21;
            }
        }
    }

    sort(sq_flights, sq_flights + sq_flights_count);
    int16_t sq_late_temp[50][50];
    
    for (int t_idx = 0; t_idx < 21; ++t_idx) {
        int T = 660 + t_idx * 30;
        for (int j = 0; j < N; ++j) {
            for (int i = 0; i < N; ++i) sq_late_temp[j][i] = -1;
            sq_late_temp[j][j] = INF;
            
            for (int i = 0; i < sq_flights_count; ++i) {
                const auto& f = sq_flights[i];
                if (f.end_time > T) continue;
                if (sq_late_temp[j][f.to] >= f.end_time) {
                    if (f.start_time > sq_late_temp[j][f.from]) {
                        sq_late_temp[j][f.from] = f.start_time;
                    }
                }
            }
            sq_late_temp[j][j] = -1; 
            
            for (int i = 0; i < N; ++i) {
                sq_late[i][t_idx][j] = sq_late_temp[j][i];
            }
        }
    }

    int8_t sorted_cities[50];
    for (int8_t i = 0; i < N; ++i) sorted_cities[i] = i;
    sort(sorted_cities, sorted_cities + N, [](int8_t a, int8_t b) {
        return cities[a].w > cities[b].w;
    });

    Schedule current_schedule[25];
    int8_t initial_cities[25];
    for (int k = 0; k < K; ++k) {
        initial_cities[k] = sorted_cities[k % N]; 
        build_schedule(initial_cities[k], 360, current_schedule[k]); 
    }

    double current_score = evaluate_all(current_schedule);
    double best_score = current_score;                 
    Schedule best_schedule[25];                        
    memcpy(best_schedule, current_schedule, sizeof(current_schedule));

    double MAX_TIME = 0.95;
    int iter = 0;
    
    // 1機ずつ順番に集中して焼きなます
    for (int k = 0; k < K; ++k) {
        double start_temp = 0.05;
        double end_temp = 0.00001;
        double temp = start_temp;
        
        double target_time = MAX_TIME * (k + 1) / K;
        double start_time_for_k = MAX_TIME * k / K;

        Flight other_f[1500];
        int counts[182] = {0};
        for (int i = 0; i < K; ++i) {
            if (i == k) continue;
            for (int j = 0; j < current_schedule[i].count; ++j) {
                int idx = (current_schedule[i].flights[j].start_time - 360) / 5;
                counts[idx]++;
            }
        }
        int offsets[182];
        offsets[181] = 0;
        for (int i = 180; i >= 0; --i) {
            offsets[i] = offsets[i+1] + counts[i];
        }
        int other_f_count = offsets[0];
        for (int i = 0; i < K; ++i) {
            if (i == k) continue;
            for (int j = 0; j < current_schedule[i].count; ++j) {
                const Flight& f = current_schedule[i].flights[j];
                int idx = (f.start_time - 360) / 5;
                other_f[offsets[idx+1]++] = f; 
            }
        }
        
        current_score = evaluate_k(current_schedule[k], other_f, other_f_count);

        while (true) {
            if ((iter & 63) == 0) {
                auto now = chrono::high_resolution_clock::now();
                double elapsed = chrono::duration<double>(now - start_time_clock).count();
                
                if (elapsed > target_time) break;
                
                double progress = (elapsed - start_time_for_k) / (target_time - start_time_for_k);
                progress = max(0.0, min(1.0, progress));
                temp = start_temp * pow(end_temp / start_temp, progress);
            }
            iter++;
            
            Schedule backup_sked = current_schedule[k]; 
            
            // フライト配列から都市の通過列を抽出し、そのうち1箇所だけをランダムに変更
            int num_v = backup_sked.count + 1; // 頂点(都市)の数
            int idx = xorshift32() % num_v;    // 変更する頂点のインデックス
            
            int old_city = (idx == 0) ? backup_sked.flights[0].from : backup_sked.flights[idx - 1].to;
            
            int X;
            while(true) {
                X = xorshift32() % N;
                if (X == old_city) continue;
                if (idx > 0) {
                    int prev = (idx == 1) ? backup_sked.flights[0].from : backup_sked.flights[idx - 2].to;
                    if (X == prev) continue;
                }
                if (idx < num_v - 1) {
                    int next = backup_sked.flights[idx].to;
                    if (X == next) continue;
                }
                break;
            }
            
            // 現在の頂点列を構築し、変更を反映
            int8_t V[60];
            V[0] = backup_sked.flights[0].from;
            for (int i = 0; i < backup_sked.count; ++i) {
                V[i+1] = backup_sked.flights[i].to;
            }
            V[idx] = X;
            
            // 差分更新
            int start_f = max(0, idx - 1);
            int16_t cur_time = (start_f == 0) ? 360 : backup_sked.flights[start_f - 1].end_time;
            int8_t cur_city = V[start_f];
            
            current_schedule[k].count = start_f; 
            
            // 以降のスケジュールを再構築
            for (int i = start_f + 1; i < num_v; ++i) {
                int8_t nxt = V[i];
                int16_t req = req_time_tbl[cur_city][nxt];
                if (cur_time + req > 1260) {
                    break;
                }
                Flight& f = current_schedule[k].flights[current_schedule[k].count++];
                f.from = cur_city;
                f.to = nxt;
                f.start_time = cur_time;
                f.end_time = cur_time + req;
                f.start_t = start_t_tbl[f.end_time];
                
                cur_time = f.end_time;
                cur_city = nxt;
            }
            
            // 余白修復
            while (cur_time < 1260 && current_schedule[k].count < 49) {
                int8_t cands[50];
                int8_t cands_count = 0;
                for (int8_t i = 0; i < N; ++i) {
                    if (i == cur_city) continue;
                    if (cur_time + req_time_tbl[cur_city][i] <= 1260) {
                        cands[cands_count++] = i;
                    }
                }
                if (cands_count == 0) break;
                
                int8_t nxt = cands[xorshift32() % cands_count];
                int8_t cand2 = cands[xorshift32() % cands_count];
                if (cities[cand2].w > cities[nxt].w) nxt = cand2;

                int16_t req = req_time_tbl[cur_city][nxt];
                
                Flight& f = current_schedule[k].flights[current_schedule[k].count++];
                f.from = cur_city;
                f.to = nxt;
                f.start_time = cur_time;
                f.end_time = cur_time + req;
                f.start_t = start_t_tbl[f.end_time];
                
                cur_time = f.end_time;
                cur_city = nxt;
            }
            
            // 評価
            double new_score = evaluate_k(current_schedule[k], other_f, other_f_count);
            
            // 受理判定
            if (new_score > current_score || 
                exp((new_score - current_score) / temp) > (double)(xorshift32() % 10000) / 10000.0) {
                
                current_score = new_score;
                
                if (new_score > best_score) {
                    best_score = new_score;
                    memcpy(best_schedule, current_schedule, sizeof(current_schedule));
                }
            } else {
                current_schedule[k] = backup_sked;
            }
        }
    }

    // 出力
    for (int k = 0; k < K; ++k) {
        cout << (int)best_schedule[k].count << "\n";
        for (int i = 0; i < best_schedule[k].count; ++i) {
            const auto& f = best_schedule[k].flights[i];
            cout << f.from + 1 << " " 
                 << int_to_time(f.start_time) << " " 
                 << f.to + 1 << " " 
                 << int_to_time(f.end_time) << "\n";
        }
    }

    // ログ
    cerr << "Iterations: " << iter << "\n";

    return 0;
}