結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 e869120
|
| 提出日時 | 2026-02-26 01:01:54 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 888 ms / 1,000 ms |
| コード長 | 10,446 bytes |
| 記録 | |
| コンパイル時間 | 3,978 ms |
| コンパイル使用メモリ | 273,776 KB |
| 実行使用メモリ | 8,212 KB |
| スコア | 58,383,114 |
| 最終ジャッジ日時 | 2026-02-26 01:03:50 |
| 合計ジャッジ時間 | 89,585 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// --- 定数 ---
constexpr int N = 47, R = 1000, M = 400, K = 25;
constexpr int INF = 1e9;
constexpr int MAX_TIME_SLOTS = 182;
constexpr int MAX_FLIGHTS = 2500;
struct Flight {
int u, s, v, t;
};
// スロット(0~180)を "HH:MM" 形式の文字列に変換
string to_time_str(int t) {
int h = 6 + t / 12;
int m = (t % 12) * 5;
char buf[10];
snprintf(buf, sizeof(buf), "%02d:%02d", h, m);
return string(buf);
}
struct Input {
array<int, N> x, y, w;
array<int, M> a, s, b, t;
bool valid_dist[N][N]{};
long long weight[N][N]{};
long long total_W = 0;
int dur[N][N]{};
Input() {
int _;
cin >> _ >> _;
for (int i = 0; i < N; ++i) cin >> x[i] >> y[i] >> w[i];
cin >> _;
string s_str, t_str;
for (int i = 0; i < M; ++i) {
cin >> a[i] >> s_str >> b[i] >> t_str;
--a[i]; --b[i];
s[i] = (stoi(s_str.substr(0, 2)) - 6) * 12 + stoi(s_str.substr(3, 2)) / 5;
t[i] = (stoi(t_str.substr(0, 2)) - 6) * 12 + stoi(t_str.substr(3, 2)) / 5;
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (i == j) continue;
long long dx = x[i] - x[j];
long long dy = y[i] - y[j];
dur[i][j] = (int)ceil((60.0 * sqrt(dx * dx + dy * dy) / 800.0 + 40.0) / 5.0 - 1e-9);
if (dx * dx + dy * dy >= (R * R) / 16) {
valid_dist[i][j] = true;
weight[i][j] = (long long)w[i] * w[j];
total_W += weight[i][j] * 21;
}
}
}
}
};
// 計算用の巨大配列を持つワークスペース（生配列にして動的確保とオーバーヘッドを削除）
struct MarginalGainWorkspace {
int current_s_ci[N][N][21];
long long edge_gain[N][N][MAX_TIME_SLOTS];
long long dp[N][MAX_TIME_SLOTS];
int nxt_v[N][MAX_TIME_SLOTS];
};
// O(N^2) に圧縮された超高速な compute_s_ci
void compute_s_ci(const Input& in, const vector<Flight>& flights, int s_ci[N][N][21]) {
for (int u = 0; u < N; ++u)
for (int dst = 0; dst < N; ++dst)
for (int t_idx = 0; t_idx < 21; ++t_idx)
s_ci[u][dst][t_idx] = -INF;
int head[MAX_TIME_SLOTS + 1];
memset(head, -1, sizeof(head));
int nxt[MAX_FLIGHTS];
for (int i = 0; i < (int)flights.size(); ++i) {
int s = flights[i].s;
if (s >= 0 && s <= 180) {
nxt[i] = head[s];
head[s] = i;
}
}
for (int dst = 0; dst < N; ++dst) {
int min_arr[N];
for (int i = 0; i < N; ++i) min_arr[i] = INF;
int next_T_idx[N];
for (int i = 0; i < N; ++i) next_T_idx[i] = 20;
for (int t = 180; t >= 0; --t) {
for (int e = head[t]; e != -1; e = nxt[e]) {
int u = flights[e].u;
int v = flights[e].v;
int arr_t = flights[e].t;
if (arr_t <= 180) {
int arr_time_at_v = (v == dst) ? arr_t : min_arr[v];
if (arr_time_at_v < min_arr[u]) {
min_arr[u] = arr_time_at_v;
if (u != dst && in.valid_dist[u][dst]) {
while (next_T_idx[u] >= 0) {
int T_target = 60 + next_T_idx[u] * 6;
if (min_arr[u] <= T_target) {
s_ci[u][dst][next_T_idx[u]] = t;
next_T_idx[u]--;
} else {
break;
}
}
}
}
}
}
}
}
}
struct RivalSchedule {
int s_sq[N][N][21];
RivalSchedule(const Input& in) {
vector<Flight> r_flights;
r_flights.reserve(M);
for (int i = 0; i < M; ++i) r_flights.push_back({in.a[i], in.s[i], in.b[i], in.t[i]});
compute_s_ci(in, r_flights, s_sq);
}
};
// キャッシュ最適化された DP テーブルの構築
void build_dp(const Input& in, const RivalSchedule& rival, MarginalGainWorkspace& mg_ws) {
memset(mg_ws.edge_gain, 0, sizeof(mg_ws.edge_gain));
for (int u = 0; u < N; ++u) {
for (int v = 0; v < N; ++v) {
if (u == v) continue;
int d = in.dur[u][v];
long long* gain_uv = mg_ws.edge_gain[u][v];
for (int dst = 0; dst < N; ++dst) {
if (!in.valid_dist[u][dst]) continue;
long long w = in.weight[u][dst];
const int* r_u_dst = rival.s_sq[u][dst];
const int* c_u_dst = mg_ws.current_s_ci[u][dst];
const int* c_v_dst = mg_ws.current_s_ci[v][dst];
for (int T_idx = 0; T_idx < 21; ++T_idx) {
int r_s = r_u_dst[T_idx];
int c_s = c_u_dst[T_idx];
if (c_s > r_s) continue;
int min_s = max(0, r_s + 1);
int max_t = (v == dst) ? (60 + T_idx * 6) : c_v_dst[T_idx];
if (max_t < 0) continue;
int max_s = min(180 - d, max_t - d);
if (min_s <= max_s) {
gain_uv[min_s] += w;
if (max_s + 1 <= 180) gain_uv[max_s + 1] -= w;
}
}
}
long long current_val = 0;
for (int s = 0; s <= 180; ++s) {
current_val += gain_uv[s];
gain_uv[s] = current_val;
}
}
}
memset(mg_ws.dp, 0, sizeof(mg_ws.dp));
memset(mg_ws.nxt_v, -1, sizeof(mg_ws.nxt_v));
for (int t = 180; t >= 0; --t) {
for (int u = 0; u < N; ++u) {
if (t + 1 <= 180) {
mg_ws.dp[u][t] = mg_ws.dp[u][t + 1];
mg_ws.nxt_v[u][t] = -1;
}
for (int v = 0; v < N; ++v) {
if (u == v) continue;
int t_next = t + in.dur[u][v];
if (t_next <= 180) {
long long gain = mg_ws.edge_gain[u][v][t];
if (gain + mg_ws.dp[v][t_next] > mg_ws.dp[u][t]) {
mg_ws.dp[u][t] = gain + mg_ws.dp[v][t_next];
mg_ws.nxt_v[u][t] = v;
}
}
}
}
}
}
long long get_score(const Input& in, const RivalSchedule& rival, const int c_s[N][N][21]) {
long long v_ci = 0;
for (int u = 0; u < N; ++u) {
for (int v = 0; v < N; ++v) {
if (!in.valid_dist[u][v]) continue;
long long w = in.weight[u][v];
const int* r_arr = rival.s_sq[u][v];
const int* c_arr = c_s[u][v];
for (int t = 0; t < 21; ++t) {
if (c_arr[t] > r_arr[t]) v_ci += w;
}
}
}
return (long long)(1000000.0 * (double)v_ci / in.total_W);
}
// ビームサーチで管理する「状態」
struct State {
vector<vector<Flight>> current_paths;
vector<Flight> all_flights;
long long score;
bool operator<(const State& other) const {
return score > other.score;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
Input in;
// 巨大な配列はヒープ領域に確保する
auto mg_ws = make_unique<MarginalGainWorkspace>();
RivalSchedule rival(in);
// ★ ビームサーチの設定
const int BEAM_WIDTH = 6; // 保持する状態数
const int BRANCHES = 10; // 各状態から展開する「開始都市の数」
vector<State> beam;
State init_state;
init_state.score = 0;
beam.push_back(init_state);
for (int k = 0; k < K; ++k) {
vector<State> next_beam;
for (const auto& state : beam) {
compute_s_ci(in, state.all_flights, mg_ws->current_s_ci);
build_dp(in, rival, *mg_ws);
vector<pair<long long, int>> start_cands;
for (int u = 0; u < N; ++u) {
// ★ 修正箇所：emplace_back を使用して std::pair 推論エラーを回避
start_cands.emplace_back(mg_ws->dp[u][0], u);
}
sort(start_cands.rbegin(), start_cands.rend());
for (int i = 0; i < min(N, BRANCHES); ++i) {
int start_u = start_cands[i].second;
vector<Flight> path;
int curr_u = start_u, curr_t = 0;
while (curr_t <= 180) {
int next_city = mg_ws->nxt_v[curr_u][curr_t];
if (next_city != -1) {
int d = in.dur[curr_u][next_city];
path.push_back({curr_u, curr_t, next_city, curr_t + d});
curr_u = next_city;
curr_t += d;
} else {
curr_t += 1;
}
}
State nstate = state;
nstate.current_paths.push_back(path);
for (const auto& f : path) {
nstate.all_flights.push_back(f);
}
compute_s_ci(in, nstate.all_flights, mg_ws->current_s_ci);
nstate.score = get_score(in, rival, mg_ws->current_s_ci);
next_beam.push_back(nstate);
}
}
sort(next_beam.begin(), next_beam.end());
beam.clear();
for (const auto& s : next_beam) {
if (beam.empty() || beam.back().score != s.score) {
beam.push_back(s);
if (beam.size() == BEAM_WIDTH) break;
}
}
}
const auto& best_state = beam.front();
for (int k = 0; k < K; ++k) {
cout << best_state.current_paths[k].size() << "\n";
for (const auto& f : best_state.current_paths[k]) {
cout << f.u + 1 << " " << to_time_str(f.s) << " "
<< f.v + 1 << " " << to_time_str(f.t) << "\n";
}
}
return 0;
}