#1169516 (Rust) No.5016 Worst Mayor

• 問題: No.5016 Worst Mayor
• ユーザー: assy1028
• 提出日時: 2026-06-21 11:09:17
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 1,626 ms / 2,000 ms
• コード長: 13,928 bytes
• コンパイル時間: 2,600 ms
• コンパイル使用メモリ: 208,748 KB
• 実行使用メモリ: 39,920 KB
• スコア: 22,305,470,848
• 平均クエリ数: 400.00
• 最終ジャッジ日時: 2026-06-21 11:10:51
• 合計ジャッジ時間: 88,059 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_1

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

ソースコード

use std::io::{self, BufRead, BufWriter, Write};
use std::time::{Duration, Instant};

const H: usize = 14;
const W: usize = 14;
const V: usize = H * W;
const TURNS: usize = 400;
const NORMAL_COST: i32 = 1000;
const HIGHWAY_COST: i32 = 223;
const INITIAL_MONEY: i64 = 1_000_000;
const FUND_GAIN: i64 = 50_000;
const MAX_PLAN_EDGES: usize = 150;
const BEAM_WIDTH: usize = 4;
const BEAM_BRANCH: usize = 5;
const SEARCH_TIME_LIMIT_MS: u64 = 1_250;
const COMPUTE_TIME_LIMIT_MS: u64 = 1_650;
const PLAN_START_MARGIN_MS: u64 = 80;
const INF_NEG: i64 = i64::MIN / 4;

#[derive(Clone, Copy)]
struct Edge {
    u: usize,
    v: usize,
}

#[derive(Clone, Copy)]
struct Demand {
    from: usize,
    to: usize,
    count: i64,
}

#[derive(Clone)]
enum Action {
    Build(Edge),
    Collaborate,
    Fund,
}

#[derive(Clone)]
struct SearchState {
    dist: Vec<i32>,
    highway_cnt: Vec<i16>,
    used: Vec<u64>,
    order: Vec<Edge>,
    revenues: Vec<i64>,
}

fn cell(r: usize, c: usize) -> usize {
    r * W + c
}

fn build_edges() -> Vec<Edge> {
    let mut edges = Vec::new();
    for r in 0..H {
        for c in 0..W {
            let u = cell(r, c);
            if r + 1 < H {
                edges.push(Edge {
                    u,
                    v: cell(r + 1, c),
                });
            }
            if c + 1 < W {
                edges.push(Edge {
                    u,
                    v: cell(r, c + 1),
                });
            }
        }
    }
    edges
}

fn idx(a: usize, b: usize) -> usize {
    a * V + b
}

fn build_cost(collaborators: usize) -> i64 {
    let limit: i128 = 100_000_000_000_000;
    let mut cost = (10_000_000.0 / (collaborators as f64).sqrt()) as i64;
    while ((cost + 1) as i128) * ((cost + 1) as i128) * collaborators as i128 <= limit {
        cost += 1;
    }
    while (cost as i128) * (cost as i128) * collaborators as i128 > limit {
        cost -= 1;
    }
    cost
}

fn initial_shortest() -> (Vec<i32>, Vec<i16>) {
    let mut dist = vec![0; V * V];
    let cnt = vec![0; V * V];
    for a in 0..V {
        let ar = a / W;
        let ac = a % W;
        for b in 0..V {
            let br = b / W;
            let bc = b % W;
            dist[idx(a, b)] = ((ar.abs_diff(br) + ac.abs_diff(bc)) as i32) * NORMAL_COST;
        }
    }
    (dist, cnt)
}

fn marginal_revenue(edge: Edge, dist: &[i32], highway_cnt: &[i16], demands: &[Demand]) -> i64 {
    let mut delta_count = 0_i64;
    let u = edge.u;
    let v = edge.v;
    for demand in demands {
        let a = demand.from;
        let b = demand.to;
        let old_dist = dist[idx(a, b)];
        let old_cnt = highway_cnt[idx(a, b)];
        let mut best_dist = old_dist;
        let mut best_cnt = old_cnt;

        let d1 = dist[idx(a, u)] + HIGHWAY_COST + dist[idx(v, b)];
        let c1 = highway_cnt[idx(a, u)] + 1 + highway_cnt[idx(v, b)];
        if d1 < best_dist || (d1 == best_dist && c1 > best_cnt) {
            best_dist = d1;
            best_cnt = c1;
        }

        let d2 = dist[idx(a, v)] + HIGHWAY_COST + dist[idx(u, b)];
        let c2 = highway_cnt[idx(a, v)] + 1 + highway_cnt[idx(u, b)];
        if d2 < best_dist || (d2 == best_dist && c2 > best_cnt) {
            best_cnt = c2;
        }

        delta_count += demand.count * (best_cnt as i64 - old_cnt as i64);
    }
    60 * delta_count
}

