#1149385 (C++17) No.5023 Airlines Optimization

• 問題: No.5023 Airlines Optimization
• ユーザー: mtmr_s1
• 提出日時: 2026-02-25 23:27:19
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 982 ms / 1,000 ms
• コード長: 19,896 bytes
• コンパイル時間: 4,800 ms
• コンパイル使用メモリ: 280,232 KB
• 実行使用メモリ: 7,848 KB
• スコア: 46,501,139
• 最終ジャッジ日時: 2026-02-25 23:29:08
• 合計ジャッジ時間: 108,501 ms
• ジャッジサーバーID （参考情報）: judge7 / judge4

ファイルパターン	結果
other	AC * 100

ソースコード

#include <bits/stdc++.h>
using namespace std;

static constexpr int START_MIN = 6 * 60;
static constexpr int END_MIN = 21 * 60;
static constexpr int STEP_MIN = 5;
static constexpr int TICK_MAX = (END_MIN - START_MIN) / STEP_MIN; // 180
static constexpr int NEG_INF = -1;

struct City {
  int x, y;
  long long w;
};

struct Flight {
  int a, b; // 0-based city
  int s, t; // tick [0..180]
};

struct Candidate {
  bool valid = false;
  int b = -1;
  int t = -1;
  int dur = -1;
  long long delta = LLONG_MIN;
  long long potential = LLONG_MIN;
  long long pop = LLONG_MIN;
};

struct XorShift {
  uint64_t x = 88172645463325252ULL;
  uint64_t next_u64() {
    x ^= x << 7;
    x ^= x >> 9;
    return x;
  }
  int next_int(int lo, int hi) {
    return lo + (int)(next_u64() % (uint64_t)(hi - lo + 1));
  }
  double next_double() {
    return (next_u64() >> 11) * (1.0 / 9007199254740992.0);
  }
};

static int time_to_idx(const string &hhmm) {
  int hh = stoi(hhmm.substr(0, 2));
  int mm = stoi(hhmm.substr(3, 2));
  int mins = hh * 60 + mm;
  return (mins - START_MIN) / STEP_MIN;
}

static string idx_to_time(int idx) {
  int mins = START_MIN + idx * STEP_MIN;
  int hh = mins / 60;
  int mm = mins % 60;
  ostringstream oss;
  oss << setw(2) << setfill('0') << hh << ":" << setw(2) << setfill('0') << mm;
  return oss.str();
}

static int duration_ticks(const City &c1, const City &c2) {
  double dx = double(c1.x - c2.x);
  double dy = double(c1.y - c2.y);
  double dist = sqrt(dx * dx + dy * dy);
  double raw = 60.0 * dist / 800.0 + 40.0;
  int rounded = int(ceil(raw / 5.0 - 1e-12) * 5.0);
  return rounded / 5;
}

static inline int latest_idx(int n, int dcount, int dest, int dk, int orig) {
  return ((dest * dcount) + dk) * n + orig;
}

static void compute_latest_all_sorted(
    int n,
    const vector<int> &deadlines,
    const vector<Flight> &flights_desc,
    vector<int> &latest_out) {
  const int dcount = (int)deadlines.size();
  latest_out.assign(n * dcount * n, NEG_INF);

  for (int dest = 0; dest < n; dest++) {
    for (int dk = 0; dk < dcount; dk++) {
      int deadline = deadlines[dk];
      int base = latest_idx(n, dcount, dest, dk, 0);
      int *L = &latest_out[base];
      fill(L, L + n, NEG_INF);
      L[dest] = deadline;

      for (const auto &f : flights_desc) {
        if (f.t > deadline) {
          continue;
        }
        if (L[f.b] >= f.t && f.s > L[f.a]) {
          L[f.a] = f.s;
        }
      }
    }
  }
}

