#1149347 (Rust) No.5023 Airlines Optimization

• 問題: No.5023 Airlines Optimization
• ユーザー: rhoo
• 提出日時: 2026-02-25 23:02:12
• 言語: Rust (1.93.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 680 ms / 1,000 ms
• コード長: 15,627 bytes
• コンパイル時間: 3,546 ms
• コンパイル使用メモリ: 224,120 KB
• 実行使用メモリ: 12,928 KB
• スコア: 53,119,364
• 最終ジャッジ日時: 2026-02-25 23:03:37
• 合計ジャッジ時間: 69,328 ms
• ジャッジサーバーID （参考情報）: judge6 / judge1

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

ソースコード

use std::io::{self, Read};

const START_TIME: i32 = 6 * 60;
const END_TIME: i32 = 21 * 60;
const INF_NEG: i32 = -1_000_000_000;
const BEAM_WIDTH: usize = 1;
const HISTORY_LEN: usize = 10;
const REFINE_ROUNDS: usize = 1;
const TIME_EQ_MIN: i32 = 10;
const SIGNATURE_BITS: usize = 2048;
const SIGNATURE_WORDS: usize = SIGNATURE_BITS / 64;

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

#[derive(Clone, Copy)]
struct Flight {
    u: usize,
    v: usize,
    dep: i32,
    arr: i32,
}

#[derive(Clone, Copy)]
#[allow(dead_code)]
struct Opportunity {
    u: usize,
    v: usize,
    min_dep: i32,
    deadline: i32,
    points: i64,
}

fn read_value<T: std::str::FromStr>(it: &mut std::str::SplitWhitespace<'_>) -> T
where
    T::Err: std::fmt::Debug,
{
    it.next()
        .unwrap()
        .trim_start_matches('\u{feff}')
        .parse::<T>()
        .unwrap()
}

fn parse_time(token: &str) -> i32 {
    let mut it = token.trim_start_matches('\u{feff}').split(':');
    let h: i32 = it.next().unwrap().parse().unwrap();
    let m: i32 = it.next().unwrap().parse().unwrap();
    h * 60 + m
}

fn format_time(t: i32) -> String {
    format!("{:02}:{:02}", t / 60, t % 60)
}

fn distance(c1: City, c2: City) -> f64 {
    let dx = (c1.x - c2.x) as f64;
    let dy = (c1.y - c2.y) as f64;
    (dx * dx + dy * dy).sqrt()
}

fn required_duration(c1: City, c2: City) -> i32 {
    let d = distance(c1, c2);
    let raw = 60.0 * d / 800.0 + 40.0;
    (raw / 5.0).ceil() as i32 * 5
}

fn target_deadlines() -> Vec<i32> {
    (0..=20).map(|i| 11 * 60 + i * 30).collect()
}

fn sort_by_dep_desc(mut flights: Vec<Flight>) -> Vec<Flight> {
    flights.sort_by_key(|f| -f.dep);
    flights
}

fn compute_latest_departure(
    n: usize,
    flights_desc: &[Flight],
    dest: usize,
    deadline: i32,
) -> Vec<i32> {
    let mut latest = vec![INF_NEG; n];
    latest[dest] = deadline;
    for &f in flights_desc {
        if f.arr <= latest[f.v] {
            latest[f.u] = latest[f.u].max(f.dep);
        }
    }
    latest
}

fn make_far_pair_table(cities: &[City], r: i32) -> Vec<Vec<bool>> {
    let n = cities.len();
    let threshold = r as f64 * 0.25;
    let mut far = vec![vec![false; n]; n];
    for i in 0..n {
        for j in 0..n {
            far[i][j] = distance(cities[i], cities[j]) >= threshold;
        }
    }
    far
}

fn enumerate_opportunities(cities: &[City], r: i32, square_desc: &[Flight]) -> Vec<Opportunity> {
    let n = cities.len();
    let far = make_far_pair_table(cities, r);
    let deadlines = target_deadlines();
    let mut opportunities = Vec::new();

    for &deadline in &deadlines {
        for dest in 0..n {
            let latest_sq = compute_latest_departure(n, square_desc, dest, deadline);
            for src in 0..n {
                if !far[src][dest] {
                    continue;
                }
                let s_sq = latest_sq[src];
                let min_dep = if s_sq < START_TIME {
                    START_TIME
                } else {
                    s_sq + 5
                };
                opportunities.push(Opportunity {
                    u: src,
                    v: dest,
                    min_dep,
                    deadline,
                    points: cities[src].w * cities[dest].w,
                });
            }
        }
    }
    opportunities
}

fn precompute_latest_table(
    n: usize,
    flights_desc: &[Flight],
    deadlines: &[i32],
) -> Vec<Vec<Vec<i32>>> {
    let mut table = Vec::with_capacity(deadlines.len());
    for &deadline in deadlines {
        let mut by_dest = Vec::with_capacity(n);
        for dest in 0..n {
            by_dest.push(compute_latest_departure(n, flights_desc, dest, deadline));
        }
        table.push(by_dest);
    }
    table
}

fn precompute_durations(cities: &[City]) -> Vec<Vec<i32>> {
    let n = cities.len();
    let mut d = vec![vec![0; n]; n];
    for i in 0..n {
        for j in 0..n {
            if i == j {
                continue;
            }
            d[i][j] = required_duration(cities[i], cities[j]);
        }
    }
    d
}

fn top_k_cities_by_population(cities: &[City], k: usize) -> Vec<usize> {
    let mut ids: Vec<usize> = (0..cities.len()).collect();
    ids.sort_by_key(|&i| std::cmp::Reverse(cities[i].w));
    ids.truncate(k);
    ids
}

#[derive(Clone)]
struct BeamState {
    score_est: i128,
    route: Vec<Flight>,
    history_tail: Vec<(usize, i32, i32)>,
    used_signature: [u64; SIGNATURE_WORDS],
}

#[derive(Clone, Copy)]
struct BeamOpp {
    id: usize,
    min_dep: i32,
    deadline: i32,
    points: i128,
}

fn bit_test(bits: &[u64], idx: usize) -> bool {
    let x = idx as u64;
    let h = x.wrapping_mul(0x9E3779B185EBCA87u64) as usize & (SIGNATURE_BITS - 1);
    (bits[h >> 6] >> (h & 63)) & 1 == 1
}

fn bit_set(bits: &mut [u64], idx: usize) {
    let x = idx as u64;
    let h = x.wrapping_mul(0x9E3779B185EBCA87u64) as usize & (SIGNATURE_BITS - 1);
    bits[h >> 6] |= 1u64 << (h & 63);
}

fn insert_beam(bucket: &mut Vec<BeamState>, cand: BeamState) {
    bucket.push(cand);
    bucket.sort_by_key(|s| std::cmp::Reverse(s.score_est));
    if bucket.len() > BEAM_WIDTH {
        bucket.truncate(BEAM_WIDTH);
    }
}

fn build_opportunities_with_fixed(
    cities: &[City],
    far: &[Vec<bool>],
    latest_sq_table: &[Vec<Vec<i32>>],
    latest_fixed_table: &[Vec<Vec<i32>>],
    deadlines: &[i32],
) -> (Vec<Vec<Vec<BeamOpp>>>, usize) {
    let n = cities.len();
    let dlen = deadlines.len();
    let mut opp_by_uv = vec![vec![Vec::<BeamOpp>::new(); n]; n];
    let mut id_counter = 0usize;

    for u in 0..n {
        for v in 0..n {
            if !far[u][v] {
                continue;
            }
            let points = (cities[u].w as i128) * (cities[v].w as i128);
            for d_idx in 0..dlen {
                let sq = latest_sq_table[d_idx][v][u];
                let fixed = latest_fixed_table[d_idx][v][u];
                if fixed > sq {
                    continue;
                }
                let base = sq.max(fixed);
                let min_dep = if base < START_TIME {
                    START_TIME
                } else {
                    base + 5
                };
                if min_dep > deadlines[d_idx] {
                    continue;
                }
                opp_by_uv[u][v].push(BeamOpp {
                    id: id_counter,
                    min_dep,
                    deadline: deadlines[d_idx],
                    points,
                });
                id_counter += 1;
            }
        }
    }
    (opp_by_uv, id_counter)
}

fn beam_search_single_plane(
    start_city: usize,
    opp_by_uv: &[Vec<Vec<BeamOpp>>],
    durations: &[Vec<i32>],
) -> Vec<Flight> {
    let n = durations.len();
    let mut time_points = Vec::new();
    let mut t = START_TIME;
    while t < END_TIME {
        time_points.push(t);
        t += TIME_EQ_MIN;
    }
    if *time_points.last().unwrap() != END_TIME {
        time_points.push(END_TIME);
    }
    let tlen = time_points.len();

    let mut dp: Vec<Vec<Vec<BeamState>>> = vec![vec![Vec::new(); n]; tlen];
    dp[0][start_city].push(BeamState {
        score_est: 0,
        route: Vec::new(),
        history_tail: Vec::new(),
        used_signature: [0; SIGNATURE_WORDS],
    });

    for t_idx in 0..tlen {
        let cur_time = time_points[t_idx];
        for city in 0..n {
            let states = dp[t_idx][city].clone();
            for st in states {
                if t_idx + 1 < tlen {
                    insert_beam(&mut dp[t_idx + 1][city], st.clone());
                }

                for v in 0..n {
                    if v == city {
                        continue;
                    }
                    let duration = durations[city][v];
                    let arr = cur_time + duration;
                    if arr > END_TIME {
                        continue;
                    }
                    let arr_t_idx = time_points.partition_point(|&x| x < arr);
                    if arr_t_idx >= tlen {
                        continue;
                    }

                    let mut gain: i128 = 0;
                    for &opp in &opp_by_uv[city][v] {
                        if arr <= opp.deadline && cur_time >= opp.min_dep {
                            if !bit_test(&st.used_signature, opp.id) {
                                gain += opp.points;
                            }
                        }
                    }

                    let mut should_expand = true;
                    if BEAM_WIDTH > 0 && !dp[arr_t_idx][v].is_empty() {
                        let worst = dp[arr_t_idx][v].last().unwrap().score_est;
                        if dp[arr_t_idx][v].len() >= BEAM_WIDTH && st.score_est + gain <= worst {
                            should_expand = false;
                        }
                    }
                    if !should_expand {
                        continue;
                    }

                    let mut ns = st.clone();
                    ns.score_est += gain;
                    ns.route.push(Flight {
                        u: city,
                        v,
                        dep: cur_time,
                        arr,
                    });
                    ns.history_tail.push((v, arr, cur_time));
                    if ns.history_tail.len() > HISTORY_LEN {
                        let drop = ns.history_tail.len() - HISTORY_LEN;
                        ns.history_tail.drain(0..drop);
                    }
                    for &opp in &opp_by_uv[city][v] {
                        if arr <= opp.deadline && cur_time >= opp.min_dep {
                            bit_set(&mut ns.used_signature, opp.id);
                        }
                    }
                    insert_beam(&mut dp[arr_t_idx][v], ns);
                }
            }
        }
    }

    let mut best: Option<BeamState> = None;
    for layer in &dp {
        for bucket in layer {
            for st in bucket {
                if best
                    .as_ref()
                    .map(|b| st.score_est > b.score_est)
                    .unwrap_or(true)
                {
                    best = Some(st.clone());
                }
            }
        }
    }
    best.map(|b| b.route).unwrap_or_default()
}

fn optimize_planes_with_fixed_opportunities(
    cities: &[City],
    deadlines: &[i32],
    latest_sq_table: &[Vec<Vec<i32>>],
    far: &[Vec<bool>],
    durations: &[Vec<i32>],
    k: usize,
) -> Vec<Vec<Flight>> {
    let n = cities.len();
    let starts = top_k_cities_by_population(cities, k);
    let mut planes = vec![Vec::<Flight>::new(); k];

    for _round in 0..REFINE_ROUNDS {
        for pid in 0..k {
            let mut fixed = Vec::new();
            for (i, route) in planes.iter().enumerate() {
                if i == pid {
                    continue;
                }
                fixed.extend(route.iter().copied());
            }
            let fixed_desc = sort_by_dep_desc(fixed);
            let latest_fixed = precompute_latest_table(n, &fixed_desc, deadlines);
            let (opp_by_uv, opp_count) = build_opportunities_with_fixed(
                cities,
                far,
                latest_sq_table,
                &latest_fixed,
                deadlines,
            );
            let _ = opp_count;
            planes[pid] = beam_search_single_plane(starts[pid], &opp_by_uv, durations);
        }
    }

    planes
}

fn compute_score(cities: &[City], r: i32, square_desc: &[Flight], circle_desc: &[Flight]) -> i64 {
    let n = cities.len();
    let far = make_far_pair_table(cities, r);
    let deadlines = target_deadlines();
    let mut v_sq: i128 = 0;
    let mut v_ci: i128 = 0;

    for &deadline in &deadlines {
        for dest in 0..n {
            let latest_sq = compute_latest_departure(n, square_desc, dest, deadline);
            let latest_ci = compute_latest_departure(n, circle_desc, dest, deadline);
            for src in 0..n {
                if !far[src][dest] {
                    continue;
                }
                let points = (cities[src].w as i128) * (cities[dest].w as i128);
                if latest_sq[src] < latest_ci[src] {
                    v_ci += points;
                } else {
                    v_sq += points;
                }
            }
        }
    }
    let total = v_sq + v_ci;
    if total == 0 {
        0
    } else {
        (1_000_000i128 * v_ci / total) as i64
    }
}

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut it = input.split_whitespace();

    let n: usize = read_value(&mut it);
    let r: i32 = read_value(&mut it);
    let mut cities = Vec::with_capacity(n);
    for _ in 0..n {
        let x: i32 = read_value(&mut it);
        let y: i32 = read_value(&mut it);
        let w: i64 = read_value(&mut it);
        cities.push(City { x, y, w });
    }

    let m: usize = read_value(&mut it);
    let mut square = Vec::with_capacity(m);
    for _ in 0..m {
        let a: usize = read_value::<usize>(&mut it) - 1;
        let s_token: String = read_value(&mut it);
        let b: usize = read_value::<usize>(&mut it) - 1;
        let t_token: String = read_value(&mut it);
        square.push(Flight {
            u: a,
            v: b,
            dep: parse_time(&s_token),
            arr: parse_time(&t_token),
        });
    }
    let k: usize = read_value(&mut it);

    let square_desc = sort_by_dep_desc(square.clone());
    let far = make_far_pair_table(&cities, r);
    let durations = precompute_durations(&cities);
    let deadlines = target_deadlines();
    let latest_sq_table = precompute_latest_table(n, &square_desc, &deadlines);

    let planes = optimize_planes_with_fixed_opportunities(
        &cities,
        &deadlines,
        &latest_sq_table,
        &far,
        &durations,
        k,
    );

    for plane in &planes {
        for (idx, f) in plane.iter().enumerate() {
            let need = durations[f.u][f.v];
            assert_eq!(f.arr - f.dep, need);
            assert!((START_TIME..=END_TIME).contains(&f.dep));
            assert!((START_TIME..=END_TIME).contains(&f.arr));
            assert_eq!(f.dep % 5, 0);
            assert_eq!(f.arr % 5, 0);
            if idx > 0 {
                let prev = plane[idx - 1];
                assert_eq!(prev.v, f.u);
                assert!(prev.arr <= f.dep);
            }
        }
    }

    let opportunities = enumerate_opportunities(&cities, r, &square_desc);

    let circle: Vec<Flight> = planes.iter().flat_map(|v| v.iter().copied()).collect();
    let score = compute_score(&cities, r, &square_desc, &sort_by_dep_desc(circle.clone()));

    eprintln!("opportunities={}", opportunities.len());
    let opportunity_points: i128 = opportunities.iter().map(|o| o.points as i128).sum();
    eprintln!("opportunity_points={}", opportunity_points);
    let selected_count: usize = planes.iter().map(|v| v.len()).sum();
    eprintln!("selected_flights={}", selected_count);
    eprintln!("beam_width={}", BEAM_WIDTH);
    eprintln!("history_len={}", HISTORY_LEN);
    eprintln!("refine_rounds={}", REFINE_ROUNDS);
    eprintln!("time_eq_min={}", TIME_EQ_MIN);
    eprintln!("score={}", score);

    for plane in &planes {
        println!("{}", plane.len());
        for f in plane {
            println!(
                "{} {} {} {}",
                f.u + 1,
                format_time(f.dep),
                f.v + 1,
                format_time(f.arr)
            );
        }
    }
}