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

• 問題: No.5023 Airlines Optimization
• ユーザー: sibasyun
• 提出日時: 2026-02-25 23:24:55
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 17,171 bytes
• コンパイル時間: 3,987 ms
• コンパイル使用メモリ: 271,140 KB
• 実行使用メモリ: 30,464 KB
• スコア: 6,065,027
• 最終ジャッジ日時: 2026-02-25 23:26:44
• 合計ジャッジ時間: 108,125 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

ファイルパターン	結果
other	AC * 27 WA * 73

ソースコード

#include <algorithm>
#include <array>
#include <bits/stdc++.h>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <math.h>
#include <random>
#include <vector>

using namespace std;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vl = vector<long long>;
using vvl = vector<vector<long long>>;
using vvvl = vector<vector<vector<long long>>>;

using ll = long long;
template <class T> using max_heap = priority_queue<T>;
template <class T> using min_heap = priority_queue<T, vector<T>, greater<>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, f, n) for (int i = (int)f; i < (int)(n); i++)
#define repd(i, n, l) for (int i = (int)n; i >= (int)l; i--)
#define all(p) p.begin(), p.end()
const ll inf = 1LL << 60;
void print() { putchar(' '); }
void print(bool a) { printf("%d", a); }
void print(int a) { printf("%d", a); }
void print(unsigned a) { printf("%u", a); }
void print(long a) { printf("%ld", a); }
void print(long long a) { printf("%lld", a); }
void print(unsigned long long a) { printf("%llu", a); }
void print(char a) { printf("%c", a); }
void print(char a[]) { printf("%s", a); }
void print(const char a[]) { printf("%s", a); }
void print(float a) { printf("%.15f", a); }
void print(double a) { printf("%.15f", a); }
void print(long double a) { printf("%.15Lf", a); }
void print(const string &a) {
  for (auto &&i : a)
    print(i);
}
template <class T> void print(const complex<T> &a) {
  if (a.real() >= 0)
    print('+');
  print(a.real());
  if (a.imag() >= 0)
    print('+');
  print(a.imag());
  print('i');
}
template <class T> void print(const vector<T> &);
template <class T, size_t size> void print(const array<T, size> &);
template <class T, class L> void print(const pair<T, L> &p);
template <class T, size_t size> void print(const T (&)[size]);
template <class T> void print(const vector<T> &a) {
  if (a.empty())
    return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    putchar(' ');
    print(*i);
  }
}
template <class T> void print(const deque<T> &a) {
  if (a.empty())
    return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    putchar(' ');
    print(*i);
  }
}
template <class T, size_t size> void print(const array<T, size> &a) {
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    putchar(' ');
    print(*i);
  }
}
template <class T, class L> void print(const pair<T, L> &p) {
  print(p.first);
  putchar(' ');
  print(p.second);
}
template <class T, size_t size> void print(const T (&a)[size]) {
  print(a[0]);
  for (auto i = a; ++i != end(a);) {
    putchar(' ');
    print(*i);
  }
}
template <class T> void print(const T &a) { cout << a; }

std::random_device seed_gen;
std::mt19937 engine(seed_gen());
uniform_real_distribution<> randR(0.0, 1.0);
using pii = pair<int, int>;
using vpii = vector<pii>;
using vvpii = vector<vector<pii>>;
using vvvpii = vector<vector<vector<pii>>>;

// https://atcoder.jp/contests/ahc002/submissions/47959319
//  時間をDouble型で管理し、経過時間も取り出せるクラス
class TimeKeeperDouble {
private:
  std::chrono::high_resolution_clock::time_point start_time_;
  double time_threshold_;

  double now_time_ = 0;

public:
  // 時間制限をミリ秒単位で指定してインスタンスをつくる。
  TimeKeeperDouble(const double time_threshold)
      : start_time_(std::chrono::high_resolution_clock::now()),
        time_threshold_(time_threshold) {}

  // 経過時間をnow_time_に格納する。
  void setNowTime() {
    auto diff = std::chrono::high_resolution_clock::now() - this->start_time_;
    this->now_time_ =
        std::chrono::duration_cast<std::chrono::microseconds>(diff).count() *
        1e-3; // ms
  }

  // 経過時間をnow_time_に取得する。
  double getNowTime() const { return this->now_time_; }

  // インスタンス生成した時から指定した時間制限を超過したか判定する。
  bool isTimeOver() const { return now_time_ >= time_threshold_; }
};