static long long evaluate_vci(
    int n,
    const vector<int> &deadlines,
    const vector<int> &sq_latest,
    const vector<int> &ci_latest,
    const vector<vector<pair<int, long long>>> &relevant_dests) {
  const int dcount = (int)deadlines.size();
  long long vci = 0;
  for (int orig = 0; orig < n; orig++) {
    for (const auto &[dest, wprod] : relevant_dests[orig]) {
      for (int dk = 0; dk < dcount; dk++) {
        int sq = sq_latest[latest_idx(n, dcount, dest, dk, orig)];
        int ci = ci_latest[latest_idx(n, dcount, dest, dk, orig)];
        if (sq < ci) {
          vci += wprod;
        }
      }
    }
  }
  return vci;
}

static long long estimate_delta_origin_only(
    int n,
    const vector<int> &deadlines,
    const vector<int> &sq_latest,
    const vector<int> &ci_latest,
    const vector<vector<pair<int, long long>>> &relevant_dests,
    int a,
    int b,
    int s,
    int t) {
  const int dcount = (int)deadlines.size();
  long long delta = 0;

  for (const auto &[dest, wprod] : relevant_dests[a]) {
    for (int dk = 0; dk < dcount; dk++) {
      int idx_b = latest_idx(n, dcount, dest, dk, b);
      if (ci_latest[idx_b] < t) {
        continue;
      }

      int idx_a = latest_idx(n, dcount, dest, dk, a);
      int old_ci = ci_latest[idx_a];
      if (old_ci >= s) {
        continue;
      }

      int sq = sq_latest[idx_a];
      bool old_win = (sq < old_ci);
      bool new_win = (sq < s);
      if (!old_win && new_win) {
        delta += wprod;
      }
    }
  }

  return delta;
}

static vector<pair<int, int>> collect_upstream_onehop(
    int n,
    const vector<City> &cities,
    const vector<Flight> &flights_desc,
    int a,
    int s,
    int max_upstream) {
  vector<int> best_dep(n, NEG_INF);
  best_dep[a] = s;
  for (const auto &f : flights_desc) {
    if (f.b == a && f.t <= s && f.s > best_dep[f.a]) {
      best_dep[f.a] = f.s;
    }
  }

  vector<int> ids;
  ids.reserve(n);
  for (int i = 0; i < n; i++) {
    if (best_dep[i] >= 0) {
      ids.push_back(i);
    }
  }
  sort(ids.begin(), ids.end(), [&](int p, int q) {
    if (best_dep[p] != best_dep[q]) return best_dep[p] > best_dep[q];
    if (cities[p].w != cities[q].w) return cities[p].w > cities[q].w;
    return p < q;
  });
  if ((int)ids.size() > max_upstream) {
    ids.resize(max_upstream);
  }

  vector<pair<int, int>> out;
  out.reserve(ids.size());
  for (int id : ids) {
    out.push_back({id, best_dep[id]});
  }
  return out;
}

static long long estimate_delta_upstream(
    int n,
    const vector<int> &deadlines,
    const vector<int> &sq_latest,
    const vector<int> &ci_latest,
    const vector<vector<pair<int, long long>>> &relevant_dests,
    const vector<pair<int, int>> &upstream_origins,
    int b,
    int t) {
  const int dcount = (int)deadlines.size();
  long long delta = 0;

  for (const auto &[orig, dep_tick] : upstream_origins) {
    for (const auto &[dest, wprod] : relevant_dests[orig]) {
      for (int dk = 0; dk < dcount; dk++) {
        int idx_b = latest_idx(n, dcount, dest, dk, b);
        if (ci_latest[idx_b] < t) {
          continue;
        }

        int idx_o = latest_idx(n, dcount, dest, dk, orig);
        int old_ci = ci_latest[idx_o];
        if (old_ci >= dep_tick) {
          continue;
        }

        int sq = sq_latest[idx_o];
        bool old_win = (sq < old_ci);
        bool new_win = (sq < dep_tick);
        if (!old_win && new_win) {
          delta += wprod;
        }
      }
    }
  }

  return delta;
}

