#1149430 (C++17) No.5023 Airlines Optimization

• 問題: No.5023 Airlines Optimization
• ユーザー: twins_fuyu
• 提出日時: 2026-02-25 23:57:48
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 146 ms / 1,000 ms
• コード長: 9,995 bytes
• コンパイル時間: 4,786 ms
• コンパイル使用メモリ: 389,404 KB
• 実行使用メモリ: 7,848 KB
• スコア: 39,656,609
• 最終ジャッジ日時: 2026-02-25 23:58:28
• 合計ジャッジ時間: 19,411 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

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

ソースコード

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "immintrin.h"
using namespace std;
#define rep1(a) for (int _ = 0; _ < (a); ++_)
#define rep2(i, a) for (int i = 0; i < (a); ++i)
#define rep3(i, a, b) for (int i = a; i < (b); ++i)
#define rrep1(a) for (int i = (a) - 1; i >= 0; --i)
#define rrep2(i, a) for (int i = (a) - 1; i >= 0; --i)
#define rrep3(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define overload3(a, b, c, d, ...) d
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) overload3(__VA_ARGS__, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define in(i, vec) for (auto i : (vec))
template <class T>
using pqueue = priority_queue<T, vector<T>>; // 大きい順
template <class T>
using pqueue_g = priority_queue<T, vector<T>, greater<T>>; // 小さい順

namespace library
{
    class xorshift128plus
    {
    private:
        uint64_t s[2];

    public:
        using result_type = uint64_t;

        xorshift128plus(uint64_t seed = 1)
        {
            seed_gen(seed);
        }

        void seed(uint64_t seed_val)
        {
            seed_gen(seed_val);
        }

        static constexpr result_type min()
        {
            return std::numeric_limits<result_type>::min();
        }

        static constexpr result_type max()
        {
            return std::numeric_limits<result_type>::max();
        }

        result_type operator()()
        {
            uint64_t s1 = s[0];
            uint64_t s0 = s[1];
            s[0] = s0;
            s1 ^= s1 << 23;
            s[1] = s1 ^ s0 ^ (s1 >> 17) ^ (s0 >> 26);
            return s[1] + s0;
        }

    private:
        void seed_gen(uint64_t seed_val)
        {
            // SplitMix64 で状態2個を初期化
            s[0] = splitmix64(seed_val);
            s[1] = splitmix64(s[0]);
        }

        static uint64_t splitmix64(uint64_t &x)
        {
            x += 0x9E3779B97F4A7C15ULL;
            uint64_t z = x;
            z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9ULL;
            z = (z ^ (z >> 27)) * 0x94D049BB133111EBULL;
            return z ^ (z >> 31);
        }
    };

    struct Timer
    {
        chrono::steady_clock::time_point start;
        Timer() : start(chrono::steady_clock::now()) {}
        double elapse()
        {
            return chrono::duration<double>(chrono::steady_clock::now() - start).count();
        }
        bool over(double t)
        {
            return elapse() > t;
        }
        bool operator()(double t)
        {
            return elapse() < t;
        }
    };

    void fast_io()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }

    uint64_t exp_table[2001];

    bool init_exp_table(){
        for(int i=0;i<=2000;++i){
            exp_table[i]=numeric_limits<uint64_t>::max()*exp(double(-i)/100.0);
        }
        return true;
    }
    bool exp_table_initialized = init_exp_table();

    uint64_t sa_exp(double diff, double temperature){
        if(temperature==0) return 0;
        else if (diff>=0) return numeric_limits<uint64_t>::max();
        int index = int(-diff * 100.0 / temperature);
        if(index>2000) return 0;
        return exp_table[index];
    }

} // namespace library

uniform_real_distribution<double> rnd(0.0, 1.0);
normal_distribution<double> randn(0.0, 1.0);
library::xorshift128plus rng(12345);
library::Timer timer;
double TL = 1.9;

constexpr int N = 47;
constexpr int M = 400;
constexpr int R = 1000;
long long W[N];
int DIST[N][N];
bool near[N][N];

struct QueryResult{
    int result[N][N][21];
    QueryResult(){
        rep(i,N)rep(j,N)rep(k,21)result[i][j][k] = -1;
    }
};

struct State{
    vector<tuple<int,int,int>> G[N]; // goal -> (start, start_time, goal_time)

    void sort_g(){
        rep(i,N){
            sort(G[i].begin(), G[i].end(), [](const auto& a, const auto& b){
                return get<2>(a) < get<2>(b);
            });
        }
    }

    void query_one(int goal, int goal_time, QueryResult& res){
        // 逆順でDijkstra
        bool vis[N] = {};
        pqueue<tuple<int,int>> pq; // (time, node)
        for(auto [prv, st, gt]:G[goal]){
            if(gt > goal_time) continue;
            pq.emplace(st, prv);
        }
        while (!pq.empty()){
            auto [cur_time, node] = pq.top(); pq.pop();
            if(vis[node]) continue;
            vis[node] = true;
            res.result[node][goal][(goal_time - 300) / 30] = cur_time;
            for(auto [prv, st, gt]:G[node]){
                if(gt > cur_time) continue;
                if(vis[prv]) continue;
                pq.emplace(st, prv);
            }
        }
    }

    QueryResult query_all(){
        QueryResult res;
        const int query_start_time = 300; // 11:00
        sort_g();
        rep(goal,N){
            for(int goal_time = query_start_time; goal_time <= 900; goal_time += 30){
                query_one(goal, goal_time, res);
            }
        }
        return res;
    }
};

