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

• 問題: No.5023 Airlines Optimization
• ユーザー: さがかんすけ
• 提出日時: 2026-02-25 21:38:07
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 7 ms / 1,000 ms
• コード長: 7,217 bytes
• コンパイル時間: 1,989 ms
• コンパイル使用メモリ: 139,024 KB
• 実行使用メモリ: 7,848 KB
• スコア: 27,941,969
• 最終ジャッジ日時: 2026-02-25 21:38:15
• 合計ジャッジ時間: 7,677 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

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

ソースコード

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
using ll = long long;

namespace {
constexpr int DAY_START = 6 * 60;
constexpr int DAY_END = 21 * 60;

enum class TimeFormat {
    Minutes,
    HHMM,
    HHColon
};

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

// 所要時間を5分単位で切り上げる
int calc_duration_min(double dist) {
    long double raw = 60.0L * (long double)dist / 800.0L + 40.0L;
    int q = (int)ceill(raw / 5.0L);
    return q * 5;
}

int hhmm_to_min(int x) {
    return (x / 100) * 60 + (x % 100);
}

int min_to_hhmm(int x) {
    return (x / 60) * 100 + (x % 60);
}

int parse_time_token(const string& tok, int& raw_out, bool& has_colon) {
    has_colon = false;
    size_t p = tok.find(':');
    if (p == string::npos) {
        raw_out = stoi(tok);
        return raw_out;
    }
    has_colon = true;
    int hh = stoi(tok.substr(0, p));
    int mm = stoi(tok.substr(p + 1));
    raw_out = hh * 100 + mm;
    return hh * 60 + mm;
}

string encode_time(int minute, TimeFormat fmt) {
    if (fmt == TimeFormat::Minutes) return to_string(minute);
    if (fmt == TimeFormat::HHMM) return to_string(min_to_hhmm(minute));
    char buf[8];
    snprintf(buf, sizeof(buf), "%02d:%02d", minute / 60, minute % 60);
    return string(buf);
}

vector<Flight> build_shuttle_schedule(int hub, int spoke, int start_time, bool start_from_hub,
                                      const vector<vector<int>>& dur) {
    vector<Flight> out;
    int cur = start_from_hub ? hub : spoke;
    int nxt = start_from_hub ? spoke : hub;
    int tm = start_time;

    while (true) {
        int d = dur[cur][nxt];
        if (d <= 0) break;
        if (tm + d > DAY_END) break;
        out.push_back(Flight{cur + 1, tm, nxt + 1, tm + d});
        tm += d;
        swap(cur, nxt);
    }
    return out;
}
}  // namespace

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

    int N, R;
    cin >> N >> R;

    vector<int> x(N), y(N);
    vector<ll> w(N);
    for (int i = 0; i < N; ++i) {
        cin >> x[i] >> y[i] >> w[i];
    }

    int M;
    cin >> M;
    struct RawFlight {
        int a;
        int b;
        int s_raw;
        int t_raw;
    };
    vector<RawFlight> raw_sq(M);
    bool has_colon_input = false;
    for (int i = 0; i < M; ++i) {
        int a, b;
        string s_tok, t_tok;
        cin >> a >> s_tok >> b >> t_tok;

        int s_raw, t_raw;
        bool s_colon, t_colon;
        parse_time_token(s_tok, s_raw, s_colon);
        parse_time_token(t_tok, t_raw, t_colon);
        has_colon_input = has_colon_input || s_colon || t_colon;

        raw_sq[i] = RawFlight{a - 1, b - 1, s_raw, t_raw};
    }

    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) continue;
            double dx = (double)x[i] - (double)x[j];
            double dy = (double)y[i] - (double)y[j];
            double d = sqrt(dx * dx + dy * dy);
            dur[i][j] = calc_duration_min(d);
        }
    }

    // 入力の時刻表現（分 or HHMM）を既存便との整合で判定
    int mismatch_minutes = 0;
    int mismatch_hhmm = 0;
    for (const auto& f : raw_sq) {
        int need = dur[f.a][f.b];

        int got_m = f.t_raw - f.s_raw;
        if (got_m != need) mismatch_minutes++;

        int got_h = hhmm_to_min(f.t_raw) - hhmm_to_min(f.s_raw);
        if (got_h != need) mismatch_hhmm++;
    }
    TimeFormat out_fmt = TimeFormat::Minutes;
    if (has_colon_input) {
        out_fmt = TimeFormat::HHColon;
    } else {
        if (mismatch_hhmm < mismatch_minutes) {
            out_fmt = TimeFormat::HHMM;
        } else if (mismatch_hhmm == mismatch_minutes) {
            bool has_minute_only_pattern = false;
            bool has_large_clock_like = false;
            bool has_small_clock_like = false;
            for (const auto& f : raw_sq) {
                int ts[2] = {f.s_raw, f.t_raw};
                for (int z = 0; z < 2; ++z) {
                    int v = ts[z];
                    if (v % 100 >= 60) has_minute_only_pattern = true;
                    if (v > 1439) has_large_clock_like = true;
                    if (v < 600) has_small_clock_like = true;
                }
            }
            if (!has_minute_only_pattern && (has_large_clock_like || !has_small_clock_like)) {
                out_fmt = TimeFormat::HHMM;
            }
        }
    }

    // 人口最大都市をハブにする
    int hub = 0;
    for (int i = 1; i < N; ++i) {
        if (w[i] > w[hub]) hub = i;
    }

    vector<int> spokes;
    spokes.reserve(N - 1);
    for (int i = 0; i < N; ++i) {
        if (i != hub) spokes.push_back(i);
    }

    // ハブからの距離も加味して重要度を作る
    vector<double> score(N, 0.0);
    for (int v : spokes) {
        double dx = (double)x[v] - (double)x[hub];
        double dy = (double)y[v] - (double)y[hub];
        double d = sqrt(dx * dx + dy * dy);
        score[v] = (double)w[v] * (1.0 + d / (double)R);
    }
    sort(spokes.begin(), spokes.end(), [&](int a, int b) {
        if (score[a] != score[b]) return score[a] > score[b];
        return w[a] > w[b];
    });

    int use_spokes = min((int)spokes.size(), min(K, 12));
    vector<int> alloc(use_spokes, 1);
    int remain = K - use_spokes;

    if (use_spokes > 0 && remain > 0) {
        vector<double> wt(use_spokes, 0.0), frac(use_spokes, 0.0);
        double sum_wt = 0.0;
        for (int i = 0; i < use_spokes; ++i) {
            wt[i] = sqrt(max(1.0, score[spokes[i]]));
            sum_wt += wt[i];
        }

        for (int i = 0; i < use_spokes; ++i) {
            double z = remain * wt[i] / sum_wt;
            int add = (int)floor(z);
            alloc[i] += add;
            remain -= add;
            frac[i] = z - add;
        }

        vector<int> ord(use_spokes);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int a, int b) { return frac[a] > frac[b]; });
        for (int k = 0; k < remain; ++k) {
            alloc[ord[k % use_spokes]]++;
        }
    }

    vector<vector<Flight>> schedules(K);
    int plane_id = 0;

    for (int i = 0; i < use_spokes && plane_id < K; ++i) {
        int spoke = spokes[i];
        for (int j = 0; j < alloc[i] && plane_id < K; ++j) {
            int offset_slot = (i * 5 + j * 3) % 24;
            int start_time = DAY_START + offset_slot * 5;
            bool start_from_hub = ((i + j) % 2 == 0);
            schedules[plane_id] =
                build_shuttle_schedule(hub, spoke, start_time, start_from_hub, dur);
            plane_id++;
        }
    }

    // 余った機体は運航なし
    while (plane_id < K) {
        schedules[plane_id].clear();
        plane_id++;
    }

    for (int i = 0; i < K; ++i) {
        cout << schedules[i].size() << '\n';
        for (const auto& f : schedules[i]) {
            cout << f.a << ' ' << encode_time(f.s, out_fmt) << ' ' << f.b << ' '
                 << encode_time(f.t, out_fmt) << '\n';
        }
    }
    return 0;
}