Submission #70299712

---

Source Code Expand

use std::cmp::{max, min};
use std::io::{self, Read};

fn any_weapon_available(available: &[bool], cur_c: &[i64]) -> bool {
    for w in 0..available.len() {
        if available[w] && cur_c[w] > 0 {
            return true;
        }
    }
    false
}

fn compute_reserved_targets(
    n: usize,
    opened: &[bool],
    rem_h: &[i64],
    available: &[bool],
    cur_c: &[i64],
    a: &Vec<Vec<i64>>,
    reserve_coef: f64,
) -> Vec<Option<usize>> {
    let mut reserved: Vec<Option<usize>> = vec![None; n];
    for w in 0..n {
        if !available[w] || cur_c[w] <= 0 {
            continue;
        }
        let mut best_j: Option<usize> = None;
        let mut best_val: i64 = -1;
        let mut second_val: i64 = -1;
        for j in 0..n {
            if !opened[j] && rem_h[j] > 0 {
                let v = a[w][j];
                if v > best_val {
                    second_val = best_val;
                    best_val = v;
                    best_j = Some(j);
                } else if v > second_val {
                    second_val = v;
                }
            }
        }
        if best_j.is_none() {
            continue;
        }
        if second_val < 0 {
            second_val = 0;
        }
        if (best_val as f64) >= reserve_coef * (second_val as f64) {
            reserved[w] = best_j;
        }
    }
    reserved
}

fn choose_weapon_for_target(
    n: usize,
    target: usize,
    rem_h: &[i64],
    available: &[bool],
    cur_c: &[i64],
    a: &Vec<Vec<i64>>,
    waste_coef: f64,
    reserved: &Vec<Option<usize>>,
    fist_threshold: i64,
) -> (Option<usize>, i64) {
    let mut best_w: Option<usize> = None;
    let mut best_score: f64 = -1e18;
    let mut best_d: i64 = 1;

    let rem = rem_h[target];

    // 残り硬さが閾値以下なら素手優先
    if rem <= fist_threshold {
        return (None, 1);
    }

    let fist_score = min(1, rem) as f64;
    best_score = fist_score;
    best_w = None;
    best_d = 1;

    for w in 0..n {
        if !available[w] || cur_c[w] <= 0 {
            continue;
        }
        if let Some(t) = reserved[w] {
            if t != target {
                continue;
            }
        }
        let d = a[w][target];
        let waste = max(0, d - rem) as f64;
        let effective = min(d, rem) as f64;
        let score = effective - waste_coef * waste;
        if score > best_score || ((score - best_score).abs() < 1e-12 && d > best_d) {
            best_score = score;
            best_w = Some(w);
            best_d = d;
        }
    }
    (best_w, best_d)
}

fn compute_weapon_value(
    n: usize,
    j: usize,
    opened: &[bool],
    rem_h: &[i64],
    c: &[i64],
    a: &Vec<Vec<i64>>,
) -> i64 {
    let mut vals: Vec<i64> = Vec::new();
    for k in 0..n {
        if !opened[k] && rem_h[k] > 0 && k != j {
            vals.push(a[j][k]);
        }
    }
    if vals.is_empty() {
        return 0;
    }
    vals.sort_by(|x, y| y.cmp(x)); // 降順
    let cap = min(c[j] as usize, vals.len());
    let mut s: i64 = 0;
    for i in 0..cap {
        s += vals[i];
    }
    s
}

// 追加: 箱 j の武器を仮に使ったときの「有効削減量」(無駄を除いた合計)
fn compute_effective_weapon_gain(
    n: usize,
    j: usize,
    opened: &[bool],
    rem_h: &[i64],
    c: &[i64],
    a: &Vec<Vec<i64>>,
) -> i64 {
    let mut vals: Vec<i64> = Vec::new();
    for k in 0..n {
        if !opened[k] && rem_h[k] > 0 && k != j {
            // 無駄を除くため、min(A[j][k], rem_h[k]) を評価値にする
            vals.push(min(a[j][k], rem_h[k]));
        }
    }
    if vals.is_empty() {
        return 0;
    }
    vals.sort_by(|x, y| y.cmp(x)); // 降順
    let cap = min(c[j] as usize, vals.len());
    let mut s: i64 = 0;
    for i in 0..cap {
        s += vals[i];
    }
    s
}