State SQUARE;


constexpr int K = 25;

int get_time(int d_squared){
    double d = sqrt(d_squared);
    long long m = max(0.0 ,(3*d) / 200 - 1);
    long long d_squared_ll = d_squared;
    while ((200*m)*(200*m) < 9*d_squared_ll) {
        m += 1;
    }
    return 40 + 5*m;
}

int parse(const string& s){
    // s 06:00 ~ 21:00
    int hour = stoi(s.substr(0, 2));
    int minute = stoi(s.substr(3, 2));
    return (hour - 6) * 60 + minute;
}
string format_time(int t){
    int hour = 6 + t / 60;
    int minute = t % 60;
    string res;
    if(hour < 10) res += "0";
    res += to_string(hour) + ":";
    if(minute < 10) res += "0";
    res += to_string(minute);
    return res;
}

void get_input(){
    int n,r; cin>>n>>r;
    assert(n==N && r==R);
    pair<int,int> xy[N];
    rep(i,N){
        int x,y,w; cin>>x>>y>>w;
        xy[i] = {x,y};
        W[i] = w;
    }
    rep(i,N)DIST[i][i] = 0, near[i][i] = true;
    rep(i,N)rep(j,i+1,N){
        int dx = xy[i].first - xy[j].first;
        int dy = xy[i].second - xy[j].second;
        DIST[i][j] = get_time(dx*dx + dy*dy);
        DIST[j][i] = DIST[i][j];
        near[i][j] = (16*(dx*dx + dy*dy) < R*R) ? true : false;
    }
    int m; cin>>m;
    assert(m==M);
    rep(i,M){
        int a,b;
        string s,t;
        cin >> a >> s >> b >> t;
        a--; b--;
        SQUARE.G[b].emplace_back(a, parse(s), parse(t));
    }
    SQUARE.sort_g();
}

double get_score(State& state, const QueryResult& opponent_query){
    QueryResult player_query = state.query_all();
    long long w_player = 0, w_opponent = 0;
    rep(i,N)rep(j,N)if(!near[i][j])rep(k,21){
        int player_time = player_query.result[i][j][k];
        int opponent_time = opponent_query.result[i][j][k];
        if(player_time > opponent_time) w_player += W[i]*W[j];
        else w_opponent += W[i]*W[j];
    }
    cerr << "Player: " << w_player/1e10 << ", Opponent: " << w_opponent/1e10 << endl;
    return w_player / double(w_player + w_opponent);
}

struct AirLine{
    int start;
    vector<int> goals;
    vector<int> goal_times;

    AirLine(int start):start(start){}

    void add_goal(int goal, int goal_time){
        int last_goal_time = goal_times.empty() ? 0 : goal_times.back();
        int start_time = last_goal_time + DIST[start][goal];
        assert(last_goal_time <= start_time);
        goals.push_back(goal);
        goal_times.push_back(goal_time);
    }

    State get_state() const {
        State state;
        int cur_start = start;
        for(size_t i=0;i<goals.size();++i){
            int goal = goals[i];
            int goal_time = goal_times[i];
            int start_time = goal_time - DIST[cur_start][goal];
            state.G[goal].emplace_back(cur_start, start_time, goal_time);
            cur_start = goal;
        }
        return state;
    }
};

vector<AirLine> get_airlines(int center){
    int target = 0;
    vector<AirLine> airlines;
    rep(i,K){
        if(target==center) target++;
        int cur_time = 0;
        airlines.emplace_back(target);
        int dist = DIST[0][target];
        rep(itr,100){
            int nxt_time = cur_time + dist;
            if(nxt_time > 900) break;
            int to = itr%2 ? target : 0;
            airlines[i].add_goal(to, nxt_time);
            cur_time = nxt_time; 
        }
        target++;
    }
    return airlines;
}

State get_state_from_airlines(const vector<AirLine>& airlines){
    State state;
    for(const auto& airline: airlines){
        int start = airline.start;
        for(size_t i=0;i<airline.goals.size();++i){
            int goal = airline.goals[i];
            int goal_time = airline.goal_times[i];
            int start_time = goal_time - DIST[start][goal];
            state.G[goal].emplace_back(start, start_time, goal_time);
            start = goal;
        }
    }
    return state;
}

void output(const vector<AirLine>& airlines){
    for(const auto& airline: airlines){
        cout << airline.goals.size() << endl;
        rep(i,airline.goals.size()){
            int start = (i == 0) ? airline.start : airline.goals[i-1];
            int goal = airline.goals[i];
            int goal_time = airline.goal_times[i];
            int start_time = goal_time - DIST[start][goal];
            cout << start + 1 << " " << format_time(start_time) << " " << goal + 1 << " " << format_time(goal_time) << endl;
        }
    }
}

int main(){
    library::fast_io();
    get_input();
    QueryResult opponent_query = SQUARE.query_all();

    vector<AirLine> best_airlines;
    double best_score = -1e18;
    rep(center,N){
        auto airlines = get_airlines(center);
        State state = get_state_from_airlines(airlines);
        double score = get_score(state, opponent_query);
        if(score > best_score){
            best_score = score;
            best_airlines = airlines;
        }
        cerr << "Center: " << center << ", Score: " << score << endl;
    }
    cerr << "Best Score: " << best_score << endl;

    output(best_airlines);
    
    return 0;
}