結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 prussian_coder
|
| 提出日時 | 2026-02-25 22:15:38 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 905 ms / 1,000 ms |
| コード長 | 20,238 bytes |
| 記録 | |
| コンパイル時間 | 5,514 ms |
| コンパイル使用メモリ | 364,524 KB |
| 実行使用メモリ | 7,844 KB |
| スコア | 41,229,743 |
| 最終ジャッジ日時 | 2026-02-25 22:17:21 |
| 合計ジャッジ時間 | 101,496 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge6 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
const int N = 47;
const int MF = 400;
const int K = 25;
const int TMIN = 360;
const int TMAX = 1260;
const int NT = 21;
const int NINF = -1000000;
int cx[N], cy[N], cw[N];
int sqa_[MF], sqb_[MF], sqs_[MF], sqt_[MF];
int ft[N][N];
bool vp[N][N];
int tgt[NT];
int ssq[N][N][NT];
mt19937 rng(42);
int parse_time(const char* s) {
return (s[0]-'0')*600 + (s[1]-'0')*60 + (s[3]-'0')*10 + (s[4]-'0');
}
string fmt(int t) {
char b[6];
b[0]='0'+t/600; t%=600; b[1]='0'+t/60; t%=60;
b[2]=':'; b[3]='0'+t/10; b[4]='0'+t%10; b[5]=0;
return string(b);
}
int cft(double d) {
return ((int)ceil((60.0*d/800.0+40.0)/5.0))*5;
}
void compute_sq() {
struct E { int arr, dep, from; };
vector<E> rev[N];
for (int i = 0; i < MF; i++)
rev[sqb_[i]].push_back({sqt_[i], sqs_[i], sqa_[i]});
for (int i = 0; i < N; i++)
sort(rev[i].begin(), rev[i].end(), [](auto& a, auto& b){ return a.arr > b.arr; });
for (int ti = 0; ti < NT; ti++) {
int T = tgt[ti];
for (int j = 0; j < N; j++) {
int best[N]; fill(best, best+N, NINF);
best[j] = T;
priority_queue<pair<int,int>> pq;
pq.push({T, j});
while (!pq.empty()) {
auto [at, c] = pq.top(); pq.pop();
if (at < best[c]) continue;
for (auto& e : rev[c]) {
if (e.arr > at) continue;
if (e.dep > best[e.from]) {
best[e.from] = e.dep;
pq.push({e.dep, e.from});
}
}
}
for (int i = 0; i < N; i++) ssq[i][j][ti] = best[i];
}
}
}
struct Flight { int from, to, dep, arr; };
struct Plane { vector<Flight> fs; };
vector<Flight> build(const vector<int>& cities, int start) {
vector<Flight> fs;
int ct = start;
for (int i = 0; i+1 < (int)cities.size(); i++) {
int a = cities[i], b = cities[i+1];
if (a == b) continue;
int d = ((ct+4)/5)*5;
if (d < TMIN) d = TMIN;
int ar = d + ft[a][b];
if (ar > TMAX) break;
fs.push_back({a, b, d, ar});
ct = ar;
}
return fs;
}
bool valid(const Plane& p) {
for (int j = 0; j < (int)p.fs.size(); j++) {
auto& f = p.fs[j];
if (f.from == f.to || f.dep < TMIN || f.arr > TMAX) return false;
if (f.dep%5 || f.arr%5) return false;
if (f.arr - f.dep != ft[f.from][f.to]) return false;
if (j > 0 && (p.fs[j-1].to != f.from || p.fs[j-1].arr > f.dep)) return false;
}
return true;
}
// =========================================================
// BF-based evaluation
// =========================================================
struct CF { int from, to, dep, arr; };
CF sorted_flights[500];
int nf;
void collect_sorted(const vector<Plane>& planes) {
nf = 0;
for (auto& p : planes)
for (auto& f : p.fs)
sorted_flights[nf++] = {f.from, f.to, f.dep, f.arr};
sort(sorted_flights, sorted_flights+nf, [](auto& a, auto& b){ return a.arr > b.arr; });
}
int best_ci[NT][N][N];
long long spp[NT][N];
long long score_for(int j, int ti, const int* best) {
long long s = 0;
for (int i = 0; i < N; i++)
if (vp[i][j] && best[i] > ssq[i][j][ti])
s += (long long)cw[i]*cw[j];
return s;
}
void bf_solve(int j, int ti, int* best_out) {
fill(best_out, best_out+N, NINF);
best_out[j] = tgt[ti];
for (int round = 0; round < 8; round++) {
bool changed = false;
for (int fi = 0; fi < nf; fi++) {
auto& f = sorted_flights[fi];
if (f.arr <= best_out[f.to] && f.dep > best_out[f.from]) {
best_out[f.from] = f.dep;
changed = true;
}
}
if (!changed) break;
}
}
long long eval_full(const vector<Plane>& planes) {
collect_sorted(planes);
long long total = 0;
for (int ti = 0; ti < NT; ti++) {
for (int j = 0; j < N; j++) {
bf_solve(j, ti, best_ci[ti][j]);
spp[ti][j] = score_for(j, ti, best_ci[ti][j]);
total += spp[ti][j];
}
}
return total;
}
struct Change { int ti, j; int old_best[N]; long long old_spp; };
Change changes[NT*N];
int nchanges;
long long eval_incr(const vector<Plane>& planes, long long old_score) {
collect_sorted(planes);
long long total = old_score;
nchanges = 0;
int new_best[N];
for (int ti = 0; ti < NT; ti++) {
for (int j = 0; j < N; j++) {
bf_solve(j, ti, new_best);
if (memcmp(new_best, best_ci[ti][j], sizeof(int)*N) == 0) continue;
Change& ch = changes[nchanges++];
ch.ti = ti; ch.j = j;
memcpy(ch.old_best, best_ci[ti][j], sizeof(int)*N);
ch.old_spp = spp[ti][j];
long long new_s = score_for(j, ti, new_best);
total += new_s - spp[ti][j];
spp[ti][j] = new_s;
memcpy(best_ci[ti][j], new_best, sizeof(int)*N);
}
}
return total;
}
// Partial eval for specific time slots only
long long eval_incr_partial(const vector<Plane>& planes, long long old_score,
const int* ti_list, int ti_cnt) {
collect_sorted(planes);
long long total = old_score;
nchanges = 0;
int new_best[N];
for (int k = 0; k < ti_cnt; k++) {
int ti = ti_list[k];
for (int j = 0; j < N; j++) {
bf_solve(j, ti, new_best);
if (memcmp(new_best, best_ci[ti][j], sizeof(int)*N) == 0) continue;
Change& ch = changes[nchanges++];
ch.ti = ti; ch.j = j;
memcpy(ch.old_best, best_ci[ti][j], sizeof(int)*N);
ch.old_spp = spp[ti][j];
long long new_s = score_for(j, ti, new_best);
total += new_s - spp[ti][j];
spp[ti][j] = new_s;
memcpy(best_ci[ti][j], new_best, sizeof(int)*N);
}
}
return total;
}
void rollback() {
for (int i = 0; i < nchanges; i++) {
auto& ch = changes[i];
memcpy(best_ci[ch.ti][ch.j], ch.old_best, sizeof(int)*N);
spp[ch.ti][ch.j] = ch.old_spp;
}
}
// =========================================================
// Greedy initial solution: backward construction
//
// Strategy: For each plane, build schedule from back to front.
// 1. Pick a "final destination" (high-population city)
// 2. Set deadline = TMAX (21:00)
// 3. Repeatedly prepend flights:
// - For current position (city c, must depart by time t),
// pick the source city a that maximizes score contribution
// of the flight a->c arriving at or before t
// - Update c = a, t = dep time of that flight
// - Stop when we reach TMIN
// =========================================================
// Quick heuristic: weight of a direct flight a->b arriving at arr
// = sum over valid (i, b, ti) where arr <= tgt[ti] and dep > ssq[i][b][ti]
// of w_i * w_b
// But for greedy construction, we simplify: value of flight a->b =
// sum over ti where arr <= tgt[ti] of (w_a * w_b if dep > ssq[a][b][ti])
// plus general "connectivity value" for transfer potential
long long flight_value(int a, int b, int dep, int arr) {
if (a == b || !vp[a][b]) return 0;
long long val = 0;
// Direct value: does this flight beat square for (a->b, ti)?
for (int ti = 0; ti < NT; ti++) {
if (arr <= tgt[ti] && dep > ssq[a][b][ti]) {
val += (long long)cw[a] * cw[b];
}
}
// Transfer value: this flight brings passengers to b
// Other flights from b can then continue - approximate value
// by connectivity bonus weighted by city population
val += (long long)cw[a] * cw[b] / 10; // small bonus for connectivity
return val;
}
// Backward greedy construction: build flights from back to front
// Each plane gets a hub. Schedule is built as:
// ... -> spoke -> hub -> spoke -> hub -> final_dest
// where flights are prepended, ensuring timing constraints.
void greedy_init(vector<Plane>& planes) {
// Hub assignments for 25 planes (same distribution as original)
// 8 planes hub=0, 6 planes hub=1, 5 planes hub=2, 6 planes hub=0 (extended)
int hub_assign[K];
for (int i = 0; i < 8; i++) hub_assign[i] = 0;
for (int i = 8; i < 14; i++) hub_assign[i] = 1;
for (int i = 14; i < 19; i++) hub_assign[i] = 2;
for (int i = 19; i < 25; i++) hub_assign[i] = 0;
// For spoke selection, rank cities by value relative to each hub
// value(hub, spoke) = w_hub * w_spoke * (number of ti where direct flight beats sq)
struct SpokeVal { int city; long long val; };
for (int p = 0; p < K; p++) {
int hub = hub_assign[p];
// Compute spoke values for this hub
vector<SpokeVal> spokes;
for (int s = 0; s < N; s++) {
if (s == hub || !vp[hub][s]) continue;
long long val = 0;
// How valuable is the hub<->spoke route?
int fwd_time = ft[hub][s];
int rev_time = ft[s][hub];
for (int ti = 0; ti < NT; ti++) {
// hub -> spoke flight: dep, arr=dep+fwd_time
// Check multiple possible arrival times
for (int arr = tgt[ti]; arr >= TMIN + fwd_time; arr -= 30) {
int dep = arr - fwd_time;
if (dep >= TMIN && dep > ssq[hub][s][ti]) {
val += (long long)cw[hub] * cw[s];
break;
}
}
// spoke -> hub flight
for (int arr = tgt[ti]; arr >= TMIN + rev_time; arr -= 30) {
int dep = arr - rev_time;
if (dep >= TMIN && dep > ssq[s][hub][ti]) {
val += (long long)cw[s] * cw[hub];
break;
}
}
}
spokes.push_back({s, val});
}
sort(spokes.begin(), spokes.end(), [](auto& a, auto& b){ return a.val > b.val; });
// Pick spoke for this plane (distribute among top spokes)
int spoke = spokes[p % min((int)spokes.size(), 15)].city;
// Build backward: hub <-> spoke shuttle from TMAX
vector<Flight> fs;
int cur_city = hub; // end at hub (for transfer connectivity)
int cur_deadline = TMAX;
// Stagger start: offset the "end time" slightly per plane
cur_deadline -= (p % 5) * 5;
for (int step = 0; step < 20; step++) {
int next_city = (cur_city == hub) ? spoke : hub;
int flight_time = ft[next_city][cur_city];
int arr = (cur_deadline / 5) * 5;
if (arr > TMAX) arr = TMAX;
int dep = arr - flight_time;
if (dep < TMIN) break;
// Ensure 5-min alignment
dep = (dep / 5) * 5;
arr = dep + flight_time;
if (arr > cur_deadline || arr > TMAX) break;
fs.push_back({next_city, cur_city, dep, arr});
cur_city = next_city;
cur_deadline = dep;
}
reverse(fs.begin(), fs.end());
planes[p].fs = fs;
}
}
// =========================================================
// Phase-based SA evaluation
// =========================================================
int phase_ti[3][NT];
int phase_nt[3];
double phase_scale[3];
void init_phases() {
// Phase 0: every 3rd slot (7 slots)
phase_nt[0] = 0;
for (int i = 0; i < NT; i += 3) phase_ti[0][phase_nt[0]++] = i;
phase_scale[0] = (double)NT / phase_nt[0];
// Phase 1: every 2nd slot (11 slots)
phase_nt[1] = 0;
for (int i = 0; i < NT; i += 2) phase_ti[1][phase_nt[1]++] = i;
phase_scale[1] = (double)NT / phase_nt[1];
// Phase 2: all slots (21 slots)
phase_nt[2] = NT;
for (int i = 0; i < NT; i++) phase_ti[2][i] = i;
phase_scale[2] = 1.0;
}
int main() {
auto t0 = chrono::steady_clock::now();
auto el = [&]() { return chrono::duration<double>(chrono::steady_clock::now()-t0).count(); };
int n, r; scanf("%d%d", &n, &r);
for (int i = 0; i < N; i++) scanf("%d%d%d", &cx[i], &cy[i], &cw[i]);
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
if (i == j) { ft[i][j] = 0; vp[i][j] = false; continue; }
double dx = cx[i]-cx[j], dy = cy[i]-cy[j];
double d = sqrt(dx*dx+dy*dy);
ft[i][j] = cft(d);
vp[i][j] = d >= 250.0;
}
int m; scanf("%d", &m);
for (int i = 0; i < m; i++) {
char s1[6], s2[6];
scanf("%d%5s%d%5s", &sqa_[i], s1, &sqb_[i], s2);
sqa_[i]--; sqb_[i]--;
sqs_[i] = parse_time(s1);
sqt_[i] = parse_time(s2);
}
int k; scanf("%d", &k);
for (int i = 0; i < NT; i++) tgt[i] = 660 + i*30;
compute_sq();
init_phases();
long long tw = 0;
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
if (vp[i][j]) tw += (long long)cw[i]*cw[j];
tw *= NT;
fprintf(stderr, "Precomp: %.3fs\n", el());
// =========================================================
// Initial solution: try both greedy and hub-spoke, pick better
// =========================================================
vector<Plane> planes(K);
auto shuttle = [](int hub, int spoke, int start) -> vector<Flight> {
vector<int> route;
int cur = hub, ct = start;
route.push_back(cur);
while (true) {
int next = (cur==hub)?spoke:hub;
int d = ((ct+4)/5)*5;
if (d < TMIN) d = TMIN;
if (d+ft[cur][next] > TMAX) break;
route.push_back(next);
ct = d+ft[cur][next];
cur = next;
}
return build(route, start);
};
// Option A: hub-spoke (original)
vector<Plane> planes_hs(K);
{
int asgn[][2] = {
{0,1},{0,2},{0,3},{0,4},{0,5},{0,6},{0,7},{0,8},
{1,0},{1,2},{1,3},{1,4},{1,5},{1,6},
{2,0},{2,1},{2,3},{2,4},{2,5},
{0,9},{0,10},{0,11},{0,12},{0,13},{0,14}
};
for (int i = 0; i < K; i++)
planes_hs[i].fs = shuttle(asgn[i][0], asgn[i][1], TMIN + i*12);
}
long long score_hs = eval_full(planes_hs);
fprintf(stderr, "Hub-spoke init: %lld share=%.4f (%.3fs)\n", score_hs, (double)score_hs/tw, el());
// Option B: greedy backward
vector<Plane> planes_gr(K);
greedy_init(planes_gr);
long long score_gr = eval_full(planes_gr);
fprintf(stderr, "Greedy init: %lld share=%.4f (%.3fs)\n", score_gr, (double)score_gr/tw, el());
// Pick the better one
if (score_gr > score_hs) {
planes = planes_gr;
fprintf(stderr, "Using greedy init\n");
} else {
planes = planes_hs;
fprintf(stderr, "Using hub-spoke init\n");
}
long long cur = eval_full(planes);
long long best = cur;
vector<Plane> best_p = planes;
fprintf(stderr, "Init: %lld share=%.4f (%.3fs)\n", cur, (double)cur/tw, el());
// =========================================================
// SA with phased precision
// =========================================================
const double phase_boundary[2] = {0.35, 0.70};
const double sa_lim = 0.90;
int cur_phase = 0;
// Compute partial score for current phase from cache
long long cur_partial = 0;
for (int k2 = 0; k2 < phase_nt[cur_phase]; k2++) {
int ti = phase_ti[cur_phase][k2];
for (int j = 0; j < N; j++) cur_partial += spp[ti][j];
}
double Ts_base = 3e13, Te_base = 1e9;
int it = 0, ac = 0;
int phase_its[3] = {0, 0, 0};
while (el() < sa_lim) {
double t_now = el();
double prog = t_now / sa_lim;
double sc = phase_scale[cur_phase];
double Ts_eff = Ts_base / sc, Te_eff = Te_base / sc;
double T = Ts_eff * pow(Te_eff/Ts_eff, prog);
// Phase transition
int new_phase = (prog < phase_boundary[0]) ? 0 :
(prog < phase_boundary[1]) ? 1 : 2;
if (new_phase != cur_phase) {
cur_phase = new_phase;
eval_full(planes);
cur_partial = 0;
for (int k2 = 0; k2 < phase_nt[cur_phase]; k2++) {
int ti = phase_ti[cur_phase][k2];
for (int j = 0; j < N; j++) cur_partial += spp[ti][j];
}
long long full_now = 0;
for (int ti = 0; ti < NT; ti++)
for (int j = 0; j < N; j++) full_now += spp[ti][j];
if (full_now > best) { best = full_now; best_p = planes; }
}
it++;
phase_its[cur_phase]++;
int pi = rng() % K;
Plane old = planes[pi];
int op = rng() % 100;
if (op < 40) {
int hub, spoke;
int r2 = rng()%10;
hub = (r2<5)?0:(r2<8)?1:2;
spoke = rng()%N;
if (spoke == hub) spoke = (hub+1+rng()%(N-1))%N;
int start = TMIN + (rng()%72)*5;
planes[pi].fs = shuttle(hub, spoke, start);
} else if (op < 60) {
int shift = ((int)(rng()%9)-4)*5;
if (!shift) shift = 5;
bool ok = true;
for (auto& f : planes[pi].fs) {
f.dep += shift; f.arr += shift;
if (f.dep < TMIN || f.arr > TMAX) { ok = false; break; }
}
if (!ok) { planes[pi] = old; continue; }
} else if (op < 80) {
int sc2; int r2=rng()%10;
sc2 = (r2<4)?rng()%3:(r2<7)?rng()%10:rng()%N;
int start = TMIN + (rng()%72)*5;
vector<int> route = {sc2};
int c = sc2, ct = start;
for (int t = 0; t < 15; t++) {
int nx; int r3=rng()%10;
nx = (r3<3)?rng()%3:(r3<6)?rng()%10:(r3<8)?rng()%20:rng()%N;
if (nx == c) continue;
int d = ((ct+4)/5)*5;
if (d < TMIN) d = TMIN;
if (d+ft[c][nx] > TMAX) continue;
route.push_back(nx);
ct = d+ft[c][nx];
c = nx;
}
planes[pi].fs = build(route, start);
} else {
auto& fs = planes[pi].fs;
if (fs.size() < 2) { planes[pi] = old; continue; }
int split = 1+rng()%((int)fs.size()-1);
int c = fs[split-1].to, ct = fs[split-1].arr;
vector<Flight> nfs(fs.begin(), fs.begin()+split);
for (int t = 0; t < 10; t++) {
int nx; int r3=rng()%10;
nx = (r3<3)?rng()%3:(r3<6)?rng()%10:rng()%N;
if (nx == c) continue;
int d = ((ct+4)/5)*5;
if (d+ft[c][nx] > TMAX) break;
nfs.push_back({c, nx, d, d+ft[c][nx]});
ct = d+ft[c][nx]; c = nx;
}
planes[pi].fs = nfs;
}
if (!valid(planes[pi])) { planes[pi] = old; continue; }
long long ns = eval_incr_partial(planes, cur_partial,
phase_ti[cur_phase], phase_nt[cur_phase]);
long long delta = ns - cur_partial;
if (delta > 0 || exp((double)delta/T) > (double)(rng()%1000000)/1e6) {
cur_partial = ns; ac++;
} else {
planes[pi] = old;
rollback();
}
}
// Final full evaluation
{
long long final_score = eval_full(planes);
if (final_score > best) { best = final_score; best_p = planes; }
}
planes = best_p;
fprintf(stderr, "SA: it=%d ac=%d best=%lld share=%.4f\n", it, ac, best, (double)best/tw);
fprintf(stderr, "Phase iters: [%d, %d, %d]\n", phase_its[0], phase_its[1], phase_its[2]);
long long verify = eval_full(planes);
fprintf(stderr, "Verify: %lld (diff=%lld)\n", verify, verify - best);
for (int p = 0; p < K; p++) {
printf("%d\n", (int)planes[p].fs.size());
for (auto& f : planes[p].fs) {
string sd = fmt(f.dep), sa2 = fmt(f.arr);
printf("%d %s %d %s\n", f.from+1, sd.c_str(), f.to+1, sa2.c_str());
}
}
fprintf(stderr, "Score: %lld\nTotal: %.3fs\n", (long long)((double)best/tw*1e6), el());
return 0;
}