// 変更: A[i][j] >= 100 を候補に、重み（A）降順で辺を試し、サイクルになる辺は無視してDAGを構築（入次数つき）
fn build_pos_edge_graph(n: usize, a: &Vec<Vec<i64>>) -> (Vec<Vec<usize>>, Vec<i32>) {
    let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
    let mut indeg: Vec<i32> = vec![0; n];

    // 候補辺を収集（A[i][j] >= 100）して重み降順にソート
    let mut edges: Vec<(i64, usize, usize)> = Vec::new();
    for i in 0..n {
        for j in 0..n {
            if i == j {
                continue;
            }
            if a[i][j] >= 50 {
                edges.push((a[i][j], i, j));
            }
        }
    }
    edges.sort_by(|x, y| y.0.cmp(&x.0)); // 重い順

    // サイクルが生じるなら無視して張る
    for &(_, i, j) in &edges {
        // 既存グラフで j から i へ到達できるなら、i->j を張るとサイクルになる
        let mut stack = vec![j];
        let mut vis = vec![false; n];
        vis[j] = true;
        let mut makes_cycle = false;
        while let Some(u) = stack.pop() {
            if u == i {
                makes_cycle = true;
                break;
            }
            for &v in &adj[u] {
                if !vis[v] {
                    vis[v] = true;
                    stack.push(v);
                }
            }
        }
        if makes_cycle {
            continue; // サイクルになるので無視
        }
        adj[i].push(j);
        indeg[j] += 1;
    }
    (adj, indeg)
}