fn add_edge(edge: Edge, dist: &mut [i32], highway_cnt: &mut [i16]) {
    let old_dist = dist.to_vec();
    let old_cnt = highway_cnt.to_vec();
    let u = edge.u;
    let v = edge.v;

    for a in 0..V {
        let au = idx(a, u);
        let av = idx(a, v);
        for b in 0..V {
            let ab = idx(a, b);
            let mut best_dist = old_dist[ab];
            let mut best_cnt = old_cnt[ab];

            let d1 = old_dist[au] + HIGHWAY_COST + old_dist[idx(v, b)];
            let c1 = old_cnt[au] + 1 + old_cnt[idx(v, b)];
            if d1 < best_dist || (d1 == best_dist && c1 > best_cnt) {
                best_dist = d1;
                best_cnt = c1;
            }

            let d2 = old_dist[av] + HIGHWAY_COST + old_dist[idx(u, b)];
            let c2 = old_cnt[av] + 1 + old_cnt[idx(u, b)];
            if d2 < best_dist || (d2 == best_dist && c2 > best_cnt) {
                best_dist = d2;
                best_cnt = c2;
            }

            dist[ab] = best_dist;
            highway_cnt[ab] = best_cnt;
        }
    }
}

fn is_used(bits: &[u64], edge_index: usize) -> bool {
    ((bits[edge_index >> 6] >> (edge_index & 63)) & 1) != 0
}

fn set_used(bits: &mut [u64], edge_index: usize) {
    bits[edge_index >> 6] |= 1_u64 << (edge_index & 63);
}

fn push_current_plans(plans: &mut Vec<(Vec<Edge>, Vec<i64>)>, beam: &[SearchState]) {
    for state in beam {
        plans.push((state.order.clone(), state.revenues.clone()));
    }
}

fn beam_edge_orders(
    edges: &[Edge],
    demands: &[Demand],
    deadline: Instant,
) -> Vec<(Vec<Edge>, Vec<i64>)> {
    let (dist, highway_cnt) = initial_shortest();
    let words = (edges.len() + 63) / 64;
    let mut beam = vec![SearchState {
        dist,
        highway_cnt,
        used: vec![0; words],
        order: Vec::new(),
        revenues: vec![0],
    }];
    let mut plans = Vec::new();

    for step in 0..MAX_PLAN_EDGES.min(edges.len()) {
        if Instant::now() >= deadline {
            break;
        }

        let mut children = Vec::new();

        for state in &beam {
            if Instant::now() >= deadline {
                break;
            }
            let mut candidates = Vec::new();
            for (i, &edge) in edges.iter().enumerate() {
                if is_used(&state.used, i) {
                    continue;
                }
                let gain = marginal_revenue(edge, &state.dist, &state.highway_cnt, demands);
                if gain > 0 {
                    candidates.push((gain, i));
                }
            }
            candidates.sort_unstable_by(|a, b| b.0.cmp(&a.0));
            candidates.truncate(BEAM_BRANCH);

            for (gain, edge_index) in candidates {
                let edge = edges[edge_index];
                let mut next = state.clone();
                set_used(&mut next.used, edge_index);
                next.order.push(edge);
                next.revenues.push(*state.revenues.last().unwrap() + gain);
                add_edge(edge, &mut next.dist, &mut next.highway_cnt);
                children.push(next);
            }
        }

        if children.is_empty() {
            break;
        }

        children
            .sort_unstable_by(|a, b| b.revenues.last().unwrap().cmp(a.revenues.last().unwrap()));
        let mut next_beam: Vec<SearchState> = Vec::new();
        'child: for child in children {
            for existing in &next_beam {
                if existing.used == child.used {
                    continue 'child;
                }
            }
            next_beam.push(child);
            if next_beam.len() == BEAM_WIDTH {
                break;
            }
        }
        beam = next_beam;

        if (step + 1) % 5 == 0 {
            push_current_plans(&mut plans, &beam);
        }
    }

    push_current_plans(&mut plans, &beam);
    plans
}

fn plan_actions(order: &[Edge], revenues: &[i64]) -> (i64, Vec<Action>) {
    let max_built = order.len();
    let cols = max_built + 1;
    let state_count = (TURNS + 2) * cols;
    let state_idx = |collaborators: usize, built: usize| collaborators * cols + built;

    let mut costs = vec![0_i64; TURNS + 2];
    for (v, cost) in costs.iter_mut().enumerate().take(TURNS + 2).skip(1) {
        *cost = build_cost(v);
    }

    let mut current = vec![INF_NEG; state_count];
    current[state_idx(1, 0)] = INITIAL_MONEY;
    let mut parent = vec![0_u8; (TURNS + 1) * state_count];

    for turn in 0..TURNS {
        let mut next = vec![INF_NEG; state_count];
        for collaborators in 1..=turn + 1 {
            for built in 0..=max_built {
                let money = current[state_idx(collaborators, built)];
                if money == INF_NEG {
                    continue;
                }

                let revenue = revenues[built];

                let ni = state_idx(collaborators + 1, built);
                let nv = money + revenue;
                if nv > next[ni] {
                    next[ni] = nv;
                    parent[(turn + 1) * state_count + ni] = 2;
                }

                let ni = state_idx(collaborators, built);
                let nv = money + FUND_GAIN + revenue;
                if nv > next[ni] {
                    next[ni] = nv;
                    parent[(turn + 1) * state_count + ni] = 3;
                }

                if built < max_built && money >= costs[collaborators] {
                    let ni = state_idx(collaborators, built + 1);
                    let nv = money - costs[collaborators] + revenues[built + 1];
                    if nv > next[ni] {
                        next[ni] = nv;
                        parent[(turn + 1) * state_count + ni] = 1;
                    }
                }
            }
        }
        current = next;
    }

    let mut best_money = INF_NEG;
    let mut best_collaborators = 1;
    let mut best_built = 0;
    for collaborators in 1..=TURNS + 1 {
        for built in 0..=max_built {
            let money = current[state_idx(collaborators, built)];
            if money > best_money {
                best_money = money;
                best_collaborators = collaborators;
                best_built = built;
            }
        }
    }

    let mut actions = Vec::with_capacity(TURNS);
    let mut collaborators = best_collaborators;
    let mut built = best_built;
    for turn in (1..=TURNS).rev() {
        let action = parent[turn * state_count + state_idx(collaborators, built)];
        match action {
            1 => {
                actions.push(Action::Build(order[built - 1]));
                built -= 1;
            }
            2 => {
                actions.push(Action::Collaborate);
                collaborators -= 1;
            }
            3 => actions.push(Action::Fund),
            _ => actions.push(Action::Fund),
        }
    }
    actions.reverse();
    (best_money, actions)
}

