結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 ぬるぽ
|
| 提出日時 | 2026-02-27 21:53:32 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 24,225 bytes |
| 記録 | |
| コンパイル時間 | 4,611 ms |
| コンパイル使用メモリ | 295,552 KB |
| 実行使用メモリ | 7,976 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2026-02-27 21:56:54 |
| 合計ジャッジ時間 | 200,399 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge7 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | TLE * 100 |
ソースコード
#include <algorithm>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
using namespace std;
struct XorShift64 {
uint64_t x = 88172645463325252ULL;
uint64_t next() {
x ^= x << 7;
x ^= x >> 9;
return x;
}
uint64_t next(uint64_t mod) {
if (mod == 0) return 0;
return next() % mod;
}
double next_double() {
return static_cast<double>(next()) / static_cast<double>(numeric_limits<uint64_t>::max());
}
};
struct Timer {
chrono::steady_clock::time_point start = chrono::steady_clock::now();
double elapsed_sec() const {
const auto now = chrono::steady_clock::now();
return chrono::duration<double>(now - start).count();
}
};
struct Flight {
int from = -1;
int to = -1;
int dep = -1;
int arr = -1;
bool operator==(const Flight& other) const = default;
};
struct EvalResult {
double metric = 0.0; // approx contest score: 1e6 * share
unsigned long long win_weight = 0;
vector<vector<unsigned long long>> loss_pair_weight;
};
struct State {
vector<vector<Flight>> planes;
EvalResult eval;
};
class Solver {
public:
void solve() {
read_input();
precompute();
timer_ = Timer();
State current = build_initial_state();
State best = current;
const double start_temp = 3000.0;
const double end_temp = 20.0;
long long iterations = 0;
long long accepted = 0;
while (timer_.elapsed_sec() < kTimeLimitSec - 0.01) {
iterations++;
State candidate;
if (!propose_neighbor(current, candidate)) {
continue;
}
candidate.eval = evaluate(candidate.planes);
const double diff = candidate.eval.metric - current.eval.metric;
const double progress = min(1.0, timer_.elapsed_sec() / kTimeLimitSec);
const double temp = start_temp * pow(end_temp / start_temp, progress);
bool accept = false;
if (diff >= 0.0) {
accept = true;
} else {
const double prob = exp(diff / max(1e-9, temp));
accept = (rng_.next_double() < prob);
}
if (accept) {
accepted++;
current = std::move(candidate);
if (current.eval.metric > best.eval.metric) {
best = current;
}
}
}
output_state(best);
cerr << fixed << setprecision(2)
<< "[info] iters=" << iterations
<< " accepted=" << accepted
<< " final=" << current.eval.metric
<< " best=" << best.eval.metric
<< " time=" << timer_.elapsed_sec() << "s\n";
}
private:
static constexpr int kStartMin = 6 * 60;
static constexpr int kEndMin = 21 * 60;
static constexpr int kNegInf = -1'000'000'000;
static constexpr double kTimeLimitSec = 1.9;
int N_ = 0;
int R_ = 0;
int M_ = 0;
int K_ = 0;
vector<int> xs_;
vector<int> ys_;
vector<unsigned long long> ws_;
vector<Flight> square_flights_;
vector<vector<double>> dist_;
vector<vector<int>> dur_;
vector<vector<char>> eligible_pair_;
vector<int> target_times_; // 11:00..21:00, 30-min step
unsigned long long total_weight_ = 0;
vector<int> square_latest_; // flattened [q][dst][src]
XorShift64 rng_;
Timer timer_;
static string strip_bom(string s) {
if (s.size() >= 3) {
const unsigned char b0 = static_cast<unsigned char>(s[0]);
const unsigned char b1 = static_cast<unsigned char>(s[1]);
const unsigned char b2 = static_cast<unsigned char>(s[2]);
if (b0 == 0xEF && b1 == 0xBB && b2 == 0xBF) {
return s.substr(3);
}
}
return s;
}
static int parse_time(const string& s) {
// "HH:MM"
const int hh = stoi(s.substr(0, 2));
const int mm = stoi(s.substr(3, 2));
return hh * 60 + mm;
}
static string format_time(int minutes) {
const int hh = minutes / 60;
const int mm = minutes % 60;
ostringstream oss;
oss << setfill('0') << setw(2) << hh << ":" << setw(2) << mm;
return oss.str();
}
int latest_idx(int q, int dst, int src) const {
return (q * N_ + dst) * N_ + src;
}
int calc_flight_duration(int i, int j) const {
if (i == j) return 0;
const double dx = static_cast<double>(xs_[i] - xs_[j]);
const double dy = static_cast<double>(ys_[i] - ys_[j]);
const double d = sqrt(dx * dx + dy * dy);
const double raw = 60.0 * d / 800.0 + 40.0;
const int dur = static_cast<int>(ceil((raw - 1e-12) / 5.0)) * 5;
return dur;
}
void read_input() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string first;
cin >> first;
first = strip_bom(first);
N_ = stoi(first);
cin >> R_;
xs_.resize(N_);
ys_.resize(N_);
ws_.resize(N_);
for (int i = 0; i < N_; i++) {
cin >> xs_[i] >> ys_[i] >> ws_[i];
}
cin >> M_;
square_flights_.reserve(M_);
for (int i = 0; i < M_; i++) {
int a, b;
string s, t;
cin >> a >> s >> b >> t;
--a;
--b;
square_flights_.push_back(Flight{a, b, parse_time(s), parse_time(t)});
}
cin >> K_;
}
void precompute() {
dist_.assign(N_, vector<double>(N_, 0.0));
dur_.assign(N_, vector<int>(N_, 0));
eligible_pair_.assign(N_, vector<char>(N_, 0));
const double threshold = 0.25 * static_cast<double>(R_);
for (int i = 0; i < N_; i++) {
for (int j = 0; j < N_; j++) {
const double dx = static_cast<double>(xs_[i] - xs_[j]);
const double dy = static_cast<double>(ys_[i] - ys_[j]);
const double d = sqrt(dx * dx + dy * dy);
dist_[i][j] = d;
dur_[i][j] = calc_flight_duration(i, j);
if (d >= threshold - 1e-12) {
eligible_pair_[i][j] = 1;
}
}
}
target_times_.clear();
for (int t = 11 * 60; t <= 21 * 60; t += 30) {
target_times_.push_back(t);
}
total_weight_ = 0;
for (int i = 0; i < N_; i++) {
for (int j = 0; j < N_; j++) {
if (!eligible_pair_[i][j]) continue;
const unsigned long long w = ws_[i] * ws_[j];
for (int q = 0; q < static_cast<int>(target_times_.size()); q++) {
(void)q;
total_weight_ += w;
}
}
}
square_latest_ = compute_latest_departure(square_flights_);
}
vector<int> compute_latest_departure(const vector<Flight>& flights) const {
vector<Flight> sorted = flights;
sort(sorted.begin(), sorted.end(), [](const Flight& a, const Flight& b) {
if (a.dep != b.dep) return a.dep > b.dep;
return a.arr > b.arr;
});
const int Q = static_cast<int>(target_times_.size());
vector<int> latest(Q * N_ * N_, kNegInf);
vector<int> dp(N_, kNegInf);
for (int q = 0; q < Q; q++) {
const int deadline = target_times_[q];
for (int dst = 0; dst < N_; dst++) {
fill(dp.begin(), dp.end(), kNegInf);
dp[dst] = deadline;
for (const Flight& f : sorted) {
if (f.arr <= dp[f.to]) {
dp[f.from] = max(dp[f.from], f.dep);
}
}
for (int src = 0; src < N_; src++) {
latest[latest_idx(q, dst, src)] = dp[src];
}
}
}
return latest;
}
EvalResult evaluate(const vector<vector<Flight>>& planes) const {
vector<Flight> all;
size_t total_legs = 0;
for (const auto& plane : planes) total_legs += plane.size();
all.reserve(total_legs);
for (const auto& plane : planes) {
for (const Flight& f : plane) {
all.push_back(f);
}
}
const vector<int> circle_latest = compute_latest_departure(all);
EvalResult res;
res.loss_pair_weight.assign(N_, vector<unsigned long long>(N_, 0));
unsigned long long win = 0;
const int Q = static_cast<int>(target_times_.size());
for (int src = 0; src < N_; src++) {
for (int dst = 0; dst < N_; dst++) {
if (!eligible_pair_[src][dst]) continue;
const unsigned long long w = ws_[src] * ws_[dst];
for (int q = 0; q < Q; q++) {
const int sq = square_latest_[latest_idx(q, dst, src)];
const int ci = circle_latest[latest_idx(q, dst, src)];
if (sq < ci) {
win += w;
} else {
res.loss_pair_weight[src][dst] += w;
}
}
}
}
res.win_weight = win;
if (total_weight_ == 0) {
res.metric = 0.0;
} else {
res.metric = static_cast<double>(
(static_cast<long double>(win) * 1'000'000.0L) /
static_cast<long double>(total_weight_)
);
}
return res;
}
bool validate_plane(const vector<Flight>& plane) const {
for (int i = 0; i < static_cast<int>(plane.size()); i++) {
const Flight& f = plane[i];
if (f.from < 0 || f.from >= N_ || f.to < 0 || f.to >= N_ || f.from == f.to) return false;
if (f.dep < kStartMin || f.dep > kEndMin || f.arr < kStartMin || f.arr > kEndMin) return false;
if (f.dep % 5 != 0 || f.arr % 5 != 0) return false;
if (f.arr - f.dep != dur_[f.from][f.to]) return false;
if (f.arr < f.dep) return false;
if (i > 0) {
const Flight& prev = plane[i - 1];
if (prev.to != f.from) return false;
if (prev.arr > f.dep) return false;
}
}
return true;
}
int pick_weighted_index(const vector<double>& weights) {
double sum = 0.0;
int fallback = -1;
for (int i = 0; i < static_cast<int>(weights.size()); i++) {
if (weights[i] > 0.0) {
sum += weights[i];
fallback = i;
}
}
if (fallback < 0) {
return static_cast<int>(rng_.next(weights.size()));
}
const double r = rng_.next_double() * sum;
double acc = 0.0;
for (int i = 0; i < static_cast<int>(weights.size()); i++) {
if (weights[i] <= 0.0) continue;
acc += weights[i];
if (acc >= r) return i;
}
return fallback;
}
int choose_start_city(const EvalResult& eval) {
vector<unsigned long long> row_loss(N_, 0);
unsigned long long max_row = 1;
for (int i = 0; i < N_; i++) {
unsigned long long s = 0;
for (int j = 0; j < N_; j++) s += eval.loss_pair_weight[i][j];
row_loss[i] = s;
max_row = max(max_row, s);
}
vector<double> weights(N_, 0.0);
for (int i = 0; i < N_; i++) {
const double row_ratio = static_cast<double>(row_loss[i]) / static_cast<double>(max_row);
weights[i] = static_cast<double>(ws_[i]) * (1.0 + 3.0 * row_ratio);
}
return pick_weighted_index(weights);
}
struct MoveCandidate {
bool stop = false;
int to = -1;
int dep = -1;
int arr = -1;
double weight = 0.0;
};
vector<MoveCandidate> make_move_candidates(
int city,
int now,
int depth,
bool has_target,
int target_city,
int target_time,
bool force_direct,
const EvalResult& eval,
unsigned long long max_loss
) {
vector<MoveCandidate> cands;
const int limit = has_target ? target_time : kEndMin;
const double threshold = 0.25 * static_cast<double>(R_);
if (!has_target && depth >= 1) {
// 非目標区間はある程度伸びたら終了候補も許可
const double stop_w = 0.3 + 0.1 * min(depth, 6);
cands.push_back(MoveCandidate{true, -1, -1, -1, stop_w});
}
static const int waits[] = {0, 5, 10, 15, 20, 30};
const int to_begin = force_direct ? target_city : 0;
const int to_end = force_direct ? target_city + 1 : N_;
for (int to = to_begin; to < to_end; to++) {
if (to == city) continue;
const int d = dur_[city][to];
if (now + d > limit) continue;
for (int wait : waits) {
const int dep = now + wait;
const int arr = dep + d;
if (arr > limit) continue;
if (dep > kEndMin || arr > kEndMin) continue;
if (has_target) {
// 三角不等式 + 固定オーバーヘッドより、直行が最短時間近似として十分強い。
if (arr + dur_[to][target_city] > target_time) {
continue;
}
}
const long double pop_score = static_cast<long double>(ws_[city]) * static_cast<long double>(ws_[to]);
const double loss_ratio = static_cast<double>(eval.loss_pair_weight[city][to]) /
static_cast<double>(max_loss);
const double loss_score = 1.0 + 5.0 * loss_ratio;
const double wait_score = 1.0 / (1.0 + static_cast<double>(wait) / 5.0);
double dist_score = 1.0;
if (dist_[city][to] >= threshold) {
dist_score = threshold / dist_[city][to];
}
double target_score = 1.0;
if (has_target) {
const double d_goal = dist_[to][target_city];
target_score = 1.0 + threshold / (threshold + d_goal);
if (to == target_city) target_score *= 1.8;
}
double weight = static_cast<double>(pop_score) * loss_score * wait_score * dist_score * target_score;
if (weight <= 0.0) weight = 1e-9;
cands.push_back(MoveCandidate{false, to, dep, arr, weight});
}
}
return cands;
}
bool build_route_segment(
int start_city,
int start_time,
bool has_target,
int target_city,
int target_time,
const EvalResult& eval,
int max_depth,
int max_nodes,
vector<Flight>& out
) {
out.clear();
vector<Flight> path;
unsigned long long max_loss = 1;
for (int i = 0; i < N_; i++) {
for (int j = 0; j < N_; j++) {
max_loss = max(max_loss, eval.loss_pair_weight[i][j]);
}
}
int visited_nodes = 0;
function<bool(int, int, int)> dfs = [&](int city, int now, int depth) -> bool {
const double remain_global = kTimeLimitSec - timer_.elapsed_sec();
if (remain_global < 0.015) {
if (has_target) {
if (city == target_city && now <= target_time) return true;
const int dep = now;
const int arr = dep + dur_[city][target_city];
if (dep <= kEndMin && arr <= target_time && arr <= kEndMin) {
path.push_back(Flight{city, target_city, dep, arr});
return true;
}
return false;
}
return true;
}
if (has_target) {
if (city == target_city && now <= target_time) return true;
if (now > target_time) return false;
if (now + dur_[city][target_city] > target_time) return false;
} else {
if (now >= kEndMin - 5) return true;
if (depth >= max_depth) return true;
}
if (visited_nodes++ >= max_nodes) {
if (has_target) {
return city == target_city && now <= target_time;
}
return true;
}
bool force_direct = false;
if (has_target) {
const int rem = target_time - now;
if (rem <= dur_[city][target_city] + 10 || remain_global < 0.04) {
force_direct = true;
}
} else {
if (remain_global < 0.03) {
return true;
}
}
vector<MoveCandidate> cands = make_move_candidates(
city,
now,
depth,
has_target,
target_city,
target_time,
force_direct,
eval,
max_loss
);
if (cands.empty()) {
return !has_target;
}
while (!cands.empty()) {
vector<double> weights;
weights.reserve(cands.size());
for (const auto& c : cands) weights.push_back(c.weight);
const int pick = pick_weighted_index(weights);
const MoveCandidate cand = cands[pick];
cands[pick] = cands.back();
cands.pop_back();
if (cand.stop) {
if (!has_target) return true;
continue;
}
path.push_back(Flight{city, cand.to, cand.dep, cand.arr});
if (dfs(cand.to, cand.arr, depth + 1)) {
return true;
}
path.pop_back();
}
return false;
};
const bool ok = dfs(start_city, start_time, 0);
if (ok) {
out = std::move(path);
}
return ok;
}
State build_initial_state() {
State state;
state.planes.assign(K_, {});
state.eval = evaluate(state.planes); // empty schedule baseline
for (int p = 0; p < K_; p++) {
vector<Flight> route;
bool ok = false;
for (int trial = 0; trial < 8; trial++) {
const int start_city = choose_start_city(state.eval);
const int max_depth = 8 + static_cast<int>(rng_.next(8));
ok = build_route_segment(
start_city,
kStartMin,
false,
-1,
-1,
state.eval,
max_depth,
1200,
route
);
if (ok && !route.empty()) break;
}
if (!ok || route.empty()) {
// Fallback: 単発1便
const int a = choose_start_city(state.eval);
int b = -1;
for (int i = 0; i < N_; i++) {
if (i == a) continue;
if (kStartMin + dur_[a][i] > kEndMin) continue;
if (b < 0 || ws_[i] > ws_[b]) b = i;
}
if (b < 0) {
b = (a + 1) % N_;
}
route.push_back(Flight{a, b, kStartMin, kStartMin + dur_[a][b]});
}
if (!validate_plane(route)) {
// 万一の保険
const int a = 0;
const int b = 1 % N_;
route.clear();
route.push_back(Flight{a, b, kStartMin, kStartMin + dur_[a][b]});
}
state.planes[p] = std::move(route);
state.eval = evaluate(state.planes);
}
return state;
}
bool propose_neighbor(const State& current, State& out) {
out = current;
for (int attempt = 0; attempt < 10; attempt++) {
const int p = static_cast<int>(rng_.next(K_));
const vector<Flight>& base = current.planes[p];
const int m = static_cast<int>(base.size());
int l = 0;
int r = m;
bool keep_suffix = false;
const int mode_roll = static_cast<int>(rng_.next(100));
if (m == 0 || mode_roll < 25) {
// 全破壊
l = 0;
r = m;
keep_suffix = false;
} else if (mode_roll < 60) {
// 後半を再構築
l = static_cast<int>(rng_.next(m + 1));
r = m;
keep_suffix = false;
} else {
// 中区間を再構築して後続へ接続
l = static_cast<int>(rng_.next(m + 1));
if (l == m) l = m - 1;
int len = 1 + static_cast<int>(rng_.next(max(1, m - l)));
r = min(m, l + len);
keep_suffix = (r < m) && (rng_.next(100) < 75);
}
vector<Flight> prefix(base.begin(), base.begin() + l);
vector<Flight> suffix;
if (keep_suffix) {
suffix.assign(base.begin() + r, base.end());
}
int start_city = -1;
int start_time = -1;
if (!prefix.empty()) {
start_city = prefix.back().to;
start_time = prefix.back().arr;
} else {
const bool reuse_original_start = (!base.empty() && rng_.next(100) < 40);
start_city = reuse_original_start ? base.front().from : choose_start_city(current.eval);
start_time = kStartMin;
}
bool has_target = false;
int target_city = -1;
int target_time = -1;
if (!suffix.empty()) {
has_target = true;
target_city = suffix.front().from;
target_time = suffix.front().dep;
}
vector<Flight> middle;
const int max_depth = has_target ? 12 : (8 + static_cast<int>(rng_.next(8)));
const int max_nodes = has_target ? 1600 : 1200;
const bool ok = build_route_segment(
start_city,
start_time,
has_target,
target_city,
target_time,
current.eval,
max_depth,
max_nodes,
middle
);
if (!ok) continue;
vector<Flight> merged;
merged.reserve(prefix.size() + middle.size() + suffix.size());
for (const auto& f : prefix) merged.push_back(f);
for (const auto& f : middle) merged.push_back(f);
for (const auto& f : suffix) merged.push_back(f);
if (merged.empty()) continue;
if (!validate_plane(merged)) continue;
if (merged == base) continue;
out.planes[p] = std::move(merged);
return true;
}
return false;
}
void output_state(const State& state) const {
for (int p = 0; p < K_; p++) {
const auto& route = state.planes[p];
cout << route.size() << '\n';
for (const Flight& f : route) {
cout << (f.from + 1) << ' '
<< format_time(f.dep) << ' '
<< (f.to + 1) << ' '
<< format_time(f.arr) << '\n';
}
}
}
};
int main() {
Solver solver;
solver.solve();
return 0;
}