結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 FplusFplusF
|
| 提出日時 | 2026-02-28 05:37:28 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 985 ms / 1,000 ms |
| コード長 | 27,274 bytes |
| 記録 | |
| コンパイル時間 | 10,813 ms |
| コンパイル使用メモリ | 434,392 KB |
| 実行使用メモリ | 7,972 KB |
| スコア | 64,098,679 |
| 最終ジャッジ日時 | 2026-02-28 05:39:28 |
| 合計ジャッジ時間 | 116,539 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge7 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using tii=tuple<int,int,int>;
using qii=tuple<int,int,int,int>;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
constexpr int INF=1e9;
constexpr ll INF_ll=1e18;
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define replr(i,l,r) for (int i=(int)(l);i<(int)(r);i++)
#define all(v) v.begin(),v.end()
#define len(v) ((int)v.size())
template<class T> inline bool chmin(T &a,const T &b){
if(a>b){
a=b;
return true;
}
return false;
}
template<class T> inline bool chmax(T &a,const T &b){
if(a<b){
a=b;
return true;
}
return false;
}
namespace Timer{
chrono::steady_clock::time_point program_start,start;
void program_start_snap(){
program_start=start=chrono::steady_clock::now();
}
void snap(){
start=chrono::steady_clock::now();
}
int get_ms(){
auto now=chrono::steady_clock::now();
int ms=chrono::duration_cast<chrono::milliseconds>(now-start).count();
return ms;
}
int get_ms_all_program(){
auto now=chrono::steady_clock::now();
int ms=chrono::duration_cast<chrono::milliseconds>(now-program_start).count();
return ms;
}
}
mt19937 mt;
uint32_t rand_int(uint32_t r){ //[0,r)
assert(r!=0);
return ((uint64_t)mt()*r)>>32;
}
int rand_int(int l,int r){ //[l,r)
assert(l<r);
return l+rand_int(r-l);
}
constexpr double one_div_mt_max=1.0/(double)mt19937::max();
double rand_double(){ //[0.0,1.0]
return mt()*one_div_mt_max;
}
template<class T> T get_random_element(const vector<T> &v){
assert(!v.empty());
return v[rand_int(len(v))];
}
template<class T> void add(vector<T> &a,vector<T> b){
for(auto i:b) a.push_back(i);
}
template<class SA_State,int limit_ms,double start_temp,double end_temp=0.0> SA_State SA(const SA_State &first_state){
SA_State state=first_state,best_state=state;
int loop_cnt=0,accept_cnt=0,update_cnt=0;
int ms=0;
double temp=start_temp;
//Timer::snap();
while(true){
if(true){
ms=Timer::get_ms();
if(limit_ms<=ms) break;
//double t=(double)ms/limit_ms;
temp=start_temp-(start_temp-end_temp)/limit_ms*ms;
//temp=pow(start_temp,1-t)*pow(end_temp,t);
}
loop_cnt++;
double accept_diff=log(rand_double())*temp;
bool accepted=state.modify(accept_diff);
if(accepted){
accept_cnt++;
if(best_state.score<state.score){
best_state=state;
cerr << "score:" << (int)best_state.score << " ms:" << ms << " loop_cnt:" << loop_cnt << " accept_cnt:" << accept_cnt << " update_cnt:" << update_cnt << '\n';
update_cnt++;
}
}
}
cerr << "[result] " << "score:" << best_state.score << " ms:" << ms << " loop_cnt:" << loop_cnt << " accept_cnt:" << accept_cnt << " update_cnt:" << update_cnt << '\n';
return best_state;
};
constexpr int N=47,R=1000,M=400,K=25,T=181,Target_size=21;
array<int,N> X,Y,W;
array<array<ll,N>,N> W_score;
ll W_score_sum=0;
struct Plan{
int a,b;
int s,t;
auto operator<=>(const Plan &other) const{
return this->t<=>other.t;
}
};
array<Plan,M> P;
array<array<int,N>,N> D;
array<array<bool,N>,N> Is_target;
array<string,T> Time_string;
array<int,Target_size> Target_times;
array<array<int,N>,Target_size*N> memo_s_sq;
array<vector<int>,N> square_t_plans;
array<array<bool,Target_size>,N> square_next_update;
namespace SA_solver{
void calc_times(int j,int t,const vector<Plan> &sorted_plans,array<int,N> &s){
s.fill(-INF);
s[j]=t;
for(const auto &plan:sorted_plans){
if(plan.t<=s[plan.b]&&s[plan.a]<plan.s){
s[plan.a]=plan.s;
}
}
}
auto tours_to_ans(array<vector<int>,K> tours){
array<vector<Plan>,K> ans;
rep(k,K){
if(tours.empty()) continue;
int x=tours[k].back(),t=T-1;
tours[k].pop_back();
while(!tours[k].empty()){
int y=tours[k].back();
if(t-D[y][x]<0) break;
if(x==y){
tours[k].pop_back();
continue;
}
ans[k].emplace_back(y,x,t-D[y][x],t);
t-=D[y][x];
x=y;
tours[k].pop_back();
}
reverse(all(ans[k]));
}
return ans;
}
ll calc_now_ci(int j,const auto &s_sq,const auto &s_ci){
int sum=0;
rep(i,N){
sum+=Is_target[j][i]*W[i]*(s_sq[i]<s_ci[i]);
}
return (ll)sum*W[j];
}
int calc_score(array<vector<int>,K> tours){
vector<Plan> plans;
rep(k,K){
if(tours.empty()) continue;
int x=tours[k].back(),t=T-1;
tours[k].pop_back();
while(!tours[k].empty()){
int y=tours[k].back();
if(t-D[y][x]<0) break;
if(x==y){
tours[k].pop_back();
continue;
}
plans.emplace_back(y,x,t-D[y][x],t);
t-=D[y][x];
x=y;
tours[k].pop_back();
}
}
sort(all(plans));
reverse(all(plans));
array<vector<int>,N> circle_t_plans;
for(auto plan:plans){
circle_t_plans[plan.b].push_back(plan.t);
}
rep(i,N) sort(all(circle_t_plans[i]));
array<array<bool,21>,N> circle_next_update;
rep(j,N){
circle_next_update[j].fill(false);
rep(t_idx,len(Target_times)-1){
auto itr_circle=upper_bound(all(circle_t_plans[j]),Target_times[t_idx]);
if(itr_circle!=circle_t_plans[j].end()&&*itr_circle<=Target_times[t_idx+1]){
circle_next_update[j][t_idx]=true;
}
}
}
ll ci=0;
for(int j=0;j<N;j++){
array<int,N> s_ci;
calc_times(j,Target_times.front(),plans,s_ci);
auto s_sq=memo_s_sq[j*Target_size];
ll now_ci=calc_now_ci(j,s_sq,s_ci);
rep(t_idx,len(Target_times)){
ci+=now_ci;
if(t_idx+1<len(Target_times)){
bool update=false;
if(square_next_update[j][t_idx]){
s_sq=memo_s_sq[j*Target_size+t_idx+1];
update=true;
}
if(circle_next_update[j][t_idx]){
calc_times(j,Target_times[t_idx+1],plans,s_ci);
update=true;
}
if(update){
now_ci=calc_now_ci(j,s_sq,s_ci);
}
}
}
}
ll sq=W_score_sum-ci;
return floor(1e6*(double)ci/(sq+ci));
}
vector<int> w_sum;
int get_random_city(){
return upper_bound(all(w_sum),rand_int(w_sum.back()))-w_sum.begin()-1;
}
int get_random_city_near(int x){
while(true){
int y=get_random_city();
if(x==y) continue;
double prob=1/max(1.0,(double)D[x][y]/12);
if(rand_double()<prob){
return y;
}
}
}
void update_tour(vector<int> &tour){
if(tour.empty()) tour.push_back(get_random_city());
int x=tour.back(),t=T-1;
tour.pop_back();
vector<int> new_tour;
new_tour.push_back(x);
while(true){
int y=-1;
if(tour.empty()){
y=get_random_city();
}else{
y=tour.back();
tour.pop_back();
}
if(x==y) continue;
if(t-D[y][x]<0) break;
new_tour.push_back(y);
t-=D[y][x];
x=y;
}
reverse(all(new_tour));
tour=new_tour;
}
struct State{
set<int> vis;
array<vector<int>,K> tours;
int score=0;
State(const auto &ans){
rep(k,K){
rep(i,len(ans[k])){
tours[k].push_back(ans[k][i].a);
}
tours[k].push_back(ans[k].back().b);
}
score=calc_score(tours);
}
bool modify(double accept_diff){
auto new_tours=tours;
int k=rand_int(K);
int r=rand_int(4);
int sz=len(new_tours[k]);
if(r==0){
int idx=rand_int(sz+1);
int x=-1;
if(idx==sz) x=get_random_city_near(new_tours[k][idx-1]);
else x=get_random_city_near(new_tours[k][idx]);
new_tours[k].insert(new_tours[k].begin()+idx,x);
}else if(r==1){
if(new_tours[k].empty()) return false;
new_tours[k].erase(new_tours[k].begin()+rand_int(sz));
}else if(r==2){
if(new_tours[k].empty()) return false;
int idx=rand_int(sz);
int x=-1;
if(idx==sz-1) x=get_random_city_near(new_tours[k][idx-1]);
else x=get_random_city_near(new_tours[k][idx+1]);
new_tours[k][idx]=x;
}else if(r==3){
swap(new_tours[k][rand_int(sz)],new_tours[k][rand_int(sz)]);
}
update_tour(new_tours[k]);
int new_score=calc_score(new_tours);
if(accept_diff<=new_score-score){
score=new_score;
tours=new_tours;
return true;
}
return false;
}
};
auto solve(auto ans){
w_sum.resize(N+1,0);
rep(i,N) w_sum[i+1]=w_sum[i]+W[i];
State state(ans);
state=SA<State,980,800.0,0.0>(state);
return tours_to_ans(state.tours);
}
}
namespace Solver{
void calc_times(int j,int t,const vector<Plan> &sorted_plans,array<int,N> &s){
s.fill(-INF);
s[j]=t;
for(const auto &plan:sorted_plans){
if(plan.t<=s[plan.b]&&s[plan.a]<plan.s){
s[plan.a]=plan.s;
}
}
}
struct Candidate{
ll score=0;
int parent=-1;
vector<Plan> plans;
auto operator<=>(const Candidate &other) const{
return this->score<=>other.score;
}
};
struct State{
array<vector<Plan>,K> ans;
vector<Plan> all_plans;
ll calc_now_ci(int j,const auto &s_sq,const auto &s_ci){
int sum=0;
rep(i,N){
sum+=Is_target[j][i]*W[i]*(s_sq[i]<s_ci[i]);
}
return (ll)sum*W[j];
}
ll calc_true_score(){
sort(all(all_plans));
reverse(all(all_plans));
array<vector<int>,N> circle_t_plans;
for(auto plan:all_plans){
circle_t_plans[plan.b].push_back(plan.t);
}
rep(i,N) sort(all(circle_t_plans[i]));
array<array<bool,21>,N> circle_next_update;
rep(j,N){
circle_next_update[j].fill(false);
rep(t_idx,Target_size-1){
auto itr_circle=upper_bound(all(circle_t_plans[j]),Target_times[t_idx]);
if(itr_circle!=circle_t_plans[j].end()&&*itr_circle<=Target_times[t_idx+1]){
circle_next_update[j][t_idx]=true;
}
}
}
ll ci=0;
for(int j=0;j<N;j++){
array<int,N> s_ci;
calc_times(j,Target_times.front(),all_plans,s_ci);
auto s_sq=memo_s_sq[j*Target_size];
ll now_ci=calc_now_ci(j,s_sq,s_ci);
rep(t_idx,Target_size){
ci+=now_ci;
if(t_idx+1<Target_size){
bool update=false;
if(square_next_update[j][t_idx]){
s_sq=memo_s_sq[j*Target_size+t_idx+1];
update=true;
}
if(circle_next_update[j][t_idx]){
calc_times(j,Target_times[t_idx+1],all_plans,s_ci);
update=true;
}
if(update){
now_ci=calc_now_ci(j,s_sq,s_ci);
}
}
}
}
return ci;
}
int k=0;
ll score=0;
auto operator<=>(const State &other) const{
return this->score<=>other.score;
}
vector<Candidate> get_candidates(int parent){
sort(all(all_plans));
reverse(all(all_plans));
array<vector<int>,N> circle_t_plans;
for(auto plan:all_plans){
circle_t_plans[plan.b].push_back(plan.t);
}
rep(i,N) sort(all(circle_t_plans[i]));
array<array<bool,Target_size>,N> circle_next_update;
rep(j,N){
circle_next_update[j].fill(false);
rep(t_idx,Target_size){
auto itr_circle=upper_bound(all(circle_t_plans[j]),Target_times[t_idx]);
if(itr_circle!=circle_t_plans[j].end()&&*itr_circle<=Target_times[t_idx+1]){
circle_next_update[j][t_idx]=true;
}
}
}
array<array<array<ll,T+1>,N>,N> point;
rep(j,N){
rep(i,N){
point[j][i].fill(0);
}
}
for(int j=0;j<N;j++){
array<int,N> s_ci;
calc_times(j,Target_times.front(),all_plans,s_ci);
auto s_sq=memo_s_sq[j*Target_size];
int cnt=0;
rep(t_idx,Target_size){
int t=Target_times[t_idx];
rep(i,N){
if(s_sq[i]<s_ci[i]) continue;
if(!Is_target[j][i]) continue;
int l=clamp(s_sq[i]+1+D[i][j],0,T+1);
int r=t;
if(r<=l) continue;
point[j][i][l]+=W_score[j][i];
point[j][i][r+1]-=W_score[j][i];
}
cnt++;
bool update=false;
if(t_idx==Target_size-1) update=true;
if(t_idx+1<Target_size){
if(square_next_update[j][t_idx]){
update=true;
}
if(circle_next_update[j][t_idx]){
update=true;
}
}
if(!update) continue;
rep(i,N){
if(s_sq[i]<s_ci[i]) continue;
if(!Is_target[j][i]) continue;
rep(c,N){
if(c==j) continue;
if(c==i) continue;
int l=clamp(s_sq[i]+1+D[i][c],0,T+1);
int r=s_ci[c];
if(c==j) r=t;
if(r<=l) continue;
point[c][i][l]+=cnt*W_score[j][i];
point[c][i][r+1]-=cnt*W_score[j][i];
}
}
cnt=0;
if(t_idx+1<Target_size){
if(square_next_update[j][t_idx]){
s_sq=memo_s_sq[j*Target_size+t_idx+1];
}
if(circle_next_update[j][t_idx]){
calc_times(j,Target_times[t_idx+1],all_plans,s_ci);
}
}
}
}
rep(j,N){
rep(i,N){
rep(t,T){
point[j][i][t+1]+=point[j][i][t];
}
}
}
array<array<ll,N>,T> dp;
array<array<pii,N>,T> pre;
rep(t,T){
dp[t].fill(-INF_ll);
pre[t].fill({-1,-1});
}
dp[T-1].fill(0);
for(int t=T-1;0<=t;t--){
rep(j,N){
if(dp[t][j]<0) continue;
/*if(0<=t-1){
if(chmax(dp[t-1][j],dp[t][j])) pre[t-1][j]={t,j};
}*/
rep(i,N){
if(i==j) continue;
int s=t-D[j][i];
if(0<=s){
if(chmax(dp[s][i],dp[t][j]+point[j][i][t])) pre[s][i]={t,j};
}
}
}
}
vector<Candidate> ret;
rep(n,N){
ll now=0;
int nt=-1,ni=n;
for(int t=T-1;0<=t;t--){
if(chmax(now,dp[t][n])) nt=t;
}
vector<Plan> plans;
while(true){
auto [pt,pi]=pre[nt][ni];
if(pt==-1) break;
if(ni!=pi){
plans.emplace_back(ni,pi,nt,pt);
}
nt=pt;
ni=pi;
}
ret.emplace_back(score+now,parent,plans);
}
sort(all(ret));
reverse(all(ret));
ret.resize(10);
return ret;
}
void advance(Candidate candidate){
ans[k]=candidate.plans;
add(all_plans,candidate.plans);
score=calc_true_score();
k++;
}
};
auto beam_search(){
constexpr int W=5;
vector<State> dp;
dp.push_back(State());
rep(k,K){
cerr << k << " " << dp[0].score << " " << len(dp) << endl;
priority_queue<State,vector<State>,greater<State>> pq;
rep(w,W){
if(len(dp)<=w) break;
vector<Candidate> candidates=dp[w].get_candidates(w);
for(auto candidate:candidates){
State state=dp[w];
state.advance(candidate);
if(len(pq)==W&&state<=pq.top()) continue;
pq.push(state);
if(W<len(pq)) pq.pop();
}
}
dp.clear();
while(!pq.empty()){
State state=pq.top();
pq.pop();
dp.push_back(state);
}
reverse(all(dp));
}
assert(!dp.empty());
return dp[0].ans;
}
void solve(){
vector<Plan> all_plans(all(P));
sort(all(all_plans));
reverse(all(all_plans));
rep(j,N){
rep(t_idx,Target_size){
calc_times(j,Target_times[t_idx],all_plans,memo_s_sq[j*Target_size+t_idx]);
}
}
rep(i,M){
square_t_plans[P[i].b].push_back(P[i].t);
}
rep(i,N) sort(all(square_t_plans[i]));
rep(j,N){
square_next_update[j].fill(false);
rep(t_idx,Target_size){
auto itr_square=upper_bound(all(square_t_plans[j]),Target_times[t_idx]);
if(itr_square!=square_t_plans[j].end()&&*itr_square<=Target_times[t_idx+1]){
square_next_update[j][t_idx]=true;
}
}
}
array<vector<Plan>,K> ans=beam_search();
ans=SA_solver::solve(ans);
rep(k,K){
cout << len(ans[k]) << '\n';
rep(i,len(ans[k])){
if(1<=i){
assert(ans[k][i-1].b==ans[k][i].a);
assert(ans[k][i-1].t<=ans[k][i].s);
}
assert(0<=ans[k][i].s&&ans[k][i].s<T);
assert(0<=ans[k][i].t&&ans[k][i].t<T);
assert(ans[k][i].t-ans[k][i].s==D[ans[k][i].a][ans[k][i].b]);
}
for(auto plan:ans[k]){
cout << plan.a+1 << ' ' << Time_string[plan.s] << ' ' << plan.b+1 << ' ' << Time_string[plan.t] << '\n';
}
}
cerr << Timer::get_ms_all_program() << ' ' << endl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
Timer::program_start_snap();
int n,r;
cin >> n >> r;
assert(n==N);
assert(r==R);
rep(i,N) cin >> X[i] >> Y[i] >> W[i];
int m;
cin >> m;
assert(m==M);
rep(i,M){
int a,b;
string s,t;
cin >> a >> s >> b >> t;
a--;
b--;
P[i].a=a;
P[i].b=b;
int sx=stoi(s.substr(0,2)),sy=stoi(s.substr(3,2));
int tx=stoi(t.substr(0,2)),ty=stoi(t.substr(3,2));
P[i].s=(sx*60+sy-6*60)/5;
P[i].t=(tx*60+ty-6*60)/5;
}
int k;
cin >> k;
assert(k==K);
rep(i,N){
rep(j,N){
double d=hypot<double>(X[i]-X[j],Y[i]-Y[j]);
int t=ceil(60*d/800+40);
while(t%5!=0) t++;
D[i][j]=t/5;
}
}
for(int i=6;i<=21;i++){
for(int j=0;j<60;j+=5){
string sx=to_string(i),sy=to_string(j);
while(len(sx)<2) sx.insert(sx.begin(),'0');
while(len(sy)<2) sy.insert(sy.begin(),'0');
Time_string[(i*60+j-6*60)/5]=sx+":"+sy;
if(i==21) break;
}
}
int idx=0;
for(int i=11;i<=21;i++){
for(int j=0;j<60;j+=30){
Target_times[idx]=(i*60+j-6*60)/5;
idx++;
if(i==21) break;
}
}
rep(i,N){
rep(j,N){
ll x=((ll)(X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]))*16;
if(R*R<=x){
Is_target[i][j]=true;
}else{
Is_target[i][j]=false;
}
}
}
rep(i,N){
W_score[i].fill(0);
rep(j,N){
if(Is_target[i][j]) W_score[i][j]=(ll)W[i]*W[j];
}
}
W_score_sum=0;
rep(i,N){
rep(j,N){
if(!Is_target[i][j]) continue;
rep(_,Target_size){
W_score_sum+=W_score[i][j];
}
}
}
Solver::solve();
exit(0);
}