#1150728 (Rust) No.5023 Airlines Optimization

• 問題: No.5023 Airlines Optimization
• ユーザー: ikoma
• 提出日時: 2026-02-28 16:41:09
• 言語: Rust (1.93.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 968 ms / 1,000 ms
• コード長: 17,553 bytes
• コンパイル時間: 4,296 ms
• コンパイル使用メモリ: 229,640 KB
• 実行使用メモリ: 7,848 KB
• スコア: 39,470,346
• 最終ジャッジ日時: 2026-02-28 16:43:09
• 合計ジャッジ時間: 107,413 ms
• ジャッジサーバーID （参考情報）: judge2 / judge7

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

コンパイルメッセージ

warning: variable `cnt_accept` is assigned to, but never used
   --> src/main.rs:634:6
    |
634 |     let mut cnt_accept = 0;
    |         ^^^^^^^^^^^^^^
    |
    = note: consider using `_cnt_accept` instead
    = note: `#[warn(unused_variables)]` (part of `#[warn(unused)]`) on by default

warning: value assigned to `cnt_accept` is never read
   --> src/main.rs:655:4
    |
655 |             cnt_accept += 1;
    |             ^^^^^^^^^^^^^^^
    |
    = help: maybe it is overwritten before being read?
    = note: `#[warn(unused_assignments)]` (part of `#[warn(unused)]`) on by default

ソースコード

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>>, // slots
    targets: Vec<i16>,
    srcs_by_dest: Vec<Vec<(usize, i128)>>,
    total_weight: i128,
    sq_latest: Vec<Vec<Vec<i16>>>, // [dest][target_idx][src]
    order: Vec<usize>,
    hubs: Vec<usize>,
    spokes: Vec<usize>,
}

struct EvalBuf {
    flights_desc: Vec<Flight>,
    best: Vec<i16>,
}

#[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_bool(&mut self, p: f64) -> bool {
        self.gen_f64() < p
    }

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

    #[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 u16 as usize;
        l + (self.next_u64() as usize % w) as i16
    }
}

enum UndoAction {
    One {
        p: usize,
        old: Vec<Flight>,
    },
    Two {
        p: usize,
        old_p: Vec<Flight>,
        q: usize,
        old_q: Vec<Flight>,
    },
}

impl UndoAction {
    fn rollback(self, sol: &mut Solution) {
        match self {
            UndoAction::One { p, old } => sol.routes[p] = old,
            UndoAction::Two { p, old_p, q, old_q } => {
                sol.routes[p] = old_p;
                sol.routes[q] = old_q;
            }
        }
    }
}

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
}

fn evaluate_score(problem: &Problem, sol: &Solution, buf: &mut EvalBuf) -> i64 {
    buf.flights_desc.clear();
    for r in &sol.routes {
        buf.flights_desc.extend(r.iter().copied());
    }
    buf.flights_desc.sort_unstable_by_key(|f| Reverse(f.s));

    let mut ci_sum = 0i128;
    for dest in 0..problem.n {
        if problem.srcs_by_dest[dest].is_empty() {
            continue;
        }
        let sq_dest = &problem.sq_latest[dest];
        let srcs = &problem.srcs_by_dest[dest];

        for (ti, &deadline) in problem.targets.iter().enumerate() {
            buf.best.fill(-1);
            buf.best[dest] = deadline;

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

            let sq_row = &sq_dest[ti];
            for &(src, w) in srcs {
                if sq_row[src] < buf.best[src] {
                    ci_sum += w;
                }
            }
        }
    }

    if problem.total_weight == 0 {
        0
    } else {
        ((ci_sum * 1_000_000) / problem.total_weight) as i64
    }
}

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<UndoAction> {
    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 = sol.routes[p].clone();
        sol.routes[p][i].s = ns;
        sol.routes[p][i].t = nt;
        return Some(UndoAction::One { p, old });
    }
    None
}

fn op_add_last(sol: &mut Solution, problem: &Problem, rng: &mut XorShift64) -> Option<UndoAction> {
    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;
    }

    let old = sol.routes[p].clone();
    sol.routes[p].push(Flight {
        a: from,
        s: dep,
        b: to,
        t: arr,
    });
    Some(UndoAction::One { p, old })
}

