結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 Shymohn _
|
| 提出日時 | 2026-02-26 00:23:16 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 995 ms / 1,000 ms |
| コード長 | 16,070 bytes |
| 記録 | |
| コンパイル時間 | 6,410 ms |
| コンパイル使用メモリ | 373,540 KB |
| 実行使用メモリ | 7,848 KB |
| スコア | 42,627,133 |
| 最終ジャッジ日時 | 2026-02-26 00:25:08 |
| 合計ジャッジ時間 | 111,998 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge7 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
/*
Extended version: if a sequence has remaining time before DAY_END, extend it
by adding further cities (weighted by population) until no further leg fits.
Based on previous simulated annealing implementation that optimizes sequences
of cities per plane. Keeps previous features: compress sequences to avoid a==b,
clamp by time, build flights, evaluate score via dp propagation per (v,t), SA loop with time limit.
*/
using ll = long long;
const int DAY_START = 6*60; // 360
const int DAY_END = 21*60; // 1260
const int INF_NEG = -1000000000;
struct City { double x, y; ll w; };
struct Flight {
int a; // 1-based city
int dep; // minutes
int b;
int arr; // minutes
};
int flight_duration_min(const City &c1, const City &c2) {
double dx = c1.x - c2.x;
double dy = c1.y - c2.y;
double d = sqrt(dx*dx + dy*dy);
double raw = 60.0 * d / 800.0 + 40.0;
int dur = (int)ceil(raw / 5.0) * 5;
return dur;
}
string time_to_str(int m) {
int h = m/60, mm = m%60;
char buf[6];
snprintf(buf, sizeof(buf), "%02d:%02d", h, mm);
return string(buf);
}
// Remove consecutive duplicate cities from a sequence
vector<int> compress_sequence(const vector<int>& seq) {
vector<int> out;
out.reserve(seq.size());
for (size_t i = 0; i < seq.size(); ++i) {
if (i == 0 || seq[i] != seq[i-1]) out.push_back(seq[i]);
}
return out;
}
// Compute dp given flights sorted in descending departure order
vector<int> compute_dp_from_flights(int N, const vector<Flight>& flights_desc_dep, int v, int t) {
vector<int> dp(N+1, INF_NEG);
dp[v] = t;
for (const auto &f : flights_desc_dep) {
if (dp[f.b] >= f.arr) {
if (f.dep > dp[f.a]) dp[f.a] = f.dep;
}
}
return dp;
}
// Precompute dp for square flights for all (v,ti)
void precompute_square_dp(int N, const vector<Flight>& square_flights, const vector<int>& target_times,
vector<vector<int>>& dp_square_by_target) {
vector<Flight> desc = square_flights;
sort(desc.begin(), desc.end(), [](const Flight& A, const Flight& B){
return A.dep > B.dep;
});
dp_square_by_target.clear();
dp_square_by_target.reserve(N * (int)target_times.size());
for (int v = 1; v <= N; ++v) {
for (size_t ti = 0; ti < target_times.size(); ++ti) {
int t = target_times[ti];
vector<int> dp = compute_dp_from_flights(N, desc, v, t);
dp_square_by_target.push_back(std::move(dp));
}
}
}
// Build flights (circle) from sequences: each sequence is vector<int> cities visited in order.
// Start time = DAY_START at seq[0], flights between consecutive cities. Stop if arrival > DAY_END.
// Skip legs where a == b (shouldn't occur if sequences are compressed).
vector<Flight> build_circle_flights_from_seqs(const vector<vector<int>>& seqs, const vector<City>& cities) {
vector<Flight> res;
for (const auto &raw_seq : seqs) {
if (raw_seq.size() < 2) continue;
vector<int> seq = compress_sequence(raw_seq);
int cur_time = DAY_START;
for (size_t i = 0; i + 1 < seq.size(); ++i) {
int a = seq[i];
int b = seq[i+1];
if (a == b) continue;
if (a < 1 || a > (int)cities.size() || b < 1 || b > (int)cities.size()) continue;
int dur = flight_duration_min(cities[a-1], cities[b-1]);
int depart = cur_time;
int arrive = depart + dur;
if (arrive > DAY_END) break;
res.push_back({a, depart, b, arrive});
cur_time = arrive;
if (cur_time >= DAY_END) break;
}
}
return res;
}
// Compute score S for given circle_flights and precomputed square dp.
// Uses dp propagation per (v,ti).
long double compute_score_S(int N, const vector<City>& cities, const vector<Flight>& square_flights,
const vector<vector<int>>& dp_square_by_target, const vector<int>& target_times,
const vector<Flight>& circle_flights) {
vector<Flight> desc = circle_flights;
sort(desc.begin(), desc.end(), [](const Flight& A, const Flight& B){
return A.dep > B.dep;
});
long double v_circle = 0.0L;
long double v_square = 0.0L;
int T = (int)target_times.size();
for (int v = 1; v <= N; ++v) {
for (int ti = 0; ti < T; ++ti) {
int idx = (v-1)*T + ti;
// dp for circle flights
vector<int> dp_circle = compute_dp_from_flights(N, desc, v, target_times[ti]);
const vector<int>& dp_square = dp_square_by_target[idx];
for (int i = 1; i <= N; ++i) {
if (i == v) continue;
long double prod = (long double)cities[i-1].w * (long double)cities[v-1].w;
int dc = dp_circle[i];
int ds = dp_square[i];
if (dc <= INF_NEG/2 && ds <= INF_NEG/2) continue;
if (dc >= ds) v_circle += prod;
else v_square += prod;
}
}
}
long double S = 0.0L;
long double denom = v_circle + v_square;
if (denom > 0) S = v_circle / denom;
return S;
}
// Extend a single sequence by adding cities (population-weighted) while time remains.
// seq is assumed to be compressed already (but we compress inside to be safe).
vector<int> extend_sequence_by_time(const vector<int>& raw_seq, const vector<City>& cities,
const vector<double>& pop_weights, std::mt19937_64 &rng) {
vector<int> seq = compress_sequence(raw_seq);
if (seq.empty()) return seq;
// compute cur_time by simulating existing legs
int cur_time = DAY_START;
for (size_t i = 0; i + 1 < seq.size(); ++i) {
int a = seq[i];
int b = seq[i+1];
if (a < 1 || a > (int)cities.size() || b < 1 || b > (int)cities.size()) { cur_time = DAY_END + 1; break; }
if (a == b) continue;
int dur = flight_duration_min(cities[a-1], cities[b-1]);
int arrive = cur_time + dur;
if (arrive > DAY_END) { // truncate at this point
seq.resize(i+1);
cur_time = DAY_END + 1;
break;
}
cur_time = arrive;
if (cur_time >= DAY_END) break;
}
if (cur_time > DAY_END) {
// truncated to beyond day end => just compress and return
return compress_sequence(seq);
}
int cur_city = seq.back();
// keep adding while we can
while (cur_time < DAY_END) {
// build weights excluding current city
vector<double> weights = pop_weights;
if (cur_city >= 1 && cur_city <= (int)weights.size()) weights[cur_city-1] = 0.0;
double total_w = 0.0;
for (double w : weights) total_w += w;
if (total_w <= 0.0) break;
discrete_distribution<int> d(weights.begin(), weights.end());
int next_city = d(rng) + 1;
if (next_city == cur_city) {
// extremely unlikely due to weight zero, but guard
break;
}
int dur = flight_duration_min(cities[cur_city-1], cities[next_city-1]);
int arrive = cur_time + dur;
if (arrive > DAY_END) break;
seq.push_back(next_city);
cur_time = arrive;
cur_city = next_city;
}
return compress_sequence(seq);
}
// Clamp sequences by time (truncate legs that would exceed DAY_END), compress duplicates,
// and then extend sequences to fill remaining time by adding cities weighted by population.
// Requires pop_weights and rng for extension behavior.
vector<vector<int>> clamp_and_extend_sequences_by_time(const vector<vector<int>>& seqs, const vector<City>& cities,
const vector<double>& pop_weights, std::mt19937_64 &rng) {
vector<vector<int>> out;
out.reserve(seqs.size());
for (const auto &raw : seqs) {
// first compress & truncate legs that exceed day end
vector<int> seq = compress_sequence(raw);
vector<int> cur;
if (seq.empty()) { out.push_back(cur); continue; }
cur.push_back(seq[0]);
int cur_time = DAY_START;
for (size_t i = 0; i + 1 < seq.size(); ++i) {
int a = seq[i];
int b = seq[i+1];
if (a == b) continue;
if (a <1 || a > (int)cities.size() || b <1 || b >(int)cities.size()) break;
int dur = flight_duration_min(cities[a-1], cities[b-1]);
int arrive = cur_time + dur;
if (arrive > DAY_END) break;
cur.push_back(b);
cur_time = arrive;
if (cur_time >= DAY_END) break;
}
// now extend using randomness and weights
vector<int> extended = extend_sequence_by_time(cur, cities, pop_weights, rng);
out.push_back(compress_sequence(extended));
}
return out;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
auto t_start = chrono::high_resolution_clock::now();
int N; int R;
if (!(cin >> N >> R)) return 0;
vector<City> cities(N);
for (int i = 0; i < N; ++i) {
double x,y; ll w;
cin >> x >> y >> w;
cities[i] = {x,y,w};
}
int M; cin >> M;
vector<Flight> square_flights;
for (int i = 0; i < M; ++i) {
int a, b; string s_str, t_str;
cin >> a >> s_str >> b >> t_str;
int s = stoi(s_str.substr(0,2))*60 + stoi(s_str.substr(3,2));
int tt = stoi(t_str.substr(0,2))*60 + stoi(t_str.substr(3,2));
square_flights.push_back({a, s, b, tt});
}
int K; cin >> K;
// Target times: 11:00,11:30,...,21:00 (21 times)
vector<int> target_times;
for (int h = 11; h <= 21; ++h) {
target_times.push_back(h*60 + 0);
if (h != 21) target_times.push_back(h*60 + 30);
}
int T = (int)target_times.size();
vector<vector<int>> dp_square_by_target;
precompute_square_dp(N, square_flights, target_times, dp_square_by_target);
mt19937_64 rng(42);
vector<double> pop_weights(N);
for (int i = 0; i < N; ++i) pop_weights[i] = (double)cities[i].w;
// initial sequences
vector<vector<int>> seqs(K);
discrete_distribution<int> start_dist(pop_weights.begin(), pop_weights.end());
uniform_int_distribution<int> len_dist(1, max(1, N/4));
for (int p = 0; p < K; ++p) {
int len = len_dist(rng);
vector<int> seq;
seq.reserve(len);
int first = start_dist(rng) + 1;
seq.push_back(first);
for (int j = 1; j < len; ++j) {
discrete_distribution<int> d(pop_weights.begin(), pop_weights.end());
int c = d(rng) + 1;
seq.push_back(c);
}
seqs[p] = compress_sequence(seq);
}
// clamp and extend initial sequences
seqs = clamp_and_extend_sequences_by_time(seqs, cities, pop_weights, rng);
vector<Flight> circle_flights = build_circle_flights_from_seqs(seqs, cities);
long double best_score = compute_score_S(N, cities, square_flights, dp_square_by_target, target_times, circle_flights);
vector<vector<int>> best_seqs = seqs;
long double cur_score = best_score;
double T0 = 1.0, T_end = 1e-4;
int iterations = 0, score_evals = 1;
const double TIME_LIMIT_SEC = 0.99;
while (true) {
auto now = chrono::high_resolution_clock::now();
double elapsed = chrono::duration_cast<chrono::duration<double>>(now - t_start).count();
if (elapsed >= TIME_LIMIT_SEC) break;
double frac = elapsed / TIME_LIMIT_SEC;
double temp = T0 * pow(T_end / T0, frac);
int p = (int)(rng() % (uint64_t)max(1, K));
vector<int> new_seq = seqs[p];
int op = (int)(rng() % 3);
if (op == 0) { // insert
int pos = new_seq.empty() ? 0 : (int)(rng() % ((uint64_t)new_seq.size() + 1));
discrete_distribution<int> d(pop_weights.begin(), pop_weights.end());
int c = d(rng) + 1;
new_seq.insert(new_seq.begin() + pos, c);
} else if (op == 1) { // delete
if (!new_seq.empty()) {
int pos = (int)(rng() % (uint64_t)new_seq.size());
new_seq.erase(new_seq.begin() + pos);
} else {
discrete_distribution<int> d(pop_weights.begin(), pop_weights.end());
int c = d(rng) + 1;
new_seq.push_back(c);
}
} else { // replace
if (!new_seq.empty()) {
int pos = (int)(rng() % (uint64_t)new_seq.size());
discrete_distribution<int> d(pop_weights.begin(), pop_weights.end());
int c = d(rng) + 1;
new_seq[pos] = c;
} else {
discrete_distribution<int> d(pop_weights.begin(), pop_weights.end());
int c = d(rng) + 1;
new_seq.push_back(c);
}
}
// compress candidate sequence
new_seq = compress_sequence(new_seq);
vector<vector<int>> cand_seqs = seqs;
cand_seqs[p] = new_seq;
// clamp & extend candidate sequences (this may add extra legs if time remains)
cand_seqs = clamp_and_extend_sequences_by_time(cand_seqs, cities, pop_weights, rng);
vector<Flight> cand_circle_flights = build_circle_flights_from_seqs(cand_seqs, cities);
long double cand_score = compute_score_S(N, cities, square_flights, dp_square_by_target, target_times, cand_circle_flights);
score_evals++;
long double delta = cand_score - cur_score;
bool accept = false;
if (delta >= 0) accept = true;
else {
double prob = exp((double)(delta) / max(1e-12, temp));
double r = (double)(rng() % 1000000) / 1000000.0;
if (r < prob) accept = true;
}
if (accept) {
seqs = std::move(cand_seqs);
circle_flights = std::move(cand_circle_flights);
cur_score = cand_score;
if (cur_score > best_score) {
best_score = cur_score;
best_seqs = seqs;
}
}
iterations++;
}
// Final: clamp & extend best_seqs (to ensure final output uses extension)
vector<vector<int>> final_seqs = clamp_and_extend_sequences_by_time(best_seqs, cities, pop_weights, rng);
// Output per-plane flights
for (int p = 0; p < K; ++p) {
const auto &seq = final_seqs[p];
vector<pair<pair<int,int>, pair<int,int>>> flights_print;
if (!seq.empty()) {
int cur_time = DAY_START;
for (size_t i = 0; i + 1 < seq.size(); ++i) {
int a = seq[i];
int b = seq[i+1];
if (a == b) continue; // safety
int dur = flight_duration_min(cities[a-1], cities[b-1]);
int depart = cur_time;
int arrive = depart + dur;
if (arrive > DAY_END) break;
flights_print.push_back({{a, depart}, {b, arrive}});
cur_time = arrive;
if (cur_time >= DAY_END) break;
}
}
cout << flights_print.size() << "\n";
for (auto &fp : flights_print) {
int a = fp.first.first;
int dep = fp.first.second;
int b = fp.second.first;
int arr = fp.second.second;
cout << a << " " << time_to_str(dep) << " " << b << " " << time_to_str(arr) << "\n";
}
}
cout.flush();
auto t_end = chrono::high_resolution_clock::now();
auto elapsed_ms = chrono::duration_cast<chrono::milliseconds>(t_end - t_start).count();
cerr << "elapsed_ms: " << elapsed_ms << "\n";
cerr << "iterations: " << iterations << "\n";
cerr << "score_evals: " << score_evals << "\n";
cerr << "best_S: " << std::fixed << std::setprecision(9) << (double)best_score << "\n";
cerr.flush();
return 0;
}