結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 さがかんすけ
|
| 提出日時 | 2026-02-25 23:56:17 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 713 ms / 1,000 ms |
| コード長 | 46,859 bytes |
| 記録 | |
| コンパイル時間 | 5,534 ms |
| コンパイル使用メモリ | 225,552 KB |
| 実行使用メモリ | 7,848 KB |
| スコア | 38,224,356 |
| 最終ジャッジ日時 | 2026-02-25 23:57:41 |
| 合計ジャッジ時間 | 79,830 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#include <algorithm>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <string>
#include <tuple>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = long long;
namespace {
constexpr int DAY_START = 6 * 60;
constexpr int DAY_END = 21 * 60;
constexpr int SLOT_STEP = 5;
constexpr int DEADLINE_COUNT = 21;
constexpr int NEG = -1000000000;
constexpr double TOTAL_TIME_LIMIT_SEC = 0.78;
constexpr double SA_MAX_TIME_SEC = 0.66;
constexpr double SA_MARGIN_SEC = 0.05;
constexpr int BEAM_WIDTH = 16;
constexpr int BEAM_DEPTH = 3;
constexpr int BEAM_SCAN_FIRST = 140;
constexpr int BEAM_SCAN_NEXT = 90;
constexpr int WAIT_FIRST_MAX = 240;
constexpr int WAIT_NEXT_MAX = 90;
constexpr int ZERO_WAIT_ALLOW = 60;
constexpr int REBUILD_MAX_LEGS = 14;
constexpr int INIT_SCAN_MAX = 500;
constexpr int ACTIVE_SCAN_MAX = 190;
constexpr int ACTIVE_WAIT_HORIZON = 120;
constexpr int FUTURE_HORIZON = 120;
constexpr int FUTURE_SCAN_MAX = 70;
constexpr int NEAR_PER_CITY = 4;
constexpr int NEAR_TIME_STEP = 10;
constexpr double STEAL_BEAM_GAIN_WEIGHT = 20.0;
constexpr ll MOVE_OVERRIDE_NUM = 10; // best_move_future * NUM >= best_gain * DEN
constexpr ll MOVE_OVERRIDE_DEN = 80; // 8倍以上の将来奪取見込みがある時のみ移動優先
constexpr double STEAL_FAST_WEIGHT = 0.08;
constexpr double EDGE_FAST_WEIGHT = 55.0;
constexpr double WAIT_FAST_WEIGHT = 2.2;
constexpr double FILL_FAST_WEIGHT = 1.2;
constexpr double FAST_SKIP_COEF = 1.4;
constexpr int STAGNATE_LIMIT = 40;
constexpr double WAIT_AUG_WEIGHT = 600.0;
struct Flight {
int a; // 0-index
int b; // 0-index
int s; // minutes
int t; // minutes
};
struct Candidate {
int a;
int b;
int s;
int t;
int edge;
uint32_t mask; // 締切ごとの勝利ビット
ll pair_w; // 対象ODの人口積
ll base_gain; // スクエア単体に対する直行便利得
};
struct PlaneState {
bool active = false;
int city = -1;
int tm = DAY_START;
};
struct FillInfo {
int rt_time = 1e9; // 往復1セットに必要な最短時間
int rt_edge = 0; // 往復1セットで奪取密度が高いもの
int one_time = 1e9; // 片道の最短時間
int one_edge = 0; // 片道で奪取密度が高いもの
};
struct XorShift64 {
uint64_t x;
explicit XorShift64(uint64_t seed = 88172645463325252ULL) : x(seed ? seed : 88172645463325252ULL) {}
uint64_t next_u64() {
x ^= x << 7;
x ^= x >> 9;
return x;
}
int next_int(int l, int r) {
return l + (int)(next_u64() % (uint64_t)(r - l + 1));
}
double next_double() {
return (double)((next_u64() >> 11) * (1.0 / 9007199254740992.0));
}
};
int calc_duration_min(long double dist) {
long double raw = 60.0L * dist / 800.0L + 40.0L;
int q = (int)ceill(raw / 5.0L - 1e-12L);
return q * 5;
}
int parse_time(const string& tok) {
size_t p = tok.find(':');
if (p != string::npos) {
int hh = stoi(tok.substr(0, p));
int mm = stoi(tok.substr(p + 1));
return hh * 60 + mm;
}
int x = stoi(tok);
// HHMM 形式にも対応
if (x >= 600 && x <= 2359 && x % 100 < 60) {
return (x / 100) * 60 + (x % 100);
}
// 分として扱う
return x;
}
string to_hhmm(int m) {
char buf[8];
snprintf(buf, sizeof(buf), "%02d:%02d", m / 60, m % 60);
return string(buf);
}
vector<int> build_deadlines() {
vector<int> d(DEADLINE_COUNT);
for (int k = 0; k < DEADLINE_COUNT; ++k) d[k] = 11 * 60 + 30 * k;
return d;
}
// ある都市で gap 分の待機があるとき、探索中にどれだけ埋められそうかを近似評価する
double estimate_fill_gain(const FillInfo& fi, int gap, bool need_return) {
if (gap <= 0) return 0.0;
if (need_return) {
if (fi.rt_time > gap || fi.rt_time >= (int)1e9) return 0.0;
int cnt = gap / fi.rt_time;
return (double)cnt * (double)fi.rt_edge;
}
if (fi.one_time > gap || fi.one_time >= (int)1e9) return 0.0;
int cnt = gap / fi.one_time;
return (double)cnt * (double)fi.one_edge;
}
// 1機体の高速近似スコア（差分評価用）
double calc_plane_fast_score(const vector<int>& seq, const vector<Candidate>& cand,
const vector<FillInfo>& fill_info) {
if (seq.empty()) return 0.0;
double sc = 0.0;
// 初便までの待機（開始都市は初便の出発都市）
const auto& first = cand[seq[0]];
int gap0 = first.s - DAY_START;
if (gap0 > 0) {
sc -= WAIT_FAST_WEIGHT * (double)gap0;
sc += FILL_FAST_WEIGHT * estimate_fill_gain(fill_info[first.a], gap0, true);
}
for (int i = 0; i < (int)seq.size(); ++i) {
const auto& c = cand[seq[i]];
sc += STEAL_FAST_WEIGHT * (double)c.base_gain;
sc += EDGE_FAST_WEIGHT * (double)c.edge;
if (i + 1 < (int)seq.size()) {
const auto& nx = cand[seq[i + 1]];
int g = nx.s - c.t;
if (g > 0) {
sc -= WAIT_FAST_WEIGHT * (double)g;
sc += FILL_FAST_WEIGHT * estimate_fill_gain(fill_info[c.b], g, true);
}
}
}
// 末尾待機
const auto& last = cand[seq.back()];
int tail = DAY_END - last.t;
if (tail > 0) {
sc -= WAIT_FAST_WEIGHT * (double)tail;
sc += FILL_FAST_WEIGHT * estimate_fill_gain(fill_info[last.b], tail, false);
}
return sc;
}
// 1機体の待機埋め近似スコア（探索目的に組み込む）
double calc_plane_wait_fill_score(const vector<int>& seq, const vector<Candidate>& cand,
const vector<FillInfo>& fill_info) {
if (seq.empty()) return 0.0;
double sc = 0.0;
const auto& first = cand[seq[0]];
int gap0 = first.s - DAY_START;
if (gap0 > 0) {
sc -= WAIT_FAST_WEIGHT * (double)gap0;
sc += 2.0 * FILL_FAST_WEIGHT * estimate_fill_gain(fill_info[first.a], gap0, true);
}
for (int i = 0; i + 1 < (int)seq.size(); ++i) {
const auto& c = cand[seq[i]];
const auto& nx = cand[seq[i + 1]];
int g = nx.s - c.t;
if (g > 0) {
sc -= WAIT_FAST_WEIGHT * (double)g;
sc += 2.0 * FILL_FAST_WEIGHT * estimate_fill_gain(fill_info[c.b], g, true);
}
}
const auto& last = cand[seq.back()];
int tail = DAY_END - last.t;
if (tail > 0) {
sc -= WAIT_FAST_WEIGHT * (double)tail;
sc += 2.0 * FILL_FAST_WEIGHT * estimate_fill_gain(fill_info[last.b], tail, false);
}
return sc;
}
inline uint64_t flight_key(int a, int b, int s) {
return ((uint64_t)s << 12) | ((uint64_t)a << 6) | (uint64_t)b;
}
// 時間拡張DPで、開始時刻から終了時刻までの便列を最大時間だけ埋める
vector<Flight> build_best_fill_path(int start_city, int start_tm, int end_tm,
const vector<vector<int>>& dur,
const vector<vector<int>>& sq_edge_count,
const unordered_set<uint64_t>& used_keys,
bool need_return) {
int rem = end_tm - start_tm;
if (rem <= 0) return {};
int lim = rem / SLOT_STEP;
if (lim <= 0) return {};
int n = (int)dur.size();
const int NEG_INF = -1000000000;
vector<vector<int>> best(lim + 1, vector<int>(n, NEG_INF));
vector<vector<int>> prev_t(lim + 1, vector<int>(n, -1));
vector<vector<int>> prev_city(lim + 1, vector<int>(n, -1));
best[0][start_city] = 0;
for (int t = 0; t <= lim; ++t) {
int abs_tm = start_tm + t * SLOT_STEP;
for (int u = 0; u < n; ++u) {
if (best[t][u] == NEG_INF) continue;
for (int v = 0; v < n; ++v) {
if (v == u) continue;
int d = dur[u][v];
int dt = d / SLOT_STEP;
int nt = t + dt;
if (nt > lim) continue;
if (used_keys.find(flight_key(u, v, abs_tm)) != used_keys.end()) continue;
int ne = best[t][u] + sq_edge_count[u][v];
if (ne > best[nt][v]) {
best[nt][v] = ne;
prev_t[nt][v] = t;
prev_city[nt][v] = u;
}
}
}
}
int goal_t = 0;
int goal_city = -1;
if (need_return) {
for (int t = lim; t >= 1; --t) {
if (best[t][start_city] != NEG_INF) {
goal_t = t;
goal_city = start_city;
break;
}
}
} else {
for (int t = lim; t >= 1; --t) {
int best_city = -1;
int best_edge = NEG_INF;
for (int v = 0; v < n; ++v) {
if (best[t][v] > best_edge) {
best_edge = best[t][v];
best_city = v;
}
}
if (best_edge != NEG_INF) {
goal_t = t;
goal_city = best_city;
break;
}
}
}
if (goal_t == 0 || goal_city == -1) return {};
vector<Flight> rev;
int cur_t = goal_t;
int cur_city = goal_city;
while (cur_t > 0) {
int pt = prev_t[cur_t][cur_city];
int pc = prev_city[cur_t][cur_city];
if (pt < 0 || pc < 0) {
rev.clear();
break;
}
rev.push_back(Flight{pc, cur_city, start_tm + pt * SLOT_STEP, start_tm + cur_t * SLOT_STEP});
cur_t = pt;
cur_city = pc;
}
if (rev.empty() || cur_t != 0 || cur_city != start_city) return {};
reverse(rev.begin(), rev.end());
return rev;
}
// 区間[start_tm, end_tm]を、開始都市に戻る制約付きで最大限埋める
void fill_gap_roundtrips(vector<Flight>& out, int base, int start_tm, int end_tm,
const vector<vector<int>>& dur,
const vector<vector<int>>& sq_edge_count,
unordered_set<uint64_t>& used_keys) {
auto path =
build_best_fill_path(base, start_tm, end_tm, dur, sq_edge_count, used_keys, true);
for (const auto& f : path) {
out.push_back(f);
used_keys.insert(flight_key(f.a, f.b, f.s));
}
}
// 末尾区間[start_tm, DAY_END]を、戻り制約なしで最大限埋める
void fill_tail_chain(vector<Flight>& out, int start_city, int start_tm,
const vector<vector<int>>& dur,
const vector<vector<int>>& sq_edge_count,
unordered_set<uint64_t>& used_keys) {
auto path = build_best_fill_path(start_city, start_tm, DAY_END, dur, sq_edge_count, used_keys,
false);
for (const auto& f : path) {
out.push_back(f);
used_keys.insert(flight_key(f.a, f.b, f.s));
}
}
// スクエア便の発着回数が多い都市を返す
int pick_busy_city(const vector<vector<int>>& sq_edge_count) {
int n = (int)sq_edge_count.size();
int best_city = 0;
int best_score = -1;
for (int v = 0; v < n; ++v) {
int sc = 0;
for (int u = 0; u < n; ++u) {
sc += sq_edge_count[v][u];
sc += sq_edge_count[u][v];
}
if (sc > best_score) {
best_score = sc;
best_city = v;
}
}
return best_city;
}
// 既存ルートの前後ギャップを埋めて、待機時間を減らした便列を作る
vector<Flight> densify_route(const vector<int>& route_idx, const vector<Candidate>& cand,
const vector<vector<int>>& dur,
const vector<vector<int>>& sq_edge_count, int fallback_city,
unordered_set<uint64_t>& used_keys) {
vector<Flight> core;
core.reserve(route_idx.size());
for (int ci : route_idx) {
const auto& c = cand[ci];
core.push_back(Flight{c.a, c.b, c.s, c.t});
}
vector<Flight> out;
if (core.empty()) {
fill_tail_chain(out, fallback_city, DAY_START, dur, sq_edge_count, used_keys);
return out;
}
// 初便までの待機を往復で埋める
fill_gap_roundtrips(out, core[0].a, DAY_START, core[0].s, dur, sq_edge_count, used_keys);
for (int i = 0; i < (int)core.size(); ++i) {
out.push_back(core[i]);
used_keys.insert(flight_key(core[i].a, core[i].b, core[i].s));
if (i + 1 < (int)core.size()) {
// 既存2便の間の待機を往復で埋める（出発都市は維持）
fill_gap_roundtrips(out, core[i].b, core[i].t, core[i + 1].s, dur, sq_edge_count,
used_keys);
}
}
// 最終便以降を21:00まで埋める
fill_tail_chain(out, core.back().b, core.back().t, dur, sq_edge_count, used_keys);
return out;
}
// 奪取寄与がない便を、連結性を壊さない範囲で削除する
void prune_redundant_won_routes(vector<vector<int>>& routes, const vector<Candidate>& cand, int n) {
vector<vector<vector<int>>> bit_cnt(
n, vector<vector<int>>(n, vector<int>(DEADLINE_COUNT, 0)));
for (const auto& seq : routes) {
for (int ci : seq) {
const auto& c = cand[ci];
if (c.mask == 0) continue;
for (int k = 0; k < DEADLINE_COUNT; ++k) {
if ((c.mask >> k) & 1u) bit_cnt[c.a][c.b][k]++;
}
}
}
bool changed = true;
while (changed) {
changed = false;
for (int p = 0; p < (int)routes.size(); ++p) {
auto& seq = routes[p];
for (int i = 0; i < (int)seq.size(); ++i) {
int ci = seq[i];
const auto& c = cand[ci];
if (c.mask == 0) continue;
bool has_unique = false;
for (int k = 0; k < DEADLINE_COUNT; ++k) {
if (((c.mask >> k) & 1u) && bit_cnt[c.a][c.b][k] == 1) {
has_unique = true;
break;
}
}
if (has_unique) continue;
bool link_ok = true;
if (i > 0 && i + 1 < (int)seq.size()) {
const auto& prv = cand[seq[i - 1]];
const auto& nxt = cand[seq[i + 1]];
if (prv.b != nxt.a || prv.t > nxt.s) link_ok = false;
}
if (!link_ok) continue;
for (int k = 0; k < DEADLINE_COUNT; ++k) {
if ((c.mask >> k) & 1u) bit_cnt[c.a][c.b][k]--;
}
seq.erase(seq.begin() + i);
--i;
changed = true;
}
}
}
}
// latest[k][dst][src] = 締切kまでにdstへ到着するsrcの最遅出発時刻
vector<vector<vector<int>>> build_latest_tensor(int n, const vector<Flight>& flights,
const vector<int>& deadlines) {
vector<Flight> fs = flights;
sort(fs.begin(), fs.end(), [](const Flight& p, const Flight& q) {
if (p.s != q.s) return p.s > q.s;
return p.t > q.t;
});
vector<vector<vector<int>>> latest(
DEADLINE_COUNT, vector<vector<int>>(n, vector<int>(n, NEG)));
for (int k = 0; k < DEADLINE_COUNT; ++k) {
int dl = deadlines[k];
for (int dst = 0; dst < n; ++dst) {
vector<int> cur(n, NEG);
cur[dst] = dl;
for (const auto& f : fs) {
if (f.t <= cur[f.b] && f.s > cur[f.a]) cur[f.a] = f.s;
}
latest[k][dst] = std::move(cur);
}
}
return latest;
}
ll calc_exact_score(const vector<vector<int>>& routes, const vector<Candidate>& cand,
int n, const vector<int>& deadlines,
const vector<vector<vector<int>>>& latest_sq,
const vector<pair<int, int>>& eval_pairs,
const vector<vector<ll>>& pair_w) {
vector<Flight> circle;
for (const auto& seq : routes) {
for (int ci : seq) {
const auto& c = cand[ci];
circle.push_back(Flight{c.a, c.b, c.s, c.t});
}
}
auto latest_ci = build_latest_tensor(n, circle, deadlines);
ll vci = 0;
for (int k = 0; k < DEADLINE_COUNT; ++k) {
for (const auto& pr : eval_pairs) {
int a = pr.first;
int b = pr.second;
if (latest_sq[k][b][a] < latest_ci[k][b][a]) vci += pair_w[a][b];
}
}
return vci;
}
// 1手先を返すためのビーム（評価はスクエア基準の近似）
int beam_pick_next(int start_city, int start_tm, const vector<Candidate>& cand,
const vector<int>& all_by_time, const vector<vector<int>>& by_from,
const vector<char>& blocked, const vector<FillInfo>& fill_info,
XorShift64* rng = nullptr, double rand_amp = 0.0) {
struct Node {
int city;
int tm;
int depth;
int first_ci;
double score;
};
vector<Node> beam;
beam.push_back(Node{start_city, start_tm, 0, -1, 0.0});
int best_first = -1;
double best_score = -1e300;
auto try_expand = [&](const Node& node, int ci, vector<Node>& nxt) {
if (blocked[ci]) return;
const auto& c = cand[ci];
if (c.s < node.tm) return;
int wait = c.s - node.tm;
int wait_lim = (node.city == -1 ? WAIT_FIRST_MAX : WAIT_NEXT_MAX);
if (wait > wait_lim) return;
ll gain = c.base_gain;
int d = c.t - c.s;
double fill_bonus = 0.0;
if (node.city != -1 && wait > 0) {
fill_bonus = estimate_fill_gain(fill_info[node.city], wait, true);
}
double add = -1e300;
if (gain > 0) {
add = STEAL_BEAM_GAIN_WEIGHT * (double)gain + 110.0 * c.edge -
1.9 * wait - 0.35 * d + 45.0 * fill_bonus;
} else {
// 既に奪取済み（増分なし）になりやすい便は再構築でも採用しない
if (c.mask != 0) return;
if (c.edge == 0) return;
if (wait > ZERO_WAIT_ALLOW) return;
add = 60.0 * c.edge - 12.0 * wait - 1.1 * d + 30.0 * fill_bonus;
}
// 同点近辺でランダムノイズを入れて局所解脱出を強化
if (rng != nullptr && rand_amp > 0.0) {
add *= (1.0 + rand_amp * (rng->next_double() - 0.5));
}
Node nn;
nn.city = c.b;
nn.tm = c.t;
nn.depth = node.depth + 1;
nn.first_ci = (node.first_ci == -1 ? ci : node.first_ci);
nn.score = node.score + add;
if (nn.first_ci != -1 && nn.score > best_score) {
best_score = nn.score;
best_first = nn.first_ci;
}
nxt.push_back(nn);
};
for (int dep = 0; dep < BEAM_DEPTH; ++dep) {
vector<Node> nxt;
nxt.reserve((size_t)beam.size() * 64ULL);
for (const auto& node : beam) {
if (node.city == -1) {
auto it = lower_bound(all_by_time.begin(), all_by_time.end(), node.tm,
[&](int idx, int t0) { return cand[idx].s < t0; });
int scanned = 0;
for (; it != all_by_time.end() && scanned < BEAM_SCAN_FIRST; ++it, ++scanned) {
try_expand(node, *it, nxt);
}
} else {
const auto& list = by_from[node.city];
auto it = lower_bound(list.begin(), list.end(), node.tm,
[&](int idx, int t0) { return cand[idx].s < t0; });
int scanned = 0;
for (; it != list.end() && scanned < BEAM_SCAN_NEXT; ++it, ++scanned) {
try_expand(node, *it, nxt);
}
}
}
if (nxt.empty()) break;
sort(nxt.begin(), nxt.end(), [](const Node& a, const Node& b) {
if (a.score != b.score) return a.score > b.score;
if (a.tm != b.tm) return a.tm < b.tm;
return a.city < b.city;
});
if ((int)nxt.size() > BEAM_WIDTH) nxt.resize(BEAM_WIDTH);
beam.swap(nxt);
}
return best_first;
}
// 1機体をビームで再構築
vector<int> rebuild_plane_with_beam(
int p, const vector<vector<int>>& routes, const vector<Candidate>& cand,
const vector<int>& all_by_time, const vector<vector<int>>& by_from,
int n, int slot_cnt, const vector<FillInfo>& fill_info, XorShift64* rng = nullptr,
int keep_prefix = -1, bool diversify = false) {
(void)n;
(void)slot_cnt;
// 他機体で既に使われている候補は再利用しない
vector<char> blocked(cand.size(), 0);
for (int q = 0; q < (int)routes.size(); ++q) {
if (q == p) continue;
for (int ci : routes[q]) blocked[ci] = 1;
}
vector<int> seq;
int city = -1;
int tm = DAY_START;
// 既存ルートの前半を残して後半のみ再構築するモード
if (keep_prefix < 0) keep_prefix = 0;
keep_prefix = min(keep_prefix, (int)routes[p].size());
for (int i = 0; i < keep_prefix; ++i) {
int ci = routes[p][i];
if (blocked[ci]) break;
seq.push_back(ci);
blocked[ci] = 1;
city = cand[ci].b;
tm = cand[ci].t;
}
double rand_amp = (diversify ? 0.08 : 0.0);
int zero_streak = 0;
for (int leg = (int)seq.size(); leg < REBUILD_MAX_LEGS; ++leg) {
int ci =
beam_pick_next(city, tm, cand, all_by_time, by_from, blocked, fill_info, rng, rand_amp);
if (ci == -1) break;
const auto& c = cand[ci];
if (c.base_gain <= 0) {
++zero_streak;
} else {
zero_streak = 0;
}
if (zero_streak >= 3) break;
seq.push_back(ci);
blocked[ci] = 1;
city = c.b;
tm = c.t;
if (tm >= DAY_END) break;
}
return seq;
}
// 1機体に対する局所近傍（削除/挿入/置換/部分破壊再構築）
vector<int> mutate_plane_local(
int p, const vector<vector<int>>& routes, const vector<Candidate>& cand,
const vector<int>& all_by_time, const vector<vector<int>>& by_from,
const vector<FillInfo>& fill_info, XorShift64& rng) {
vector<int> seq = routes[p];
vector<char> blocked(cand.size(), 0), in_seq(cand.size(), 0);
for (int q = 0; q < (int)routes.size(); ++q) {
if (q == p) continue;
for (int ci : routes[q]) blocked[ci] = 1;
}
for (int ci : seq) in_seq[ci] = 1;
auto node_value = [&](const Candidate& c, int prev_tm, int prev_city) -> double {
int wait = c.s - prev_tm;
if (wait < 0) return -1e300;
double fill_bonus = 0.0;
if (prev_city != -1 && wait > 0) {
fill_bonus = estimate_fill_gain(fill_info[prev_city], wait, true);
}
return STEAL_BEAM_GAIN_WEIGHT * (double)c.base_gain + 95.0 * (double)c.edge -
2.1 * (double)wait + 32.0 * fill_bonus;
};
int op = rng.next_int(0, 4);
// 削除
if (op == 0 && !seq.empty()) {
for (int tr = 0; tr < 8; ++tr) {
int pos = rng.next_int(0, (int)seq.size() - 1);
bool ok = true;
if (pos > 0 && pos + 1 < (int)seq.size()) {
const auto& prv = cand[seq[pos - 1]];
const auto& nxt = cand[seq[pos + 1]];
if (prv.b != nxt.a || prv.t > nxt.s) ok = false;
}
if (!ok) continue;
seq.erase(seq.begin() + pos);
return seq;
}
}
// 挿入
if (op == 1 && (int)seq.size() < REBUILD_MAX_LEGS + 4) {
int g = rng.next_int(0, (int)seq.size());
int prev_city = -1, prev_tm = DAY_START;
if (g > 0) {
const auto& prv = cand[seq[g - 1]];
prev_city = prv.b;
prev_tm = prv.t;
}
int next_city = -1, next_tm = DAY_END;
bool has_next = (g < (int)seq.size());
if (has_next) {
const auto& nxt = cand[seq[g]];
next_city = nxt.a;
next_tm = nxt.s;
}
int best_ci = -1;
double best_sc = -1e300;
if (prev_city == -1) {
auto it = lower_bound(all_by_time.begin(), all_by_time.end(), prev_tm,
[&](int idx, int t0) { return cand[idx].s < t0; });
int scanned = 0;
for (; it != all_by_time.end() && scanned < BEAM_SCAN_FIRST * 2; ++it, ++scanned) {
int ci = *it;
if (blocked[ci] || in_seq[ci]) continue;
const auto& c = cand[ci];
if (has_next && (c.b != next_city || c.t > next_tm)) continue;
double sc = node_value(c, prev_tm, prev_city);
if (sc > best_sc) {
best_sc = sc;
best_ci = ci;
}
}
} else {
const auto& list = by_from[prev_city];
auto it = lower_bound(list.begin(), list.end(), prev_tm,
[&](int idx, int t0) { return cand[idx].s < t0; });
int scanned = 0;
for (; it != list.end() && scanned < BEAM_SCAN_NEXT * 3; ++it, ++scanned) {
int ci = *it;
if (blocked[ci] || in_seq[ci]) continue;
const auto& c = cand[ci];
if (has_next && (c.b != next_city || c.t > next_tm)) continue;
double sc = node_value(c, prev_tm, prev_city);
if (sc > best_sc) {
best_sc = sc;
best_ci = ci;
}
}
}
if (best_ci != -1) {
seq.insert(seq.begin() + g, best_ci);
return seq;
}
}
// 置換（同OD内で時刻を振り替える）
if (op == 2 && !seq.empty()) {
int pos = rng.next_int(0, (int)seq.size() - 1);
int old_ci = seq[pos];
const auto& old = cand[old_ci];
int prev_tm = (pos > 0 ? cand[seq[pos - 1]].t : DAY_START);
int next_tm = (pos + 1 < (int)seq.size() ? cand[seq[pos + 1]].s : DAY_END);
int best_ci = old_ci;
double best_sc = node_value(old, prev_tm, (pos > 0 ? cand[seq[pos - 1]].b : -1));
const auto& list = by_from[old.a];
auto it = lower_bound(list.begin(), list.end(), max(prev_tm, old.s - 120),
[&](int idx, int t0) { return cand[idx].s < t0; });
int scanned = 0;
for (; it != list.end() && scanned < BEAM_SCAN_NEXT * 4; ++it, ++scanned) {
int ci = *it;
const auto& c = cand[ci];
if (c.s > old.s + 120) break;
if (c.b != old.b) continue;
if (ci != old_ci && (blocked[ci] || in_seq[ci])) continue;
if (c.s < prev_tm || c.t > next_tm) continue;
double sc = node_value(c, prev_tm, (pos > 0 ? cand[seq[pos - 1]].b : -1));
if (sc > best_sc) {
best_sc = sc;
best_ci = ci;
}
}
if (best_ci != old_ci) {
seq[pos] = best_ci;
return seq;
}
}
// 部分破壊再構築（局所解脱出）
if (op == 3) {
int keep = 0;
if (!seq.empty()) keep = rng.next_int(0, min((int)seq.size(), 3));
return rebuild_plane_with_beam(p, routes, cand, all_by_time, by_from, 0, 0, fill_info, &rng,
keep, true);
}
// 大きいジャンプ（丸ごと再構築）
return rebuild_plane_with_beam(p, routes, cand, all_by_time, by_from, 0, 0, fill_info, &rng, 0,
true);
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
auto global_start = chrono::steady_clock::now();
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;
vector<Flight> square;
square.reserve(M);
for (int i = 0; i < M; ++i) {
int a, b;
string s_tok, t_tok;
cin >> a >> s_tok >> b >> t_tok;
int s = parse_time(s_tok);
int t = parse_time(t_tok);
square.push_back(Flight{a - 1, b - 1, s, t});
}
int K;
cin >> K;
vector<int> deadlines = build_deadlines();
int SLOT_CNT = (DAY_END - DAY_START) / SLOT_STEP + 1;
// 直行所要時間
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;
long double dx = (long double)x[i] - (long double)x[j];
long double dy = (long double)y[i] - (long double)y[j];
long double d = sqrtl(dx * dx + dy * dy);
dur[i][j] = calc_duration_min(d);
}
}
// スクエア便密度
vector<vector<int>> sq_edge_count(N, vector<int>(N, 0));
for (const auto& f : square) sq_edge_count[f.a][f.b]++;
// 探索中の待機埋め近似で使う都市ごとの埋めやすさ指標
vector<FillInfo> fill_info(N);
for (int a = 0; a < N; ++a) {
long double best_one_ratio = -1.0L;
long double best_rt_ratio = -1.0L;
for (int b = 0; b < N; ++b) {
if (a == b) continue;
int d1 = dur[a][b];
int e1 = sq_edge_count[a][b];
if (d1 > 0) {
long double r1 = (long double)e1 / (long double)d1;
if (r1 > best_one_ratio ||
(fabsl(r1 - best_one_ratio) < 1e-18L && d1 < fill_info[a].one_time)) {
best_one_ratio = r1;
fill_info[a].one_time = d1;
fill_info[a].one_edge = e1;
}
}
int d2 = dur[b][a];
int rt = d1 + d2;
int er = sq_edge_count[a][b] + sq_edge_count[b][a];
if (rt > 0) {
long double rr = (long double)er / (long double)rt;
if (rr > best_rt_ratio ||
(fabsl(rr - best_rt_ratio) < 1e-18L && rt < fill_info[a].rt_time)) {
best_rt_ratio = rr;
fill_info[a].rt_time = rt;
fill_info[a].rt_edge = er;
}
}
}
}
// 評価対象ODと人口積
vector<vector<char>> valid_pair(N, vector<char>(N, 0));
vector<vector<ll>> pair_w(N, vector<ll>(N, 0));
vector<pair<int, int>> eval_pairs;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (i == j) continue;
long double dx = (long double)x[i] - (long double)x[j];
long double dy = (long double)y[i] - (long double)y[j];
long double d = sqrtl(dx * dx + dy * dy);
if (d + 1e-12L >= 0.25L * (long double)R) {
valid_pair[i][j] = 1;
pair_w[i][j] = w[i] * w[j];
eval_pairs.push_back({i, j});
}
}
}
// スクエア側の最遅出発時刻
auto latest_sq = build_latest_tensor(N, square, deadlines);
// 候補便生成（スクエアOD + 近距離OD）
vector<Candidate> cand;
cand.reserve(M * 9 + N * 8 * 120);
const int shifts[9] = {0, 5, 10, 15, 20, 25, 30, 35, 40};
for (const auto& f : square) {
int a = f.a, b = f.b;
int d = dur[a][b];
for (int sh : shifts) {
int s = f.s + sh;
int t = s + d;
if (s < DAY_START || t > DAY_END) continue;
uint32_t mask = 0;
if (valid_pair[a][b]) {
for (int k = 0; k < DEADLINE_COUNT; ++k) {
if (t > deadlines[k]) continue;
if (s > latest_sq[k][b][a]) mask |= (1u << k);
}
}
ll pw = pair_w[a][b];
ll bg = pw * (ll)__builtin_popcount(mask);
cand.push_back(Candidate{a, b, s, t, sq_edge_count[a][b], mask, pw, bg});
}
}
// 待機活用のため、各都市から近い都市への便も候補に入れる
for (int a = 0; a < N; ++a) {
vector<pair<int, int>> near;
near.reserve(N - 1);
for (int b = 0; b < N; ++b) {
if (a == b) continue;
near.push_back({dur[a][b], b});
}
sort(near.begin(), near.end());
int use = min((int)near.size(), NEAR_PER_CITY);
for (int z = 0; z < use; ++z) {
int b = near[z].second;
int d = dur[a][b];
// あまり長い便は待機埋め用途としては使いにくいので除外
if (d > 120) continue;
for (int s = DAY_START; s + d <= DAY_END; s += NEAR_TIME_STEP) {
int t = s + d;
uint32_t mask = 0;
if (valid_pair[a][b]) {
for (int k = 0; k < DEADLINE_COUNT; ++k) {
if (t > deadlines[k]) continue;
if (s > latest_sq[k][b][a]) mask |= (1u << k);
}
}
ll pw = pair_w[a][b];
ll bg = pw * (ll)__builtin_popcount(mask);
cand.push_back(Candidate{a, b, s, t, sq_edge_count[a][b], mask, pw, bg});
}
}
}
// 重複除去
sort(cand.begin(), cand.end(), [](const Candidate& p, const Candidate& q) {
return tie(p.a, p.b, p.s) < tie(q.a, q.b, q.s);
});
cand.erase(unique(cand.begin(), cand.end(), [](const Candidate& p, const Candidate& q) {
return p.a == q.a && p.b == q.b && p.s == q.s;
}),
cand.end());
// 候補便の索引
vector<vector<int>> by_from(N);
vector<int> all_by_time;
all_by_time.reserve(cand.size());
for (int i = 0; i < (int)cand.size(); ++i) {
by_from[cand[i].a].push_back(i);
all_by_time.push_back(i);
}
for (int a = 0; a < N; ++a) {
sort(by_from[a].begin(), by_from[a].end(), [&](int i, int j) {
return cand[i].s < cand[j].s;
});
}
sort(all_by_time.begin(), all_by_time.end(), [&](int i, int j) {
return cand[i].s < cand[j].s;
});
// 初期解: 増分奪取を主軸にした全体貪欲
vector<vector<int>> routes(K);
vector<PlaneState> ps(K);
vector<vector<uint32_t>> won_mask(N, vector<uint32_t>(N, 0));
vector<char> used_ci(cand.size(), 0);
auto incremental_gain = [&](const Candidate& c) -> ll {
if (c.pair_w == 0 || c.mask == 0) return 0;
uint32_t add_bits = c.mask & (~won_mask[c.a][c.b]);
if (add_bits == 0) return 0;
return c.pair_w * (ll)__builtin_popcount(add_bits);
};
auto future_gain_from = [&](int city, int tm) -> ll {
const auto& list = by_from[city];
auto it = lower_bound(list.begin(), list.end(), tm,
[&](int idx, int t0) { return cand[idx].s < t0; });
ll best = 0;
int checked = 0;
for (; it != list.end(); ++it) {
int ci = *it;
if (used_ci[ci]) continue;
const auto& c = cand[ci];
if (c.s > tm + FUTURE_HORIZON) break;
if (++checked > FUTURE_SCAN_MAX) break;
ll g = incremental_gain(c);
if (g > best) best = g;
}
return best;
};
while (true) {
ll best_gain = 0;
int best_wait = 1e9;
int best_edge = -1;
int best_p = -1;
int best_ci = -1;
ll best_move_future = 0;
int best_move_wait = 1e9;
int best_move_edge = -1;
int best_move_p = -1;
int best_move_ci = -1;
int first_inactive = -1;
for (int p = 0; p < K; ++p) {
if (!ps[p].active) {
first_inactive = p;
break;
}
}
// 未使用機体の初手候補は1回だけ評価する
if (first_inactive != -1) {
int scanned = 0;
for (int idx : all_by_time) {
if (used_ci[idx]) continue;
const auto& c = cand[idx];
int wait = c.s - DAY_START;
if (wait < 0) continue;
if (wait > WAIT_FIRST_MAX) break;
if (++scanned > INIT_SCAN_MAX) break;
ll gain = incremental_gain(c);
if (gain > 0) {
if (gain > best_gain ||
(gain == best_gain && wait < best_wait) ||
(gain == best_gain && wait == best_wait && c.edge > best_edge)) {
best_gain = gain;
best_wait = wait;
best_edge = c.edge;
best_p = first_inactive;
best_ci = idx;
}
} else {
if (c.mask != 0) continue;
if (wait > ZERO_WAIT_ALLOW) continue;
if (c.edge == 0) continue;
ll fut = future_gain_from(c.b, c.t);
if (fut <= 0) continue;
if (fut > best_move_future ||
(fut == best_move_future && wait < best_move_wait) ||
(fut == best_move_future && wait == best_move_wait &&
c.edge > best_move_edge)) {
best_move_future = fut;
best_move_wait = wait;
best_move_edge = c.edge;
best_move_p = first_inactive;
best_move_ci = idx;
}
}
}
}
// 使用中機体の次手候補を評価
for (int p = 0; p < K; ++p) {
if (!ps[p].active) continue;
int cur = ps[p].city;
int tm = ps[p].tm;
const auto& list = by_from[cur];
auto it = lower_bound(list.begin(), list.end(), tm,
[&](int idx, int t0) { return cand[idx].s < t0; });
int scanned = 0;
for (; it != list.end() && scanned < ACTIVE_SCAN_MAX; ++it, ++scanned) {
int ci = *it;
if (used_ci[ci]) continue;
const auto& c = cand[ci];
int wait = c.s - tm;
if (wait > ACTIVE_WAIT_HORIZON) break;
ll gain = incremental_gain(c);
if (gain > 0) {
if (gain > best_gain ||
(gain == best_gain && wait < best_wait) ||
(gain == best_gain && wait == best_wait && c.edge > best_edge)) {
best_gain = gain;
best_wait = wait;
best_edge = c.edge;
best_p = p;
best_ci = ci;
}
} else {
if (c.mask != 0) continue;
if (wait < 0 || wait > ZERO_WAIT_ALLOW) continue;
if (c.edge == 0) continue;
ll fut = future_gain_from(c.b, c.t);
if (fut <= 0) continue;
if (fut > best_move_future ||
(fut == best_move_future && wait < best_move_wait) ||
(fut == best_move_future && wait == best_move_wait &&
c.edge > best_move_edge)) {
best_move_future = fut;
best_move_wait = wait;
best_move_edge = c.edge;
best_move_p = p;
best_move_ci = ci;
}
}
}
}
int pick_p = -1;
int pick_ci = -1;
ll pick_gain = 0;
if (best_p != -1 && best_ci != -1 && best_gain > 0) {
// 奪取優先: 将来見込みが極端に高い場合のみ0奪取移動を許可
if (best_move_p != -1 && best_move_ci != -1 &&
best_move_future * MOVE_OVERRIDE_NUM >= best_gain * MOVE_OVERRIDE_DEN) {
pick_p = best_move_p;
pick_ci = best_move_ci;
pick_gain = 0;
} else {
pick_p = best_p;
pick_ci = best_ci;
pick_gain = best_gain;
}
} else if (best_move_p != -1 && best_move_ci != -1) {
pick_p = best_move_p;
pick_ci = best_move_ci;
pick_gain = 0;
} else {
break;
}
const auto& c = cand[pick_ci];
if (!ps[pick_p].active) ps[pick_p].active = true;
ps[pick_p].city = c.b;
ps[pick_p].tm = c.t;
routes[pick_p].push_back(pick_ci);
used_ci[pick_ci] = 1;
if (pick_gain > 0) {
won_mask[c.a][c.b] |= c.mask;
}
}
// 焼きなまし: 1機体をビーム再構築して採用可否を温度で判定
auto start_tp = chrono::steady_clock::now();
XorShift64 rng(123456789ULL);
ll cur_score = calc_exact_score(routes, cand, N, deadlines, latest_sq, eval_pairs, pair_w);
vector<vector<int>> best_routes = routes;
ll best_score = cur_score;
vector<double> fast_plane(K, 0.0), wait_plane(K, 0.0);
double fast_total = 0.0, wait_total = 0.0;
for (int p = 0; p < K; ++p) {
fast_plane[p] = calc_plane_fast_score(routes[p], cand, fill_info);
wait_plane[p] = calc_plane_wait_fill_score(routes[p], cand, fill_info);
fast_total += fast_plane[p];
wait_total += wait_plane[p];
}
double best_wait_total = wait_total;
long double t0 = max(1.0L, fabsl((long double)cur_score) * 0.02L);
long double t1 = max(1.0L, fabsl((long double)cur_score) * 1e-6L);
long double ft0 = max(1.0L, fabsl((long double)fast_total) * 0.03L);
long double ft1 = max(1.0L, fabsl((long double)fast_total) * 1e-5L);
int stagnate = 0;
double pre_elapsed =
chrono::duration<double>(chrono::steady_clock::now() - global_start).count();
double sa_budget = min(SA_MAX_TIME_SEC, TOTAL_TIME_LIMIT_SEC - pre_elapsed - SA_MARGIN_SEC);
if (sa_budget < 0.0) sa_budget = 0.0;
while (sa_budget > 0.0) {
double elapsed = chrono::duration<double>(chrono::steady_clock::now() - start_tp).count();
if (elapsed >= sa_budget) break;
int p = rng.next_int(0, K - 1);
vector<vector<int>> nxt_routes = routes;
int mode = rng.next_int(0, 99);
if (stagnate >= STAGNATE_LIMIT && rng.next_int(0, 99) < 50) mode = 99;
if (mode < 38) {
nxt_routes[p] = rebuild_plane_with_beam(p, routes, cand, all_by_time, by_from, N,
SLOT_CNT, fill_info, &rng, 0, false);
} else if (mode < 83) {
nxt_routes[p] =
mutate_plane_local(p, routes, cand, all_by_time, by_from, fill_info, rng);
} else {
int keep = 0;
if (!routes[p].empty()) keep = rng.next_int(0, min((int)routes[p].size(), 3));
nxt_routes[p] = rebuild_plane_with_beam(p, routes, cand, all_by_time, by_from, N,
SLOT_CNT, fill_info, &rng, keep, true);
}
if (nxt_routes[p] == routes[p]) continue;
// 差分評価: 変更機体 p だけ高速再評価して悪手を先に間引く
double nxt_fast_p = calc_plane_fast_score(nxt_routes[p], cand, fill_info);
double delta_fast = nxt_fast_p - fast_plane[p];
double nxt_wait_p = calc_plane_wait_fill_score(nxt_routes[p], cand, fill_info);
double delta_wait = nxt_wait_p - wait_plane[p];
if (delta_fast < 0.0) {
long double rf = (long double)elapsed / (long double)sa_budget;
long double ftemp = ft0 * pow((double)(ft1 / ft0), (double)rf);
long double fprob = expl((long double)delta_fast / (FAST_SKIP_COEF * ftemp));
if (fprob < (long double)rng.next_double()) {
++stagnate;
continue;
}
}
ll nxt_score =
calc_exact_score(nxt_routes, cand, N, deadlines, latest_sq, eval_pairs, pair_w);
ll delta = nxt_score - cur_score;
long double delta_aug = (long double)delta + (long double)(WAIT_AUG_WEIGHT * delta_wait);
bool accept = false;
if (delta_aug >= 0) {
accept = true;
} else {
long double r = (long double)elapsed / (long double)sa_budget;
long double temp = t0 * pow((double)(t1 / t0), (double)r);
long double prob = expl((long double)delta_aug / temp);
if (prob > (long double)rng.next_double()) accept = true;
}
if (accept) {
routes.swap(nxt_routes);
cur_score = nxt_score;
fast_total += delta_fast;
wait_total += delta_wait;
fast_plane[p] = nxt_fast_p;
wait_plane[p] = nxt_wait_p;
if (cur_score > best_score || (cur_score == best_score && wait_total > best_wait_total)) {
best_score = cur_score;
best_routes = routes;
best_wait_total = wait_total;
stagnate = 0;
} else {
++stagnate;
}
} else {
++stagnate;
}
}
// 探索後に、寄与のない奪取便を削って待機埋めの余地を作る
prune_redundant_won_routes(best_routes, cand, N);
// 探索内最適化に加えて、出力前にも隙間埋め後処理を適用
int busy_city = pick_busy_city(sq_edge_count);
vector<vector<Flight>> final_flights(K);
unordered_set<uint64_t> used_keys;
used_keys.reserve(cand.size() * 2 + 4096);
// コア便を先に予約し、後から入れる埋め便との衝突を防ぐ
for (int p = 0; p < K; ++p) {
for (int ci : best_routes[p]) {
const auto& c = cand[ci];
used_keys.insert(flight_key(c.a, c.b, c.s));
}
}
for (int p = 0; p < K; ++p) {
int fallback_city = busy_city;
if (!best_routes[p].empty()) {
fallback_city = cand[best_routes[p][0]].a;
}
final_flights[p] =
densify_route(best_routes[p], cand, dur, sq_edge_count, fallback_city, used_keys);
}
for (int p = 0; p < K; ++p) {
cout << final_flights[p].size() << '\n';
for (const auto& f : final_flights[p]) {
cout << (f.a + 1) << ' ' << to_hhmm(f.s) << ' ' << (f.b + 1) << ' ' << to_hhmm(f.t)
<< '\n';
}
}
return 0;
}