fn op_remove_last(
    sol: &mut Solution,
    problem: &Problem,
    rng: &mut XorShift64,
) -> Option<UndoAction> {
    for _ in 0..10 {
        let p = rng.gen_usize(0, problem.k);
        if sol.routes[p].is_empty() {
            continue;
        }
        let old = sol.routes[p].clone();
        sol.routes[p].pop();
        return Some(UndoAction::One { p, old });
    }
    None
}

fn op_change_last_dest(
    sol: &mut Solution,
    problem: &Problem,
    rng: &mut XorShift64,
) -> Option<UndoAction> {
    for _ in 0..10 {
        let p = rng.gen_usize(0, problem.k);
        if sol.routes[p].is_empty() {
            continue;
        }
        let last = *sol.routes[p].last().unwrap();
        let to = choose_next_city(problem, last.a, rng)?;
        if to == last.b {
            continue;
        }
        let arr = last.s + problem.durations[last.a][to];
        if arr > MAX_SLOT {
            continue;
        }

        let old = sol.routes[p].clone();
        let idx = sol.routes[p].len() - 1;
        sol.routes[p][idx].b = to;
        sol.routes[p][idx].t = arr;
        return Some(UndoAction::One { p, old });
    }
    None
}

fn op_swap_routes(
    sol: &mut Solution,
    problem: &Problem,
    rng: &mut XorShift64,
) -> Option<UndoAction> {
    if problem.k <= 1 {
        return None;
    }
    let p = rng.gen_usize(0, problem.k);
    let mut q = rng.gen_usize(0, problem.k);
    if p == q {
        q = (q + 1) % problem.k;
    }

    let old_p = sol.routes[p].clone();
    let old_q = sol.routes[q].clone();
    sol.routes.swap(p, q);
    Some(UndoAction::Two { p, old_p, q, old_q })
}

fn op_rebuild_suffix(
    sol: &mut Solution,
    problem: &Problem,
    rng: &mut XorShift64,
) -> Option<UndoAction> {
    for _ in 0..8 {
        let p = rng.gen_usize(0, problem.k);
        let old = sol.routes[p].clone();

        let cut = if old.is_empty() {
            0
        } else {
            rng.gen_usize_inclusive(0, old.len())
        };
        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,
            });
            city = to;
            time = arr;
            added = true;
        }

        if added || cut != old.len() {
            return Some(UndoAction::One { p, old });
        }

        sol.routes[p] = old;
    }
    None
}

fn mutate(sol: &mut Solution, problem: &Problem, rng: &mut XorShift64) -> Option<UndoAction> {
    for _ in 0..20 {
        let op = rng.gen_usize(0, 6);
        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),
            4 => op_swap_routes(sol, problem, rng),
            _ => op_rebuild_suffix(sol, problem, rng),
        };
        if ret.is_some() {
            return ret;
        }
    }
    None
}

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 mut sq_latest = vec![vec![vec![-1i16; n]; targets.len()]; n];
    let mut best_tmp = vec![-1i16; n];
    for dest in 0..n {
        for (ti, &deadline) in targets.iter().enumerate() {
            best_tmp.fill(-1);
            best_tmp[dest] = 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;
                }
            }
            sq_latest[dest][ti].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,
        order,
        hubs,
        spokes,
    };

    let mut eval_buf = EvalBuf {
        flights_desc: Vec::with_capacity(512),
        best: vec![-1; problem.n],
    };

    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_score = i64::MIN;
    for sol in &init_candidates {
        let score = evaluate_score(&problem, sol, &mut eval_buf);
        if score > best_score {
            best_score = score;
            best_sol = sol.clone();
        }
    }

    let mut cur_sol = best_sol.clone();
    let mut cur_score = best_score;

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

	let mut cnt_iter = 0;
	let mut cnt_accept = 0;

    while start.elapsed().as_secs_f64() < TIME_LIMIT_SEC {
		cnt_iter += 1;
        let undo = match mutate(&mut cur_sol, &problem, &mut rng) {
            Some(v) => v,
            None => continue,
        };

        let cand_score = evaluate_score(&problem, &cur_sol, &mut eval_buf);
        let diff = cand_score - cur_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 {
			cnt_accept += 1;
            cur_score = cand_score;
            if cand_score > best_score {
                best_score = cand_score;
                best_sol = cur_sol.clone();
            }
        } else {
            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: {}", cnt_iter);
}