fn run_simulation(
    n: usize,
    h: &Vec<i64>,
    c: &Vec<i64>,
    a: &Vec<Vec<i64>>,
    waste_coef: f64,
    weapon_value_scale: f64,
    reserve_coef: f64,
    no_weapon_strategy: i32, // 0: 既存(最小remH), 1: 有効削減量最大
    fist_threshold: i64,     // これ以下の硬さは素手で壊す
    topo_priority: bool,     // 追加: トポロジカル順優先で箱を開くか
) -> Vec<(i32, i32)> {
    let mut rem_h = h.clone();                 // 残り硬さ
    let mut opened = vec![false; n];           // 箱が開いているか
    let mut available = vec![false; n];        // 武器が使用可能か（箱を開けたら True）
    let mut cur_c = vec![0_i64; n];            // 各武器の現在の耐久（使用可能なら C[i]）

    let mut attacks: Vec<(i32, i32)> = Vec::new(); // (w, b) w == -1 なら素手
    let mut unopened_count = n as i64;

    // トポロジカル順用のグラフ構築（A[i][j] >= 100 のみ、サイクル回避）
    let (adj_topo, mut cur_indeg) = if topo_priority {
        build_pos_edge_graph(n, a)
    } else {
        (vec![Vec::new(); n], vec![0i32; n])
    };

    // main simulation loop
    while unopened_count > 0 {
        // focus 箱を選ぶ
        let mut focus: Option<usize> = None;

        // 低硬さの箱があれば最優先で素手で壊す
        {
            let mut best_rem: Option<i64> = None;
            let mut idx: Option<usize> = None;
            for j in 0..n {
                if !opened[j] && rem_h[j] > 0 && rem_h[j] <= fist_threshold {
                    if best_rem.is_none() || rem_h[j] < best_rem.unwrap() {
                        best_rem = Some(rem_h[j]);
                        idx = Some(j);
                    }
                }
            }
            if idx.is_some() {
                focus = idx;
            }
        }

        // トポロジカル順優先: 現在の入次数が0の箱のうち、有効な武器（未開封へ向く辺）がある箱を優先
        if topo_priority && focus.is_none() {
            let mut best_rem: Option<i64> = None;
            let mut idx: Option<usize> = None;
            for j in 0..n {
                if opened[j] || rem_h[j] <= 0 {
                    continue;
                }
                if cur_indeg[j] == 0 {
                    // 未開封に向かう辺があるか
                    let has_useful = adj_topo[j].iter().any(|&v| !opened[v] && rem_h[v] > 0);
                    if has_useful {
                        if best_rem.is_none() || rem_h[j] < best_rem.unwrap() {
                            best_rem = Some(rem_h[j]);
                            idx = Some(j);
                        }
                    }
                }
            }
            if idx.is_some() {
                focus = idx;
            }
        }

        // フォールバック: 入次数0の中で従来通り（最小rem）
        if topo_priority && focus.is_none() {
            let mut best_rem: Option<i64> = None;
            let mut idx: Option<usize> = None;
            for j in 0..n {
                if opened[j] || rem_h[j] <= 0 {
                    continue;
                }
                if cur_indeg[j] == 0 {
                    if best_rem.is_none() || rem_h[j] < best_rem.unwrap() {
                        best_rem = Some(rem_h[j]);
                        idx = Some(j);
                    }
                }
            }
            if idx.is_some() {
                focus = idx;
            }
        }

        if focus.is_none() {
            if !any_weapon_available(&available, &cur_c) {
                if no_weapon_strategy == 0 {
                    // 最小 remH の箱
                    let mut min_h: i64 = 1_000_000_000;
                    let mut idx: Option<usize> = None;
                    for i in 0..n {
                        if !opened[i] && rem_h[i] > 0 && rem_h[i] < min_h {
                            min_h = rem_h[i];
                            idx = Some(i);
                        }
                    }
                    focus = idx;
                } else {
                    // 追加戦略: 仮にその箱の武器を使用したときの有効削減量が最大の箱を選ぶ
                    let mut best_gain: i64 = -1;
                    let mut best_idx: Option<usize> = None;
                    let mut tie_min_rem: Option<i64> = None;
                    for j in 0..n {
                        if opened[j] || rem_h[j] <= 0 {
                            continue;
                        }
                        let gain = compute_effective_weapon_gain(n, j, &opened, &rem_h, &c, &a);
                        let better = gain > best_gain
                            || (gain == best_gain
                                && (tie_min_rem.is_none() || rem_h[j] < tie_min_rem.unwrap()));
                        if better {
                            best_gain = gain;
                            best_idx = Some(j);
                            tie_min_rem = Some(rem_h[j]);
                        }
                    }
                    focus = best_idx;
                }
            } else {
                // コスト最小の箱
                let mut best_cost: f64 = f64::INFINITY;
                let mut best_tie_rem: Option<i64> = None;
                for j in 0..n {
                    if opened[j] || rem_h[j] <= 0 {
                        continue;
                    }
                    let mut maxd: i64 = 0;
                    for w in 0..n {
                        if available[w] && cur_c[w] > 0 {
                            if a[w][j] > maxd {
                                maxd = a[w][j];
                            }
                        }
                    }
                    let base_cost = if maxd <= 0 {
                        rem_h[j] as f64
                    } else {
                        (rem_h[j] as f64) / (maxd as f64)
                    };

                    let weapon_value = compute_weapon_value(n, j, &opened, &rem_h, &c, &a) as f64;
                    let divisor = 1.0 + (weapon_value / weapon_value_scale);
                    let cost = base_cost / divisor;

                    let tie_better = match best_tie_rem {
                        None => true,
                        Some(r) => rem_h[j] < r,
                    };

                    if cost < best_cost - 1e-12 || ((cost - best_cost).abs() < 1e-12 && tie_better) {
                        best_cost = cost;
                        focus = Some(j);
                        best_tie_rem = Some(rem_h[j]);
                    }
                }
            }
        }

        let Some(f) = focus else { break };

        // focus が開くまで攻撃
        while rem_h[f] > 0 {
            let reserved = compute_reserved_targets(n, &opened, &rem_h, &available, &cur_c, &a, reserve_coef);
            let (best_w_opt, best_d) = choose_weapon_for_target(
                n, f, &rem_h, &available, &cur_c, &a, waste_coef, &reserved, fist_threshold,
            );

            if best_w_opt.is_none() {
                // 素手
                attacks.push((-1, f as i32));
                rem_h[f] -= 1;
                if rem_h[f] <= 0 && !opened[f] {
                    opened[f] = true;
                    unopened_count -= 1;
                    // unlock_weapon(f)
                    if !available[f] {
                        available[f] = true;
                        cur_c[f] = c[f];
                    }
                    // トポロジカル入次数更新
                    for &v in &adj_topo[f] {
                        cur_indeg[v] -= 1;
                    }
                    break;
                }
            } else {
                let widx = best_w_opt.unwrap();
                attacks.push((widx as i32, f as i32));
                rem_h[f] -= best_d;
                cur_c[widx] -= 1;
                if rem_h[f] <= 0 && !opened[f] {
                    opened[f] = true;
                    unopened_count -= 1;
                    // unlock_weapon(f)
                    if !available[f] {
                        available[f] = true;
                        cur_c[f] = c[f];
                    }
                    // トポロジカル入次数更新
                    for &v in &adj_topo[f] {
                        cur_indeg[v] -= 1;
                    }
                    break;
                }
                // まだ続く
            }
        }

        // 開いた後、使える武器を使い切るフェーズ
        loop {
            // 低硬さの箱が残っているなら拳優先のため中断
            let mut has_low = false;
            for j in 0..n {
                if !opened[j] && rem_h[j] > 0 && rem_h[j] <= fist_threshold {
                    has_low = true;
                    break;
                }
            }
            if has_low {
                break;
            }

            let reserved = compute_reserved_targets(n, &opened, &rem_h, &available, &cur_c, &a, reserve_coef);

            let mut best_pair: Option<(usize, usize)> = None;
            let mut best_pair_score: f64 = -1e-18;
            let mut best_pair_damage: i64 = 0;

            for w in 0..n {
                if !available[w] || cur_c[w] <= 0 {
                    continue;
                }
                let mut targets: Vec<usize> = Vec::new();
                if let Some(j) = reserved[w] {
                    if !opened[j] && rem_h[j] > fist_threshold {
                        targets.push(j);
                    }
                } else {
                    for j in 0..n {
                        if !opened[j] && rem_h[j] > fist_threshold {
                            targets.push(j);
                        }
                    }
                }
                if targets.is_empty() {
                    continue;
                }

                // この武器でのベストターゲット
                let mut best_j_for_w: Option<usize> = None;
                let mut best_score_for_w: f64 = -1e18;
                let mut best_d_for_w: i64 = 0;

                for &j in &targets {
                    let d = a[w][j];
                    let rem = rem_h[j];
                    let waste = max(0, d - rem) as f64;
                    let effective = min(d, rem) as f64;
                    let score = effective - waste_coef * waste;
                    if score > best_score_for_w
                        || ((score - best_score_for_w).abs() < 1e-12 && d > best_d_for_w)
                    {
                        best_score_for_w = score;
                        best_j_for_w = Some(j);
                        best_d_for_w = d;
                    }
                }
                if let Some(bj) = best_j_for_w {
                    if best_score_for_w > best_pair_score
                        || ((best_score_for_w - best_pair_score).abs() < 1e-12
                            && best_d_for_w > best_pair_damage)
                    {
                        best_pair_score = best_score_for_w;
                        best_pair = Some((w, bj));
                        best_pair_damage = best_d_for_w;
                    }
                }
            }

            let Some((w, j)) = best_pair else { break };

            attacks.push((w as i32, j as i32));
            rem_h[j] -= a[w][j];
            cur_c[w] -= 1;
            if rem_h[j] <= 0 && !opened[j] {
                opened[j] = true;
                unopened_count -= 1;
                // unlock_weapon(j)
                if !available[j] {
                    available[j] = true;
                    cur_c[j] = c[j];
                }
                // トポロジカル入次数更新
                for &v in &adj_topo[j] {
                    cur_indeg[v] -= 1;
                }
            }
        }
    }

    attacks
}