// 乱数を生成するクラス
class Random {
public:
  std::mt19937 mt_; // シード0でメルセンヌツイスターの乱数生成器を初期化
  // 0以上1.0未満の実数の範囲の乱数生成
  uniform_real_distribution<double> dd_{0, 1.0};

  // seedを指定して初期化
  Random(const int seed = 0) : mt_(std::mt19937(seed)) {}

  // 0以上m未満の整数の範囲の乱数
  inline int nextInt(const int m) {
    uniform_int_distribution<int> di(0, m - 1);
    return di(mt_);
  }

  // 0以上1.0未満の実数の範囲の乱数
  inline double nextDouble() { return dd_(mt_); }

  // 0以上1.0未満の実数の範囲の乱数のlog。焼きなまし法で使いやすい。
  inline double nextLog() { return log(dd_(mt_)); }
};
Random rnd((int)seed_gen());

// ここから

const int N = 47;
const int R = 1000;
const int M = 400;
const int K = 25;

// 座標を格納する構造体
struct Coord{
    double x, y;
    Coord(double x, double y) : x(x), y(y) {}
    Coord() : x(0), y(0) {}
};

double dist(Coord a, Coord b){
    return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

vector<vector<double>> dist_matrix(N, vector<double>(N));

struct Flight{
    int from, to;
    int start, end;
    Flight(int from, int to, int start, int end) : from(from), to(to), start(start), end(end) {}
    Flight() : from(0), to(0), start(0), end(0) {}
};

vector<Coord> coords(N, Coord());
vector<ll> w(N);
vector<Flight> square_flights(M, Flight());
vector<vector<Flight>> flights(K, vector<Flight>());

// hh:mm -> int
int time2int(string time){
    int h, m;
    sscanf(time.c_str(), "%d:%d", &h, &m);
    return h*60 + m;
}

// int -> hh:mm
string int2time(int time){
    int h = time / 60;
    int m = time % 60;
    stringstream ss;
    ss << setw(2) << setfill('0') << h << ":" << setw(2) << setfill('0') << m;
    return ss.str();
}

struct Input{
    int N_, R_, M_, K_;
    void input(){
        cin >> N_ >> R_;
        assert(N_ == N && R_ == R);
        rep(i, N)
            cin >> coords[i].x >> coords[i].y >> w[i];
        cin >> M_;
        assert(M_ == M);
        rep(i, M){
            int from, to;
            string start, end;
            cin >> from >> start >> to >> end;
            from--, to--;
            int _s = time2int(start), _e = time2int(end);
            square_flights[i] = Flight(from, to, _s, _e);
        }
        cin >> K_;
        rep(i, N) rep(j, N){
            dist_matrix[i][j] = dist(coords[i], coords[j]);
        }
    }
};

void output(){
    rep(i, K){
        cout << flights[i].size() << endl;
        for (auto flight : flights[i]){
            cout << flight.from + 1 << ' ' << int2time(flight.start) << ' ' << flight.to + 1 << ' ' << int2time(flight.end) << endl;
        }
    }
}

// ユークリッド距離が0.25R以上のi, jの数を数える
void test(){
    int ans = 0;
    rep(i, N) rep(j, N){
        if (dist(coords[i], coords[j]) >= 0.25*R){
            ans++;
        }
    }
    cout << ans << endl;
}
const int INF = 10000;
// 時刻t(11:00, 11:30,,,,)までに、頂点jに到達するフライトのうち、各頂点から最も遅く出発できる時間を求める
vvvi latest(N, vvi(N, vi(24*60, -INF)));
vector<vector<tuple<int, int, int>>> G(N); // tuple : from, start time, end time. 逆辺を張る
void calc_latest(){
    int et = 11 * 60; // 11:00から、30分刻みでスタート
    vi added(M, 0);
    while (et <= 21 * 60){
        // グラフの更新
        rep(i, M) {
            if (added[i]) continue;
            if (square_flights[i].end <= et) {
                added[i] = 1;
                G[square_flights[i].to].push_back(make_tuple(square_flights[i].from, square_flights[i].start, square_flights[i].end));
            }
        }
        // 各頂点について、最も遅く到達できる時間を求める
        rep(i, N){
            // latest[i][i][et] = et; // 自分に到達できる最も遅い時間はetとなる
            max_heap<pair<int, int>> hq;
            hq.push({et, i});
            while (!hq.empty()){
                auto [t, v] = hq.top(); hq.pop();
                if (latest[i][v][t] > t) continue;
                latest[i][v][t] = t;
                for (auto [from, start, end] : G[v]){
                    if (end > t) continue;
                    if (latest[from][i][et] < start){
                        latest[from][i][et] = start;
                        hq.push({start, from});
                    }
                }
            }
        }
        et += 30;
    }
}

// サークル航空（自社）の latest[i][j][et]
vvvi circle_latest(N, vvi(N, vi(24*60, -INF)));
vector<vector<tuple<int, int, int>>> G_circle(N);

void calc_circle_latest() {
    rep(i, N) G_circle[i].clear();
    for (int k = 0; k < K; k++) {
        for (const auto& f : flights[k]) {
            G_circle[f.to].push_back(make_tuple(f.from, f.start, f.end));
        }
    }
    for (int et = 11 * 60; et <= 21 * 60; et += 30) {
        rep(i, N) rep(j, N) circle_latest[i][j][et] = -INF;
        rep(j, N) {
            max_heap<pair<int, int>> hq;
            hq.push({et, j});
            while (!hq.empty()) {
                auto [t, v] = hq.top(); hq.pop();
                if (circle_latest[j][v][et] >= t) continue;
                circle_latest[j][v][et] = t;
                for (auto [from, start, end] : G_circle[v]) {
                    if (end > t) continue;
                    if (circle_latest[from][j][et] < start) {
                        circle_latest[from][j][et] = start;
                        hq.push({start, from});
                    }
                }
            }
        }
    }
}

// スコア S = v_ci / (v_sq + v_ci) を返す。v_sq, v_ci も参照で返す。
double compute_score(ll& v_sq, ll& v_ci) {
    v_sq = 0, v_ci = 0;
    for (int et = 11 * 60; et <= 21 * 60; et += 30) {
        rep(i, N) rep(j, N) {
            if (dist(coords[i], coords[j]) < 0.25 * R) continue;
            int s_sq = latest[i][j][et];
            int s_ci = circle_latest[i][j][et];
            ll val = w[i] * w[j];
            if (s_ci <= -INF) {
                v_sq += val;
            } else if (s_sq < s_ci) {
                v_ci += val;
            } else {
                v_sq += val;
            }
        }
    }
    if (v_sq + v_ci == 0) return 0.0;
    return (double)v_ci / (v_sq + v_ci);
}

// 各et(11:00, 11:30,,,,)について、0.25R以上の距離の組について、wi * wj, 及び最も遅くスタートできる時間を格納する
vector<vector<tuple<ll, int, int, int>>> values(24*60);
void calc_values(){
    for (int et = 11 * 60; et <= 21 * 60; et += 30){
        rep(i, N) rep(j, N){
            if (dist(coords[i], coords[j]) < 0.25*R) continue;
            values[et].push_back(make_tuple(w[i] * w[j], latest[i][j][et], i, j));
        }
        sort(all(values[et]));
        reverse(all(values[et]));
        // debug
        // cout << values[et].size() << endl;
        // for (auto [value, start, i, j] : values[et]){
        //     cout << value << ' ' << int2time(start) << ' ' << i + 1 << ' ' << j + 1 << endl;
        // }
    }
}

// 貪欲に各飛行機を価値が高い順に割り付ける
// 飛行機の到達時間及び到着地をもつ必要があるが、それは答えの配列で管理可能
// wi * wjのmaxに対して10%未満の便については無視してもよいか？

// 5分単位で切り上げる
int leadtime(int i, int j){
    return ceil((60 * dist_matrix[i][j] / 800.0 + 40.0) / 5.0) * 5;
}

// struct Flight{
//     int from, to;
//     int start, end;
//     Flight(int from, int to, int start, int end) : from(from), to(to), start(start), end(end) {}
//     Flight() : from(0), to(0), start(0), end(0) {}
// };

void greedy(){
    ll max_value = 0;
    rep(i, N) rep(j, N){
        if (dist(coords[i], coords[j]) < 0.25*R) continue;
        max_value = max(max_value, w[i] * w[j]);
    }
    // 10%未満の便については無視してもよい
    ll threshold = max_value / 10;
    for (int et = 11 * 60; et <= 21 * 60; et += 30){
        for (auto [value, start, i, j] : values[et]){
            if (value < threshold) break;
            int lt = leadtime(i, j);
            if (et - lt < 6 * 60) continue; // 6時未満の便はスキップ
            if (et - lt <= start) continue; // スクエアより遅い出発では意味がない
            rep(k, K){
                if (flights[k].size() == 0) {
                    flights[k].push_back(Flight(i, j, et - lt, et));
                    break;
                } else {
                    int now = flights[k].back().to;
                    if (now != i) continue;
                    if (now == j) continue;
                    int nt = flights[k].back().end;
                    if (et - lt >= nt){
                        flights[k].push_back(Flight(i, j, et - lt, et));
                        break;
                    }
                }
            }
        }
    }
}

// 便 (i,j,start,end) を plane k の position に挿入可能か
bool can_insert(int k, int pos, int i, int j, int start, int end) {
    if (start < 6 * 60) return false;
    if (pos == 0) {
        if (flights[k].empty()) return true;
        return flights[k][0].from == j && flights[k][0].start >= end;
    }
    if (pos > (int)flights[k].size()) return false;
    const auto& prev = flights[k][pos - 1];
    if (prev.to != i || prev.end > start) return false;
    if (pos == (int)flights[k].size()) return true;
    return flights[k][pos].from == j && flights[k][pos].start >= end;
}

// 挿入を実行
void do_insert(int k, int pos, int i, int j, int start, int end) {
    flights[k].insert(flights[k].begin() + pos, Flight(i, j, start, end));
}

// 便を1本削除
void do_remove(int k, int idx) {
    flights[k].erase(flights[k].begin() + idx);
}

// 山登り + 焼きなまし: add/remove で改善、序盤は悪化も一定確率で受理
void hill_climb(TimeKeeperDouble& tk) {
    tk.setNowTime();
    ll v_sq, v_ci;
    calc_circle_latest();
    double best_score = compute_score(v_sq, v_ci);
    vector<vector<Flight>> best_flights = flights;

    const double time_limit = 950.; // ms (1秒手前で打ち切り)
    int iter = 0;
    while (!tk.isTimeOver()) {
        tk.setNowTime();
        if (tk.getNowTime() >= time_limit) break;
        double elapsed = tk.getNowTime();
        double progress = elapsed / time_limit;
        double temp = 0.02 * (1.0 - progress); // 温度: 序盤で悪化受理

        double cur_score = compute_score(v_sq, v_ci);
        int move = rnd.nextInt(2);

        if (move == 1) {
            // remove
            vi non_empty;
            rep(k, K) if (!flights[k].empty()) non_empty.push_back(k);
            if (non_empty.empty()) continue;
            int k = non_empty[rnd.nextInt(non_empty.size())];
            int idx = rnd.nextInt(flights[k].size());
            Flight backup = flights[k][idx];
            do_remove(k, idx);
            calc_circle_latest();
            double new_score = compute_score(v_sq, v_ci);
            if (new_score >= cur_score || (temp > 0 && rnd.nextDouble() < exp((new_score - cur_score) / temp))) {
                cur_score = new_score;
                if (new_score > best_score) {
                    best_score = new_score;
                    best_flights = flights;
                }
            } else {
                flights[k].insert(flights[k].begin() + idx, backup);
            }
        } else {
            // add
            int et = 11 * 60 + rnd.nextInt(21) * 30;
            if (values[et].empty()) continue;
            int idx = rnd.nextInt(values[et].size());
            auto [value, start_sq, i, j] = values[et][idx];
            int lt = leadtime(i, j);
            int s = et - lt, e = et;
            if (s < 6 * 60 || s <= start_sq) continue;

            vector<pii> candidates;
            rep(k, K) {
                rep(pos, (int)flights[k].size() + 1) {
                    if (can_insert(k, pos, i, j, s, e)) candidates.push_back({k, pos});
                }
            }
            if (candidates.empty()) continue;
            int c = rnd.nextInt(candidates.size());
            int k = candidates[c].first, pos = candidates[c].second;
            do_insert(k, pos, i, j, s, e);
            calc_circle_latest();
            double new_score = compute_score(v_sq, v_ci);
            if (new_score >= cur_score || (temp > 0 && rnd.nextDouble() < exp((new_score - cur_score) / temp))) {
                cur_score = new_score;
                if (new_score > best_score) {
                    best_score = new_score;
                    best_flights = flights;
                }
            } else {
                do_remove(k, pos);
            }
        }
        iter++;
    }
    flights = best_flights;
}

int main(){
    TimeKeeperDouble tk(950); // 1秒 = 1000ms
    Input input;
    input.input();
    calc_latest();
    calc_values();
    greedy();
    hill_climb(tk);
    output();
    return 0;
}