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

• 問題: No.5023 Airlines Optimization
• ユーザー: kurigen
• 提出日時: 2026-02-25 23:54:06
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 960 ms / 1,000 ms
• コード長: 16,163 bytes
• コンパイル時間: 5,580 ms
• コンパイル使用メモリ: 383,132 KB
• 実行使用メモリ: 7,848 KB
• スコア: 49,773,636
• 最終ジャッジ日時: 2026-02-25 23:56:00
• 合計ジャッジ時間: 107,218 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
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;
        
        // ランダムに2つの都市を選び、人口が多い方を目的地として採用
        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(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];
            }
        }
        
        // DPと勝敗判定
        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; 
}

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

    // 入力
    cin >> N >> R;
    
    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;

    // 前計算 (距離・人口重み・bitマスク)
    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;
            }
        }
    }

    // 前計算 (スクエア航空のDP)
    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(current_schedule);
    double best_score = current_score;                 
    Schedule best_schedule[25];                        
    memcpy(best_schedule, current_schedule, sizeof(current_schedule));

    // 焼きなまし法パラメータ
    double MAX_TIME = 0.95;
    double start_temp = 0.05;
    double end_temp = 0.00001;
    double temp = start_temp;

    // 焼きなまし実行
    int iter = 0;
    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 > MAX_TIME) break;
            
            // 温度更新
            double progress = elapsed / MAX_TIME;
            temp = start_temp * pow(end_temp / start_temp, progress);
        }
        iter++;
        
        // 1. 変更する飛行機をランダムに選定
        int k = xorshift32() % K;
        Schedule backup_sked = current_schedule[k]; 
        
        // 2. 近傍操作
        int num_f = current_schedule[k].count;
        int type = xorshift32() % 100;
        
        bool valid_move = true;

        if (num_f == 0 || type < 5) { 
            // 5%: 完全再構築
            int8_t new_start = sorted_cities[xorshift32() % 10]; 
            build_schedule(new_start, 360, current_schedule[k], 0);
            
        } else if (type < 50) {
            // 45%: 中継都市変更
            if (num_f >= 2) {
                int drop_idx = xorshift32() % (num_f - 1);
                int cityA = current_schedule[k].flights[drop_idx].from;
                int cityC = current_schedule[k].flights[drop_idx + 1].to;
                int stA   = current_schedule[k].flights[drop_idx].start_time;
                
                int X = xorshift32() % N; 
                if (X != cityA && X != cityC) {
                    int req1 = req_time_tbl[cityA][X];
                    int req2 = req_time_tbl[X][cityC];
                    
                    if (stA + req1 > 1260) {
                        current_schedule[k].count = drop_idx;
                    } else if (stA + req1 + req2 > 1260) {
                        current_schedule[k].flights[drop_idx].to = X;
                        current_schedule[k].flights[drop_idx].end_time = stA + req1;
                        current_schedule[k].flights[drop_idx].start_t = start_t_tbl[stA + req1];
                        current_schedule[k].count = drop_idx + 1;
                    } else {
                        int old_end = current_schedule[k].flights[drop_idx + 1].end_time;
                        
                        current_schedule[k].flights[drop_idx].to = X;
                        current_schedule[k].flights[drop_idx].end_time = stA + req1;
                        current_schedule[k].flights[drop_idx].start_t = start_t_tbl[stA + req1];
                        
                        current_schedule[k].flights[drop_idx+1].from = X;
                        current_schedule[k].flights[drop_idx+1].start_time = stA + req1; 
                        current_schedule[k].flights[drop_idx+1].end_time = stA + req1 + req2;
                        current_schedule[k].flights[drop_idx+1].start_t = start_t_tbl[stA + req1 + req2];
                        
                        int dt = current_schedule[k].flights[drop_idx+1].end_time - old_end;
                        for (int i = drop_idx + 2; i < num_f; ++i) {
                            current_schedule[k].flights[i].start_time += dt;
                            current_schedule[k].flights[i].end_time += dt;
                            if (current_schedule[k].flights[i].end_time > 1260) {
                                current_schedule[k].count = i; 
                                break;
                            }
                            current_schedule[k].flights[i].start_t = start_t_tbl[current_schedule[k].flights[i].end_time];
                        }
                    }
                } else {
                    valid_move = false;
                }
            } else {
                valid_move = false;
            }
            
        } else {
            // 50%: 部分再構築
            int drop_idx = xorshift32() % num_f;
            int8_t restart_city = (drop_idx == 0) ? backup_sked.flights[0].from : backup_sked.flights[drop_idx - 1].to;
            int16_t restart_time = (drop_idx == 0) ? 360 : backup_sked.flights[drop_idx - 1].end_time;
            
            build_schedule(restart_city, restart_time, current_schedule[k], drop_idx);
        }
        
        if (!valid_move) {
            current_schedule[k] = backup_sked;
            continue;
        }

        // 余白修復
        if (current_schedule[k].count == 0) {
             int8_t new_start = sorted_cities[xorshift32() % 10]; 
             build_schedule(new_start, 360, current_schedule[k], 0);
        } else if (current_schedule[k].flights[current_schedule[k].count - 1].end_time <= 1260 - 45) {
             build_schedule(current_schedule[k].flights[current_schedule[k].count - 1].to, 
                           current_schedule[k].flights[current_schedule[k].count - 1].end_time, 
                           current_schedule[k], current_schedule[k].count);
        }
        
        // 3. 評価
        double new_score = evaluate(current_schedule);
        
        // 4. 受理判定
        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;
}