fn main() {
    // 入力読み取り
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut it = input.split_whitespace();

    let n: usize = match it.next() {
        Some(x) => x.parse().unwrap(),
        None => return,
    };

    let mut h = vec![0_i64; n];
    for i in 0..n {
        h[i] = it.next().unwrap().parse::<i64>().unwrap();
    }

    let mut c = vec![0_i64; n];
    for i in 0..n {
        c[i] = it.next().unwrap().parse::<i64>().unwrap();
    }

    let mut a = vec![vec![0_i64; n]; n];
    for i in 0..n {
        for j in 0..n {
            a[i][j] = it.next().unwrap().parse::<i64>().unwrap();
        }
    }

    // パラメータの候補
    let waste_coef_list: [f64; 1] = [0.0];
    let weapon_value_scale_list: [f64; 3] = [0.01, 200.0, 1000.0];
    let reserve_coef_list: [f64; 3] = [1.0, 2.0, 10.0];
    let no_weapon_strategy_list: [i32; 2] = [0, 1];
    let topo_flag_list: [bool; 2] = [false, true]; // 追加: トポロジカル順を試すか

    // 素手で壊す硬さの閾値
    let fist_threshold_list: [i64; 4] = [1, 10, 20, 30];

    let mut best_attacks: Option<Vec<(i32, i32)>> = None;
    let mut best_len: Option<usize> = None;

    for &wc in &waste_coef_list {
        for &vs in &weapon_value_scale_list {
            for &rc in &reserve_coef_list {
                for &ns in &no_weapon_strategy_list {
                    for &topo in &topo_flag_list {
                        for &fist_threshold in &fist_threshold_list {
                            let attacks = run_simulation(
                                n, &h, &c, &a, wc, vs, rc, ns, fist_threshold, topo,
                            );
                            let tlen = attacks.len();
                            if best_attacks.is_none() || tlen < best_len.unwrap() {
                                best_len = Some(tlen);
                                best_attacks = Some(attacks);
                            }
                        }
                    }
                }
            }
        }
    }

    let best = best_attacks.unwrap();
    let mut out = String::new();
    for (w, b) in best {
        out.push_str(&format!("{} {}\n", w, b));
    }
    print!("{}", out);
}

Submission Info

Compile Error

warning: value assigned to `best_w` is never read
  --> src/main.rs:66:13
   |
66 |     let mut best_w: Option<usize> = None;
   |             ^^^^^^
   |
   = help: maybe it is overwritten before being read?
   = note: `#[warn(unused_assignments)]` on by default

warning: value assigned to `best_score` is never read
  --> src/main.rs:67:13
   |
67 |     let mut best_score: f64 = -1e18;
   |             ^^^^^^^^^^
   |
   = help: maybe it is overwritten before being read?

warning: value assigned to `best_d` is never read
  --> src/main.rs:68:13
   |
68 |     let mut best_d: i64 = 1;
   |             ^^^^^^
   |
   = help: maybe it is overwritten before being read?

Judge Result