#1150736 (Rust) No.5023 Airlines Optimization

• 問題: No.5023 Airlines Optimization
• ユーザー: ikoma
• 提出日時: 2026-02-28 16:51:40
• 言語: Rust (1.93.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 967 ms / 1,000 ms
• コード長: 22,378 bytes
• コンパイル時間: 5,501 ms
• コンパイル使用メモリ: 225,572 KB
• 実行使用メモリ: 7,848 KB
• スコア: 42,124,345
• 最終ジャッジ日時: 2026-02-28 16:53:30
• 合計ジャッジ時間: 107,342 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

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

ソースコード

use proconio::input;
use std::cmp::Reverse;
use std::time::Instant;

const START_MINUTE: i32 = 6 * 60;
const END_MINUTE: i32 = 21 * 60;
const SLOT_STEP: i32 = 5;
const MAX_SLOT: i16 = ((END_MINUTE - START_MINUTE) / SLOT_STEP) as i16; // 180
const SHARE_DISTANCE: i64 = 250;
const TIME_LIMIT_SEC: f64 = 0.96;

#[derive(Clone, Copy)]
struct City {
    x: i32,
    y: i32,
    w: i64,
}

#[derive(Clone, Copy)]
struct Flight {
    a: usize,
    s: i16,
    b: usize,
    t: i16,
}

#[derive(Clone)]
struct Solution {
    routes: Vec<Vec<Flight>>,
}

struct Problem {
    n: usize,
    k: usize,
    durations: Vec<Vec<i16>>, // [from][to]
    targets: Vec<i16>,
    srcs_by_dest: Vec<Vec<(usize, i128)>>,
    total_weight: i128,
    sq_latest_flat: Vec<Vec<i16>>, // [dest][ti*n + src]
    order: Vec<usize>,
    hubs: Vec<usize>,
    spokes: Vec<usize>,
}

struct EvalState {
    flights_desc: Vec<Flight>,
    reach: Vec<u64>,
    dest_ci: Vec<i128>,
    ci_sum: i128,
    score: i64,
}

struct EvalScratch {
    flights_desc: Vec<Flight>,
    reach: Vec<u64>,
    best: Vec<i16>,
    affected: Vec<usize>,
    updated_dest_ci: Vec<i128>,
}

#[derive(Clone, Copy)]
struct XorShift64 {
    x: u64,
}

impl XorShift64 {
    fn new(seed: u64) -> Self {
        let mut s = seed;
        if s == 0 {
            s = 0x9e3779b97f4a7c15;
        }
        Self { x: s }
    }

    #[inline]
    fn next_u64(&mut self) -> u64 {
        let mut x = self.x;
        x ^= x << 7;
        x ^= x >> 9;
        self.x = x;
        x
    }

    #[inline]
    fn gen_f64(&mut self) -> f64 {
        const DEN: f64 = (1u64 << 53) as f64;
        ((self.next_u64() >> 11) as f64) / DEN
    }

    #[inline]
    fn gen_bool(&mut self, p: f64) -> bool {
        self.gen_f64() < p
    }

    #[inline]
    fn gen_usize(&mut self, l: usize, r: usize) -> usize {
        debug_assert!(l < r);
        l + (self.next_u64() as usize % (r - l))
    }

    #[inline]
    fn gen_usize_inclusive(&mut self, l: usize, r: usize) -> usize {
        debug_assert!(l <= r);
        l + (self.next_u64() as usize % (r - l + 1))
    }

    #[inline]
    fn gen_i16_inclusive(&mut self, l: i16, r: i16) -> i16 {
        debug_assert!(l <= r);
        let w = (r - l + 1) as usize;
        l + (self.next_u64() as usize % w) as i16
    }
}

enum UndoAction {
    Shift {
        p: usize,
        i: usize,
        old_s: i16,
        old_t: i16,
    },
    AddLast {
        p: usize,
    },
    RemoveLast {
        p: usize,
        removed: Flight,
    },
    ChangeLastDest {
        p: usize,
        old_b: usize,
        old_t: i16,
    },
    RebuildSuffix {
        p: usize,
        cut: usize,
        old_suffix: Vec<Flight>,
    },
}

impl UndoAction {
    fn rollback(self, sol: &mut Solution) {
        match self {
            UndoAction::Shift { p, i, old_s, old_t } => {
                sol.routes[p][i].s = old_s;
                sol.routes[p][i].t = old_t;
            }
            UndoAction::AddLast { p } => {
                sol.routes[p].pop();
            }
            UndoAction::RemoveLast { p, removed } => {
                sol.routes[p].push(removed);
            }
            UndoAction::ChangeLastDest { p, old_b, old_t } => {
                let idx = sol.routes[p].len() - 1;
                sol.routes[p][idx].b = old_b;
                sol.routes[p][idx].t = old_t;
            }
            UndoAction::RebuildSuffix { p, cut, old_suffix } => {
                sol.routes[p].truncate(cut);
                sol.routes[p].extend(old_suffix);
            }
        }
    }
}

struct MoveInfo {
    undo: UndoAction,
    touched_b: Vec<usize>,
    topo_changed: bool,
}

struct CandEval {
    ci_sum: i128,
    score: i64,
    topo_changed: bool,
}

fn parse_time_to_slot(s: &str) -> i16 {
    let hh: i32 = s[0..2].parse().unwrap();
    let mm: i32 = s[3..5].parse().unwrap();
    ((hh * 60 + mm - START_MINUTE) / SLOT_STEP) as i16
}

fn slot_to_time(slot: i16) -> String {
    let m = START_MINUTE + (slot as i32) * SLOT_STEP;
    format!("{:02}:{:02}", m / 60, m % 60)
}

fn ceil_to_5(x: f64) -> i32 {
    ((x / 5.0).ceil() as i32) * 5
}

fn flight_duration_slots(c1: City, c2: City) -> i16 {
    let dx = (c1.x - c2.x) as f64;
    let dy = (c1.y - c2.y) as f64;
    let d = (dx * dx + dy * dy).sqrt();
    (ceil_to_5(60.0 * d / 800.0 + 40.0) / 5) as i16
}

#[inline]
fn score_from_ci(ci: i128, total: i128) -> i64 {
    if total == 0 {
        0
    } else {
        ((ci * 1_000_000) / total) as i64
    }
}

fn build_flights_desc(routes: &[Vec<Flight>], out: &mut Vec<Flight>) {
    out.clear();
    for r in routes {
        out.extend(r.iter().copied());
    }
    out.sort_unstable_by_key(|f| Reverse(f.s));
}

fn compute_reach(n: usize, flights: &[Flight], reach: &mut Vec<u64>) {
    reach.resize(n, 0);
    for (i, v) in reach.iter_mut().enumerate() {
        *v = 1u64 << i;
    }
    for &f in flights {
        reach[f.a] |= 1u64 << f.b;
    }
    for k in 0..n {
        let rk = reach[k];
        for i in 0..n {
            if ((reach[i] >> k) & 1) == 1 {
                reach[i] |= rk;
            }
        }
    }
}

fn recompute_dest_score_only(
    problem: &Problem,
    flights_desc: &[Flight],
    dest: usize,
    best: &mut [i16],
) -> i128 {
    let srcs = &problem.srcs_by_dest[dest];
    if srcs.is_empty() {
        return 0;
    }

    let mut ci = 0i128;
    let n = problem.n;
    let sq_flat = &problem.sq_latest_flat[dest];
    for (ti, &deadline) in problem.targets.iter().enumerate() {
        best.fill(-1);
        best[dest] = deadline;

        for &f in flights_desc {
            let bb = best[f.b];
            if f.t <= bb && f.s > best[f.a] {
                best[f.a] = f.s;
            }
        }

        let base = ti * n;
        let sq_row = &sq_flat[base..base + n];
        for &(src, w) in srcs {
            if sq_row[src] < best[src] {
                ci += w;
            }
        }
    }
    ci
}

fn init_eval_state(problem: &Problem, sol: &Solution) -> EvalState {
    let mut flights_desc = Vec::with_capacity(512);
    build_flights_desc(&sol.routes, &mut flights_desc);

    let mut reach = Vec::with_capacity(problem.n);
    compute_reach(problem.n, &flights_desc, &mut reach);

    let mut best = vec![-1; problem.n];
    let mut dest_ci = vec![0i128; problem.n];
    let mut ci_sum = 0i128;

    for d in 0..problem.n {
        let c = recompute_dest_score_only(problem, &flights_desc, d, &mut best);
        dest_ci[d] = c;
        ci_sum += c;
    }

    let score = score_from_ci(ci_sum, problem.total_weight);
    EvalState {
        flights_desc,
        reach,
        dest_ci,
        ci_sum,
        score,
    }
}

fn build_one_hub_solution(problem: &Problem, hub: usize) -> Solution {
    let mut routes = vec![Vec::<Flight>::new(); problem.k];
    let targets: Vec<usize> = problem.order.iter().copied().filter(|&x| x != hub).collect();
    if targets.is_empty() {
        return Solution { routes };
    }

    for p in 0..problem.k {
        let target = targets[p % targets.len()];
        let mut city = hub;
        let mut time = (p % 3) as i16;

        loop {
            let next = if city == hub { target } else { hub };
            let arr = time + problem.durations[city][next];
            if arr > MAX_SLOT {
                break;
            }
            routes[p].push(Flight {
                a: city,
                s: time,
                b: next,
                t: arr,
            });
            city = next;
            time = arr;
        }
    }

    Solution { routes }
}

fn build_multi_hub_solution(problem: &Problem) -> Solution {
    let mut routes = vec![Vec::<Flight>::new(); problem.k];
    let hub_len = problem.hubs.len();

    for p in 0..problem.k {
        let base_hub = problem.hubs[p % hub_len];
        let mut city = base_hub;
        let mut time = (p % 6) as i16;
        let mut turn = 0usize;

        loop {
            let next = if city == base_hub {
                if !problem.spokes.is_empty() {
                    problem.spokes[(p + turn * 5) % problem.spokes.len()]
                } else {
                    problem.hubs[(p + turn + 1) % hub_len]
                }
            } else if hub_len >= 2 && turn % 3 == 2 {
                problem.hubs[(p + turn + 1) % hub_len]
            } else {
                base_hub
            };

            if next == city {
                break;
            }
            let arr = time + problem.durations[city][next];
            if arr > MAX_SLOT {
                break;
            }
            routes[p].push(Flight {
                a: city,
                s: time,
                b: next,
                t: arr,
            });
            city = next;
            let wait = if time < 96 { ((p + turn) & 1) as i16 } else { 0 };
            time = arr + wait;
            turn += 1;
            if time > MAX_SLOT {
                break;
            }
        }
    }

    Solution { routes }
}

fn choose_next_city(problem: &Problem, from: usize, rng: &mut XorShift64) -> Option<usize> {
    let top = problem.order.len().min(16);
    for _ in 0..24 {
        let idx = if rng.gen_bool(0.7) {
            rng.gen_usize(0, top)
        } else {
            rng.gen_usize(0, problem.n)
        };
        let v = problem.order[idx];
        if v != from {
            return Some(v);
        }
    }
    (0..problem.n).find(|&x| x != from)
}

fn op_shift_time(sol: &mut Solution, problem: &Problem, rng: &mut XorShift64) -> Option<MoveInfo> {
    for _ in 0..10 {
        let p = rng.gen_usize(0, problem.k);
        let len = sol.routes[p].len();
        if len == 0 {
            continue;
        }
        let i = rng.gen_usize(0, len);
        let delta = rng.gen_i16_inclusive(-3, 3);
        if delta == 0 {
            continue;
        }

        let ns = sol.routes[p][i].s + delta;
        let nt = sol.routes[p][i].t + delta;
        if ns < 0 || nt > MAX_SLOT {
            continue;
        }
        if i > 0 && ns < sol.routes[p][i - 1].t {
            continue;
        }
        if i + 1 < len && nt > sol.routes[p][i + 1].s {
            continue;
        }

        let old_s = sol.routes[p][i].s;
        let old_t = sol.routes[p][i].t;
        let b = sol.routes[p][i].b;
        sol.routes[p][i].s = ns;
        sol.routes[p][i].t = nt;
        return Some(MoveInfo {
            undo: UndoAction::Shift { p, i, old_s, old_t },
            touched_b: vec![b],
            topo_changed: false,
        });
    }
    None
}

fn op_add_last(sol: &mut Solution, problem: &Problem, rng: &mut XorShift64) -> Option<MoveInfo> {
    let p = rng.gen_usize(0, problem.k);
    let (from, dep) = if sol.routes[p].is_empty() {
        (
            problem.hubs[p % problem.hubs.len()],
            rng.gen_i16_inclusive(0, 60),
        )
    } else {
        let last = *sol.routes[p].last().unwrap();
        (last.b, last.t + rng.gen_i16_inclusive(0, 2))
    };

    if dep > MAX_SLOT {
        return None;
    }
    let to = choose_next_city(problem, from, rng)?;
    let arr = dep + problem.durations[from][to];
    if arr > MAX_SLOT {
        return None;
    }

    sol.routes[p].push(Flight {
        a: from,
        s: dep,
        b: to,
        t: arr,
    });
    Some(MoveInfo {
        undo: UndoAction::AddLast { p },
        touched_b: vec![to],
        topo_changed: true,
    })
}

fn op_remove_last(sol: &mut Solution, problem: &Problem, rng: &mut XorShift64) -> Option<MoveInfo> {
    for _ in 0..10 {
        let p = rng.gen_usize(0, problem.k);
        if let Some(removed) = sol.routes[p].pop() {
            return Some(MoveInfo {
                undo: UndoAction::RemoveLast { p, removed },
                touched_b: vec![removed.b],
                topo_changed: true,
            });
        }
    }
    None
}

fn op_change_last_dest(
    sol: &mut Solution,
    problem: &Problem,
    rng: &mut XorShift64,
) -> Option<MoveInfo> {
    for _ in 0..10 {
        let p = rng.gen_usize(0, problem.k);
        if sol.routes[p].is_empty() {
            continue;
        }

        let idx = sol.routes[p].len() - 1;
        let old = sol.routes[p][idx];
        let to = choose_next_city(problem, old.a, rng)?;
        if to == old.b {
            continue;
        }
        let arr = old.s + problem.durations[old.a][to];
        if arr > MAX_SLOT {
            continue;
        }

        sol.routes[p][idx].b = to;
        sol.routes[p][idx].t = arr;
        return Some(MoveInfo {
            undo: UndoAction::ChangeLastDest {
                p,
                old_b: old.b,
                old_t: old.t,
            },
            touched_b: vec![old.b, to],
            topo_changed: true,
        });
    }
    None
}

fn op_rebuild_suffix(
    sol: &mut Solution,
    problem: &Problem,
    rng: &mut XorShift64,
) -> Option<MoveInfo> {
    for _ in 0..8 {
        let p = rng.gen_usize(0, problem.k);
        let len = sol.routes[p].len();
        let cut = if len == 0 {
            0
        } else {
            rng.gen_usize_inclusive(0, len)
        };

        let old_suffix = sol.routes[p][cut..].to_vec();
        let mut touched = Vec::with_capacity(old_suffix.len() + 6);
        for f in &old_suffix {
            touched.push(f.b);
        }

        sol.routes[p].truncate(cut);
        let (mut city, mut time) = if sol.routes[p].is_empty() {
            (
                problem.hubs[p % problem.hubs.len()],
                rng.gen_i16_inclusive(0, 90),
            )
        } else {
            let last = *sol.routes[p].last().unwrap();
            (last.b, last.t)
        };

        let mut added = false;
        let add_cnt = rng.gen_usize_inclusive(1, 4);
        for _ in 0..add_cnt {
            let to = match choose_next_city(problem, city, rng) {
                Some(v) => v,
                None => break,
            };
            let dep = time + rng.gen_i16_inclusive(0, 2);
            let arr = dep + problem.durations[city][to];
            if dep > MAX_SLOT || arr > MAX_SLOT || city == to {
                break;
            }
            sol.routes[p].push(Flight {
                a: city,
                s: dep,
                b: to,
                t: arr,
            });
            touched.push(to);
            city = to;
            time = arr;
            added = true;
        }

        if added || !old_suffix.is_empty() {
            return Some(MoveInfo {
                undo: UndoAction::RebuildSuffix { p, cut, old_suffix },
                touched_b: touched,
                topo_changed: true,
            });
        }

        // no-op を避ける
        sol.routes[p].extend(old_suffix);
    }
    None
}

fn mutate(sol: &mut Solution, problem: &Problem, rng: &mut XorShift64) -> Option<MoveInfo> {
    for _ in 0..20 {
        let op = rng.gen_usize(0, 5);
        let ret = match op {
            0 => op_shift_time(sol, problem, rng),
            1 => op_add_last(sol, problem, rng),
            2 => op_remove_last(sol, problem, rng),
            3 => op_change_last_dest(sol, problem, rng),
            _ => op_rebuild_suffix(sol, problem, rng),
        };
        if ret.is_some() {
            return ret;
        }
    }
    None
}

fn evaluate_candidate(
    problem: &Problem,
    sol: &Solution,
    cur: &EvalState,
    scratch: &mut EvalScratch,
    mv: &MoveInfo,
) -> CandEval {
    build_flights_desc(&sol.routes, &mut scratch.flights_desc);

    if mv.topo_changed {
        compute_reach(problem.n, &scratch.flights_desc, &mut scratch.reach);
    }

    let mut affected_mask = 0u64;
    for &b in &mv.touched_b {
        if b >= problem.n {
            continue;
        }
        affected_mask |= cur.reach[b];
        if mv.topo_changed {
            affected_mask |= scratch.reach[b];
        }
    }

    scratch.affected.clear();
    if affected_mask == 0 {
        return CandEval {
            ci_sum: cur.ci_sum,
            score: cur.score,
            topo_changed: mv.topo_changed,
        };
    }

    for d in 0..problem.n {
        if ((affected_mask >> d) & 1) == 1 {
            scratch.affected.push(d);
        }
    }

    scratch.updated_dest_ci.resize(scratch.affected.len(), 0);
    let mut ci_sum = cur.ci_sum;
    for (idx, &d) in scratch.affected.iter().enumerate() {
        ci_sum -= cur.dest_ci[d];
        let c = recompute_dest_score_only(problem, &scratch.flights_desc, d, &mut scratch.best);
        scratch.updated_dest_ci[idx] = c;
        ci_sum += c;
    }

    CandEval {
        ci_sum,
        score: score_from_ci(ci_sum, problem.total_weight),
        topo_changed: mv.topo_changed,
    }
}

fn apply_candidate(cur: &mut EvalState, scratch: &mut EvalScratch, cand: &CandEval) {
    std::mem::swap(&mut cur.flights_desc, &mut scratch.flights_desc);
    if cand.topo_changed {
        cur.reach.copy_from_slice(&scratch.reach);
    }

    for (idx, &d) in scratch.affected.iter().enumerate() {
        cur.dest_ci[d] = scratch.updated_dest_ci[idx];
    }

    cur.ci_sum = cand.ci_sum;
    cur.score = cand.score;
}

fn main() {
    input! {
        n: usize,
        _r: i32,
    }
    let mut cities = Vec::with_capacity(n);
    for _ in 0..n {
        input! { x: i32, y: i32, w: i64 }
        cities.push(City { x, y, w });
    }

    input! { m: usize }
    let mut square_flights = Vec::with_capacity(m);
    for _ in 0..m {
        input! {
            a1: usize,
            s: String,
            b1: usize,
            t: String,
        }
        square_flights.push(Flight {
            a: a1 - 1,
            s: parse_time_to_slot(&s),
            b: b1 - 1,
            t: parse_time_to_slot(&t),
        });
    }

    input! { k: usize }

    let mut durations = vec![vec![0i16; n]; n];
    for i in 0..n {
        for j in 0..n {
            if i == j {
                continue;
            }
            durations[i][j] = flight_duration_slots(cities[i], cities[j]);
        }
    }

    let mut targets = Vec::new();
    for minute in (11 * 60..=21 * 60).step_by(30) {
        targets.push(((minute - START_MINUTE) / SLOT_STEP) as i16);
    }
    let mut srcs_by_dest = vec![Vec::<(usize, i128)>::new(); n];
    let mut total_weight = 0i128;
    for i in 0..n {
        for j in 0..n {
            if i == j {
                continue;
            }
            let dx = (cities[i].x - cities[j].x) as i64;
            let dy = (cities[i].y - cities[j].y) as i64;
            if dx * dx + dy * dy < SHARE_DISTANCE * SHARE_DISTANCE {
                continue;
            }
            let w = (cities[i].w as i128) * (cities[j].w as i128);
            srcs_by_dest[j].push((i, w));
            total_weight += w * (targets.len() as i128);
        }
    }

    square_flights.sort_unstable_by_key(|f| Reverse(f.s));
    let row_len = n * targets.len();
    let mut sq_latest_flat = vec![vec![-1i16; row_len]; n];
    let mut best_tmp = vec![-1i16; n];
    for d in 0..n {
        for (ti, &deadline) in targets.iter().enumerate() {
            best_tmp.fill(-1);
            best_tmp[d] = deadline;
            for &f in &square_flights {
                let bb = best_tmp[f.b];
                if f.t <= bb && f.s > best_tmp[f.a] {
                    best_tmp[f.a] = f.s;
                }
            }
            let base = ti * n;
            sq_latest_flat[d][base..base + n].copy_from_slice(&best_tmp);
        }
    }

    let mut order: Vec<usize> = (0..n).collect();
    order.sort_by_key(|&i| Reverse(cities[i].w));
    let hub_cnt = n.min(4).max(1);
    let hubs = order[..hub_cnt].to_vec();
    let spokes = if n > hub_cnt {
        order[hub_cnt..].to_vec()
    } else {
        Vec::new()
    };

    let problem = Problem {
        n,
        k,
        durations,
        targets,
        srcs_by_dest,
        total_weight,
        sq_latest_flat,
        order,
        hubs,
        spokes,
    };

    let mut init_candidates = Vec::new();
    init_candidates.push(build_multi_hub_solution(&problem));
    for &hub in problem.hubs.iter().take(4) {
        init_candidates.push(build_one_hub_solution(&problem, hub));
    }

    let mut best_sol = init_candidates[0].clone();
    let mut best_eval = init_eval_state(&problem, &best_sol);
    for sol in init_candidates.iter().skip(1) {
        let st = init_eval_state(&problem, sol);
        if st.score > best_eval.score {
            best_eval = st;
            best_sol = sol.clone();
        }
    }

    let mut cur_sol = best_sol.clone();
    let mut cur_eval = best_eval;
    let mut best_score = cur_eval.score;

    let mut scratch = EvalScratch {
        flights_desc: Vec::with_capacity(512),
        reach: vec![0u64; n],
        best: vec![-1; n],
        affected: Vec::with_capacity(n),
        updated_dest_ci: Vec::with_capacity(n),
    };

    let start = Instant::now();
    let mut rng = XorShift64::new(0x5eed1234);
    let temp0 = 450.0;
    let temp1 = 5.0;

    let mut loop_cnt: usize = 0;
    let mut accept_cnt: usize = 0;

    while start.elapsed().as_secs_f64() < TIME_LIMIT_SEC {
        loop_cnt += 1;

        let mv = match mutate(&mut cur_sol, &problem, &mut rng) {
            Some(v) => v,
            None => continue,
        };

        let cand = evaluate_candidate(&problem, &cur_sol, &cur_eval, &mut scratch, &mv);
        let diff = cand.score - cur_eval.score;

        let ratio = (start.elapsed().as_secs_f64() / TIME_LIMIT_SEC).clamp(0.0, 1.0);
        let temp = temp0 * (1.0 - ratio) + temp1 * ratio;
        let accept = if diff >= 0 {
            true
        } else {
            rng.gen_f64() < ((diff as f64) / temp).exp()
        };

        if accept {
            accept_cnt += 1;
            apply_candidate(&mut cur_eval, &mut scratch, &cand);
            if cur_eval.score > best_score {
                best_score = cur_eval.score;
                best_sol = cur_sol.clone();
            }
        } else {
            mv.undo.rollback(&mut cur_sol);
        }
    }

    for r in best_sol.routes {
        println!("{}", r.len());
        for f in r {
            println!(
                "{} {} {} {}",
                f.a + 1,
                slot_to_time(f.s),
                f.b + 1,
                slot_to_time(f.t)
            );
        }
    }

    eprintln!("n_loop: {}", loop_cnt);
    eprintln!("accept: {}", accept_cnt);
}