static bool better_candidate(const Candidate &lhs, const Candidate &rhs) {
  if (!lhs.valid) return false;
  if (!rhs.valid) return true;
  if (lhs.delta != rhs.delta) return lhs.delta > rhs.delta;
  if (lhs.potential != rhs.potential) return lhs.potential > rhs.potential;
  if (lhs.pop != rhs.pop) return lhs.pop > rhs.pop;
  if (lhs.dur != rhs.dur) return lhs.dur < rhs.dur;
  return lhs.b < rhs.b;
}

static vector<Flight> build_legs_from_route(
    int start_city,
    int start_tick,
    const vector<int> &route,
    const vector<vector<int>> &dur) {
  vector<Flight> legs;
  int cur_city = start_city;
  int cur_t = start_tick;

  for (int dest : route) {
    if (dest < 0 || dest >= (int)dur.size()) {
      continue;
    }
    if (dest == cur_city) {
      continue;
    }
    int d = dur[cur_city][dest];
    if (d <= 0) {
      continue;
    }
    int arr = cur_t + d;
    if (arr > TICK_MAX) {
      break;
    }
    legs.push_back(Flight{cur_city, dest, cur_t, arr});
    cur_city = dest;
    cur_t = arr;
  }

  return legs;
}

static vector<int> route_from_legs(const vector<Flight> &legs) {
  vector<int> r;
  r.reserve(legs.size());
  for (const auto &f : legs) {
    r.push_back(f.b);
  }
  return r;
}