fn output_action<Writer: Write>(out: &mut Writer, action: &Action) -> io::Result<()> {
    match action {
        Action::Build(edge) => {
            let x = edge.u / W + 1;
            let y = edge.u % W + 1;
            let z = edge.v / W + 1;
            let w = edge.v % W + 1;
            writeln!(out, "1 {} {} {} {}", x, y, z, w)
        }
        Action::Collaborate => writeln!(out, "2"),
        Action::Fund => writeln!(out, "3"),
    }
}

fn read_nonempty_line<R: BufRead>(reader: &mut R, line: &mut String) -> io::Result<bool> {
    loop {
        line.clear();
        let len = reader.read_line(line)?;
        if len == 0 {
            return Ok(false);
        }
        if !line.trim().is_empty() {
            return Ok(true);
        }
    }
}

fn main() -> io::Result<()> {
    let start_time = Instant::now();
    let search_deadline = start_time + Duration::from_millis(SEARCH_TIME_LIMIT_MS);
    let compute_deadline = start_time + Duration::from_millis(COMPUTE_TIME_LIMIT_MS);
    let plan_start_deadline =
        compute_deadline - Duration::from_millis(PLAN_START_MARGIN_MS.min(COMPUTE_TIME_LIMIT_MS));

    let stdin = io::stdin();
    let mut reader = io::BufReader::new(stdin.lock());

    let mut line = String::new();
    if !read_nonempty_line(&mut reader, &mut line)? {
        return Ok(());
    }
    let first = line
        .split_whitespace()
        .map(|x| x.parse::<usize>().unwrap())
        .collect::<Vec<_>>();
    let n = first[0];
    let turns = first[1];

    let mut demand_count = vec![0_i64; V * V];
    for _ in 0..n {
        read_nonempty_line(&mut reader, &mut line)?;
        let a = line
            .split_whitespace()
            .map(|x| x.parse::<usize>().unwrap())
            .collect::<Vec<_>>();
        let from = cell(a[0] - 1, a[1] - 1);
        let to = cell(a[2] - 1, a[3] - 1);
        demand_count[idx(from, to)] += 1;
    }

    let mut demands = Vec::new();
    for from in 0..V {
        for to in 0..V {
            let count = demand_count[idx(from, to)];
            if count > 0 {
                demands.push(Demand { from, to, count });
            }
        }
    }

    let edges = build_edges();
    let mut candidate_orders = beam_edge_orders(&edges, &demands, search_deadline);
    candidate_orders.sort_unstable_by(|a, b| b.1.last().unwrap().cmp(a.1.last().unwrap()));
    let mut best_score = INF_NEG;
    let mut actions = Vec::new();
    for (order, revenues) in &candidate_orders {
        if !actions.is_empty() && Instant::now() >= plan_start_deadline {
            break;
        }
        let (score, plan) = plan_actions(order, revenues);
        if score > best_score {
            best_score = score;
            actions = plan;
        }
    }
    if actions.is_empty() {
        actions = vec![Action::Fund; turns];
    }
    actions.truncate(turns);
    while actions.len() < turns {
        actions.push(Action::Fund);
    }

    let stdout = io::stdout();
    let mut out = BufWriter::new(stdout.lock());
    let mut has_turn_input = true;
    for action in actions.iter().take(turns) {
        if has_turn_input {
            line.clear();
            let len = reader.read_line(&mut line)?;
            if len == 0 {
                has_turn_input = false;
            } else {
                let values = line
                    .split_whitespace()
                    .map(|x| x.parse::<i64>().unwrap())
                    .collect::<Vec<_>>();
                if values.len() >= 2 && values[0] == -1 && values[1] == -1 {
                    break;
                }
            }
        }
        output_action(&mut out, action)?;
        out.flush()?;
    }

    Ok(())
}