static vector<Flight> flatten_desc(const vector<vector<Flight>> &plane_legs) {
  vector<Flight> all;
  size_t total = 0;
  for (const auto &v : plane_legs) {
    total += v.size();
  }
  all.reserve(total);
  for (const auto &v : plane_legs) {
    for (const auto &f : v) {
      all.push_back(f);
    }
  }
  sort(all.begin(), all.end(), [](const Flight &p, const Flight &q) {
    if (p.s != q.s) return p.s > q.s;
    return p.t > q.t;
  });
  return all;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  auto solver_start = chrono::steady_clock::now();
  auto elapsed_sec = [&]() {
    auto now = chrono::steady_clock::now();
    return chrono::duration<double>(now - solver_start).count();
  };
  const double TOTAL_LIMIT_SEC = 0.98;

  int n, r;
  cin >> n >> r;
  vector<City> cities(n);
  for (int i = 0; i < n; i++) {
    cin >> cities[i].x >> cities[i].y >> cities[i].w;
  }

  int m;
  cin >> m;
  vector<Flight> square(m);
  for (int i = 0; i < m; i++) {
    int a, b;
    string ss, tt;
    cin >> a >> ss >> b >> tt;
    --a;
    --b;
    square[i] = Flight{a, b, time_to_idx(ss), time_to_idx(tt)};
  }

  int k;
  cin >> k;

  vector<vector<int>> dur(n, vector<int>(n, 0));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i == j) continue;
      dur[i][j] = duration_ticks(cities[i], cities[j]);
    }
  }

  vector<int> deadlines;
  {
    int base = (11 * 60 - START_MIN) / STEP_MIN;
    for (int t = 0; t < 21; t++) {
      deadlines.push_back(base + t * 6);
    }
  }

  vector<Flight> square_desc = square;
  sort(square_desc.begin(), square_desc.end(), [](const Flight &p, const Flight &q) {
    if (p.s != q.s) return p.s > q.s;
    return p.t > q.t;
  });

  vector<int> sq_latest;
  compute_latest_all_sorted(n, deadlines, square_desc, sq_latest);

  vector<vector<pair<int, long long>>> relevant_dests(n);
  {
    long long rr = 1LL * r * r;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        long long dx = 1LL * cities[i].x - cities[j].x;
        long long dy = 1LL * cities[i].y - cities[j].y;
        long long d2 = dx * dx + dy * dy;
        if (16LL * d2 >= rr) {
          relevant_dests[i].push_back({j, cities[i].w * cities[j].w});
        }
      }
    }
  }

  vector<vector<long long>> need_score(n, vector<long long>(TICK_MAX + 1, 0));
  {
    const int dcount = (int)deadlines.size();
    for (int orig = 0; orig < n; orig++) {
      for (int s = 0; s <= TICK_MAX; s++) {
        long long val = 0;
        for (const auto &[dest, wprod] : relevant_dests[orig]) {
          for (int dk = 0; dk < dcount; dk++) {
            int sq = sq_latest[latest_idx(n, dcount, dest, dk, orig)];
            if (sq < s) {
              val += wprod;
            }
          }
        }
        need_score[orig][s] = val;
      }
    }
  }

  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int a, int b) {
    return cities[a].w > cities[b].w;
  });

  vector<int> plane_start_city(k);
  vector<int> plane_start_tick(k, 0);
  vector<int> plane_city(k), plane_time(k, 0);
  vector<vector<Flight>> plane_legs(k);
  for (int p = 0; p < k; p++) {
    plane_start_city[p] = order[p % n];
    plane_city[p] = plane_start_city[p];
  }

  vector<Flight> circle_desc;
  vector<int> ci_latest;
  compute_latest_all_sorted(n, deadlines, circle_desc, ci_latest);

  auto insert_flight_desc = [&](const Flight &f) {
    auto it = lower_bound(
        circle_desc.begin(),
        circle_desc.end(),
        f,
        [](const Flight &x, const Flight &y) {
          if (x.s != y.s) return x.s > y.s;
          return x.t > y.t;
        });
    circle_desc.insert(it, f);
  };

  int steps = 0;
  while (true) {
    if (elapsed_sec() >= TOTAL_LIMIT_SEC - 0.04) {
      break;
    }

    int p = -1;
    int best_time = TICK_MAX + 1;
    for (int i = 0; i < k; i++) {
      if (plane_time[i] <= TICK_MAX && plane_time[i] < best_time) {
        best_time = plane_time[i];
        p = i;
      }
    }
    if (p < 0) {
      break;
    }

    int a = plane_city[p];
    int s = plane_time[p];
    auto upstream_origins = collect_upstream_onehop(n, cities, circle_desc, a, s, 8);

    Candidate best;
    best.valid = false;

    for (int b = 0; b < n; b++) {
      if (b == a) continue;
      int d = dur[a][b];
      if (d <= 0) continue;
      int t = s + d;
      if (t > TICK_MAX) continue;

      long long delta = estimate_delta_upstream(
          n, deadlines, sq_latest, ci_latest, relevant_dests, upstream_origins, b, t);
      long long potential = need_score[b][t];

      Candidate cand;
      cand.valid = true;
      cand.b = b;
      cand.t = t;
      cand.dur = d;
      cand.delta = delta;
      cand.potential = potential;
      cand.pop = cities[b].w;

      if (better_candidate(cand, best)) {
        best = cand;
      }
    }

    if (!best.valid) {
      plane_time[p] = TICK_MAX + 1;
      continue;
    }

    if (best.delta <= 0 && best.potential <= 0) {
      plane_time[p] = TICK_MAX + 1;
      continue;
    }

    Flight f{a, best.b, s, best.t};
    plane_legs[p].push_back(f);
    insert_flight_desc(f);

    plane_city[p] = best.b;
    plane_time[p] = best.t;
    steps++;

    compute_latest_all_sorted(n, deadlines, circle_desc, ci_latest);

  }

  long long greedy_vci = evaluate_vci(n, deadlines, sq_latest, ci_latest, relevant_dests);

  // ---- Windowed local SA improvement ----
  vector<vector<int>> cur_routes(k);
  for (int p = 0; p < k; p++) {
    cur_routes[p] = route_from_legs(plane_legs[p]);
  }
  vector<int> cur_start_tick = plane_start_tick;
  vector<vector<Flight>> cur_legs = plane_legs;
  long long cur_score = greedy_vci;

  vector<vector<Flight>> best_legs = cur_legs;
  long long best_score = cur_score;

  auto recompute_score = [&](const vector<vector<Flight>> &legs) -> long long {
    vector<Flight> desc = flatten_desc(legs);
    vector<int> latest;
    compute_latest_all_sorted(n, deadlines, desc, latest);
    return evaluate_vci(n, deadlines, sq_latest, latest, relevant_dests);
  };

  auto proxy_leg_gain = [&](const Flight &f) -> long long {
    long long g = estimate_delta_origin_only(
        n, deadlines, sq_latest, ci_latest, relevant_dests, f.a, f.b, f.s, f.t);
    // small future-demand bonus to break ties toward useful hubs
    g += need_score[f.b][f.t] / 16;
    return g;
  };

  auto proxy_route_gain = [&](const vector<Flight> &legs) -> long long {
    long long val = 0;
    for (const auto &f : legs) {
      val += proxy_leg_gain(f);
    }
    return val;
  };

  vector<int> windows;
  const int WINDOW_STEP = 6;   // 30 min
  const int WINDOW_SIZE = 24;  // 2 hours
  for (int t = 0; t <= TICK_MAX; t += WINDOW_STEP) {
    windows.push_back(t);
  }

  XorShift rng;
  double remain = TOTAL_LIMIT_SEC - elapsed_sec();

  int sa_attempts = 0;
  int sa_accepts = 0;
  int sa_improves = 0;
  int sa_exact_evals = 0;
  int sa_prefilter_rejects = 0;
  int win_ptr = 0;

  if (remain > 0.03) {
    double sa_start = elapsed_sec();
    double sa_limit = TOTAL_LIMIT_SEC - 0.003;
    const double LOG_T0 = log(5e13);
    const double LOG_T1 = log(5e10);

    while (elapsed_sec() < sa_limit) {
      sa_attempts++;

      int w0 = windows[win_ptr];
      win_ptr++;
      if (win_ptr >= (int)windows.size()) win_ptr = 0;
      int w1 = min(TICK_MAX + 1, w0 + WINDOW_SIZE);

      int p = -1;
      vector<int> mutable_idx;
      for (int trial = 0; trial < k; trial++) {
        int cand_p = rng.next_int(0, k - 1);
        mutable_idx.clear();
        for (int idx = 0; idx < (int)cur_legs[cand_p].size(); idx++) {
          int s = cur_legs[cand_p][idx].s;
          if (w0 <= s && s < w1) {
            mutable_idx.push_back(idx);
          }
        }
        if (!mutable_idx.empty()) {
          p = cand_p;
          break;
        }
      }
      if (p < 0) {
        continue;
      }

      vector<int> cand_route = cur_routes[p];
      int cand_start = cur_start_tick[p];
      bool mutated = false;
      int move_type = rng.next_int(0, 99);

      auto pick_new_city = [&](int dep, int old) -> int {
        int L = min(n, 20);
        for (int tr = 0; tr < 24; tr++) {
          int b;
          if (rng.next_double() < 0.80) {
            b = order[rng.next_int(0, L - 1)];
          } else {
            b = rng.next_int(0, n - 1);
          }
          if (b != dep && b != old) return b;
        }
        return -1;
      };

      auto mutate_city_at = [&](int pos) {
        if (pos < 0 || pos >= (int)cand_route.size()) return;
        int dep = (pos == 0 ? plane_start_city[p] : cand_route[pos - 1]);
        int old = cand_route[pos];
        int nxt = pick_new_city(dep, old);
        if (nxt >= 0) {
          cand_route[pos] = nxt;
          mutated = true;
        }
      };

      if (move_type < 45) {
        if (cand_route.empty() || mutable_idx.empty()) continue;
        int idx = mutable_idx[rng.next_int(0, (int)mutable_idx.size() - 1)];
        mutate_city_at(idx);
        if (rng.next_double() < 0.20 && !mutable_idx.empty()) {
          int idx2 = mutable_idx[rng.next_int(0, (int)mutable_idx.size() - 1)];
          mutate_city_at(idx2);
        }
      } else if (move_type < 65) {
        if (cur_legs[p].empty()) continue;
        static const int SHIFT_OPTIONS[4] = {-2, -1, 1, 2};
        int d = SHIFT_OPTIONS[rng.next_int(0, 3)];
        int ns = cand_start + d;
        ns = max(0, min(TICK_MAX, ns));
        if (ns != cand_start) {
          cand_start = ns;
          mutated = true;
        }
      } else if (move_type < 85) {
        if (mutable_idx.empty()) continue;
        int pos = mutable_idx[rng.next_int(0, (int)mutable_idx.size() - 1)];
        pos = max(0, min((int)cand_route.size(), pos));
        int dep = (pos == 0 ? plane_start_city[p] : cand_route[pos - 1]);
        int old = (pos < (int)cand_route.size() ? cand_route[pos] : -1);
        int nxt = pick_new_city(dep, old);
        if (nxt >= 0) {
          cand_route.insert(cand_route.begin() + pos, nxt);
          mutated = true;
        }
      } else {
        if (cand_route.empty() || mutable_idx.empty()) continue;
        int idx = mutable_idx[rng.next_int(0, (int)mutable_idx.size() - 1)];
        if (0 <= idx && idx < (int)cand_route.size()) {
          cand_route.erase(cand_route.begin() + idx);
          mutated = true;
        }
      }

      if (!mutated) {
        continue;
      }

      vector<Flight> cand_legs_p =
          build_legs_from_route(plane_start_city[p], cand_start, cand_route, dur);
      cand_route = route_from_legs(cand_legs_p);

      // ---- diff-style prefilter (cheap proxy delta) ----
      long long old_proxy = proxy_route_gain(cur_legs[p]);
      long long new_proxy = proxy_route_gain(cand_legs_p);
      long long proxy_delta = new_proxy - old_proxy;

      double progress = (elapsed_sec() - sa_start) / max(1e-9, (sa_limit - sa_start));
      progress = min(1.0, max(0.0, progress));
      double temp = exp(LOG_T0 * (1.0 - progress) + LOG_T1 * progress);

      if (proxy_delta < 0) {
        double pre_x = (double)proxy_delta / (temp * 0.70);
        if (pre_x <= -50.0 || rng.next_double() >= exp(pre_x)) {
          sa_prefilter_rejects++;
          continue;
        }
      }

      vector<vector<Flight>> nxt_legs = cur_legs;
      nxt_legs[p] = std::move(cand_legs_p);
      sa_exact_evals++;

      long long nxt_score = recompute_score(nxt_legs);
      long long delta = nxt_score - cur_score;

      bool accept = false;
      if (delta >= 0) {
        accept = true;
      } else {
        double x = (double)delta / temp;
        if (x > -50.0 && rng.next_double() < exp(x)) {
          accept = true;
        }
      }

      if (!accept) {
        continue;
      }

      sa_accepts++;
      cur_score = nxt_score;
      cur_legs = std::move(nxt_legs);
      cur_routes[p] = std::move(cand_route);
      cur_start_tick[p] = cand_start;

      if (cur_score > best_score) {
        best_score = cur_score;
        best_legs = cur_legs;
        sa_improves++;
      }
    }
  }

  cerr << "[summary] greedy_v_ci=" << greedy_vci
       << " best_v_ci=" << best_score
       << " sa_attempts=" << sa_attempts
       << " sa_exact_evals=" << sa_exact_evals
       << " sa_prefilter_rejects=" << sa_prefilter_rejects
       << " sa_accepts=" << sa_accepts
       << " sa_improves=" << sa_improves
       << " elapsed=" << elapsed_sec() << "s\n";

  for (int p = 0; p < k; p++) {
    cout << best_legs[p].size() << '\n';
    for (const auto &f : best_legs[p]) {
      cout << (f.a + 1) << ' ' << idx_to_time(f.s) << ' '
           << (f.b + 1) << ' ' << idx_to_time(f.t) << '\n';
    }
  }

  return 0;
}