Submission #71726869

---

Source Code Expand

/*
[Dependencies]
proconio = "0.4.5"
*/

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

// =====================
// Hyperparameters
// =====================
const TIME_LIMIT_SEC: f64 = 1.95;

// Beam
const BEAM_WIDTH: usize = 15;
const HORIZON: usize = 10;
const BRANCH: usize = 40;

// SA
const SA_T0: f64 = 1e-1;
const SA_T1: f64 = 1e-5;
const SA_SAFE_MARGIN: f64 = 0.02;
const SA_FORCE_ACCEPT_EPS: f64 = 1e-12;

// 近傍操作の選択確率（合計 1.0 を想定）
const P_MOVE_POINT: f64 = 0.55; // 1点変更
const P_MOVE_SWAP: f64 = 0.25; // swap
const P_MOVE_REWRITE: f64 = 0.20; // 区間リライト
const REWRITE_MAX_LEN: usize = 16;

const RNG_SEED: u64 = 123456789;

// --- logging ---
const LOG: bool = false;

// =====================
// Problem fixed constants
// =====================
const N: usize = 10;
const L: usize = 4;

// ========== RNG ==========
#[derive(Clone)]
struct XorShift64 {
    s: u64,
}
impl XorShift64 {
    fn new(seed: u64) -> Self {
        let s = if seed == 0 { 88172645463325252 } else { seed };
        Self { s }
    }
    #[inline(always)]
    fn next_u64(&mut self) -> u64 {
        let mut x = self.s;
        x ^= x << 7;
        x ^= x >> 9;
        x ^= x << 8;
        self.s = x;
        x
    }
    #[inline(always)]
    fn next_f64(&mut self) -> f64 {
        const DEN: f64 = (u64::MAX as f64) + 1.0;
        (self.next_u64() as f64) / DEN
    }
    #[inline(always)]
    fn gen_usize(&mut self, upper: usize) -> usize {
        (self.next_u64() % (upper as u64)) as usize
    }
}

// ========== Data Structures ==========
#[derive(Clone)]
struct ProblemInput {
    t: usize,
    k0: u128,
    a: [u128; N],
    c: [[u128; N]; L],
    cost_scale: [f64; N],
}

#[derive(Clone)]
struct State {
    apples: u128,
    b: [[u128; N]; L],
    p: [[u32; N]; L],
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Action {
    Upgrade { level: usize, id: usize },
    Wait,
}
impl Action {
    fn format(&self) -> String {
        match *self {
            Action::Upgrade { level, id } => format!("{level} {id}"),
            Action::Wait => "-1".to_string(),
        }
    }
}

#[derive(Clone)]
struct Node {
    st: State,
    first: Action,
    score: f64,
    is_wait_line: bool,
}

// ========== Optimization Helpers ==========
#[derive(Clone, Copy)]
struct Coeffs {
    c1: u128,
    c2: u128,
    c3: u128,
    c4: u128,
}

#[inline(always)]
fn calc_coeffs(rem: usize) -> Coeffs {
    let r = rem as u128;
    if r == 0 {
        return Coeffs {
            c1: 0,
            c2: 0,
            c3: 0,
            c4: 0,
        };
    }
    let c1 = r;
    let c2 = r.saturating_mul(r.saturating_sub(1)) / 2;
    let c3 = r
        .saturating_mul(r.saturating_sub(1))
        .saturating_mul(r.saturating_sub(2))
        / 6;
    let c4 = r
        .saturating_mul(r.saturating_sub(1))
        .saturating_mul(r.saturating_sub(2))
        .saturating_mul(r.saturating_sub(3))
        / 24;
    Coeffs { c1, c2, c3, c4 }
}

#[inline(always)]
fn prereq_ok(st: &State, level: usize, j: usize) -> bool {
    unsafe {
        match level {
            0 => true,
            1 => *st.p.get_unchecked(0).get_unchecked(j) > 0,
            2 => {
                *st.p.get_unchecked(0).get_unchecked(j) > 0
                    && *st.p.get_unchecked(1).get_unchecked(j) > 0
            }
            3 => {
                *st.p.get_unchecked(0).get_unchecked(j) > 0
                    && *st.p.get_unchecked(1).get_unchecked(j) > 0
                    && *st.p.get_unchecked(2).get_unchecked(j) > 0
            }
            _ => false,
        }
    }
}

#[inline(always)]
fn upgrade_cost(inp: &ProblemInput, st: &State, level: usize, j: usize) -> u128 {
    unsafe {
        inp.c
            .get_unchecked(level)
            .get_unchecked(j)
            .saturating_mul((*st.p.get_unchecked(level).get_unchecked(j) as u128).saturating_add(1))
    }
}

#[inline(always)]
fn estimate_end_apples_fast(inp: &ProblemInput, st: &State, coeffs: &Coeffs) -> u128 {
    let mut ans = st.apples;
    unsafe {
        for j in 0..N {
            let a = *inp.a.get_unchecked(j);
            let p0 = *st.p.get_unchecked(0).get_unchecked(j) as u128;
            if p0 == 0 {
                continue;
            }
            let b0 = *st.b.get_unchecked(0).get_unchecked(j);

            ans = ans.saturating_add(
                a.saturating_mul(b0)
                    .saturating_mul(p0)
                    .saturating_mul(coeffs.c1),
            );

            let p1 = *st.p.get_unchecked(1).get_unchecked(j) as u128;
            if p1 == 0 {
                continue;
            }
            ans = ans.saturating_add(
                a.saturating_mul(*st.b.get_unchecked(1).get_unchecked(j))
                    .saturating_mul(p0)
                    .saturating_mul(p1)
                    .saturating_mul(coeffs.c2),
            );

            let p2 = *st.p.get_unchecked(2).get_unchecked(j) as u128;
            if p2 == 0 {
                continue;
            }
            ans = ans.saturating_add(
                a.saturating_mul(*st.b.get_unchecked(2).get_unchecked(j))
                    .saturating_mul(p0)
                    .saturating_mul(p1)
                    .saturating_mul(p2)
                    .saturating_mul(coeffs.c3),
            );

            let p3 = *st.p.get_unchecked(3).get_unchecked(j) as u128;
            if p3 == 0 {
                continue;
            }
            ans = ans.saturating_add(
                a.saturating_mul(*st.b.get_unchecked(3).get_unchecked(j))
                    .saturating_mul(p0)
                    .saturating_mul(p1)
                    .saturating_mul(p2)
                    .saturating_mul(p3)
                    .saturating_mul(coeffs.c4),
            );
        }
    }
    ans
}

fn score_state_fast(inp: &ProblemInput, st: &State, rem: usize, coeffs: &Coeffs) -> f64 {
    let r_f64 = rem.max(1) as f64;
    let end = estimate_end_apples_fast(inp, st, coeffs);
    let growth = end.saturating_sub(st.apples);
    let avg = (growth as f64) / r_f64;
    (avg + 1.0).ln()
}

#[inline(always)]
fn step_unchecked(inp: &ProblemInput, st: &mut State, act: Action) {
    unsafe {
        if let Action::Upgrade { level, id } = act {
            let cost = upgrade_cost(inp, st, level, id);
            st.apples = st.apples.saturating_sub(cost);
            *st.p.get_unchecked_mut(level).get_unchecked_mut(id) += 1;
        }

        for j in 0..N {
            let inc = inp
                .a
                .get_unchecked(j)
                .saturating_mul(*st.b.get_unchecked(0).get_unchecked(j))
                .saturating_mul(*st.p.get_unchecked(0).get_unchecked(j) as u128);
            st.apples = st.apples.saturating_add(inc);
        }

        // i=1 -> b0
        for j in 0..N {
            let inc =
                st.b.get_unchecked(1)
                    .get_unchecked(j)
                    .saturating_mul(*st.p.get_unchecked(1).get_unchecked(j) as u128);
            let b0 = st.b.get_unchecked_mut(0).get_unchecked_mut(j);
            *b0 = b0.saturating_add(inc);
        }
        // i=2 -> b1
        for j in 0..N {
            let inc =
                st.b.get_unchecked(2)
                    .get_unchecked(j)
                    .saturating_mul(*st.p.get_unchecked(2).get_unchecked(j) as u128);
            let b1 = st.b.get_unchecked_mut(1).get_unchecked_mut(j);
            *b1 = b1.saturating_add(inc);
        }
        // i=3 -> b2
        for j in 0..N {
            let inc =
                st.b.get_unchecked(3)
                    .get_unchecked(j)
                    .saturating_mul(*st.p.get_unchecked(3).get_unchecked(j) as u128);
            let b2 = st.b.get_unchecked_mut(2).get_unchecked_mut(j);
            *b2 = b2.saturating_add(inc);
        }
    }
}

#[inline(always)]
fn apply_action_checked(inp: &ProblemInput, st: &mut State, act: Action) -> bool {
    if let Action::Upgrade { level, id } = act {
        let cost = upgrade_cost(inp, st, level, id);
        if cost > st.apples {
            return false;
        }
    }
    step_unchecked(inp, st, act);
    true
}

// ========== Candidate Buf ==========
struct CandidateBuf {
    data: [(f64, Action); BRANCH],
    len: usize,
}
impl CandidateBuf {
    fn new() -> Self {
        Self {
            data: [(0.0, Action::Wait); BRANCH],
            len: 0,
        }
    }
    fn reset(&mut self) {
        self.len = 0;
    }
    fn push(&mut self, score: f64, act: Action) {
        if self.len == BRANCH && score <= self.data[BRANCH - 1].0 {
            return;
        }
        let mut pos = self.len;
        while pos > 0 && self.data[pos - 1].0 < score {
            pos -= 1;
        }
        if pos < BRANCH {
            if self.len < BRANCH {
                self.len += 1;
            }
            unsafe {
                let ptr = self.data.as_mut_ptr();
                for i in (pos + 1..self.len).rev() {
                    *ptr.add(i) = *ptr.add(i - 1);
                }
                *ptr.add(pos) = (score, act);
            }
        }
    }
}

fn gen_top_candidates_fast(
    inp: &ProblemInput,
    st: &State,
    rem_turns: usize,
    coeffs: &Coeffs,
    out: &mut CandidateBuf,
) {
    out.reset();
    let rem_f = rem_turns.max(20) as f64;

    for i in 0..L {
        for j in 0..N {
            if !prereq_ok(st, i, j) {
                continue;
            }
            let cost = upgrade_cost(inp, st, i, j);
            if cost == 0 || cost > st.apples {
                continue;
            }

            let a = inp.a[j];
            unsafe {
                let p0 = *st.p.get_unchecked(0).get_unchecked(j) as u128;
                let b0 = *st.b.get_unchecked(0).get_unchecked(j);

                let delta = match i {
                    0 => {
                        let p1 = *st.p.get_unchecked(1).get_unchecked(j) as u128;
                        let b1 = *st.b.get_unchecked(1).get_unchecked(j);
                        let t1 = a.saturating_mul(b0).saturating_mul(coeffs.c1);
                        if p1 == 0 {
                            t1
                        } else {
                            let t2 = a
                                .saturating_mul(b1)
                                .saturating_mul(p1)
                                .saturating_mul(coeffs.c2);
                            let p2 = *st.p.get_unchecked(2).get_unchecked(j) as u128;
                            if p2 == 0 {
                                t1.saturating_add(t2)
                            } else {
                                let b2 = *st.b.get_unchecked(2).get_unchecked(j);
                                let t3 = a
                                    .saturating_mul(b2)
                                    .saturating_mul(p1)
                                    .saturating_mul(p2)
                                    .saturating_mul(coeffs.c3);
                                let p3 = *st.p.get_unchecked(3).get_unchecked(j) as u128;
                                if p3 == 0 {
                                    t1.saturating_add(t2).saturating_add(t3)
                                } else {
                                    let b3 = *st.b.get_unchecked(3).get_unchecked(j);
                                    let t4 = a
                                        .saturating_mul(b3)
                                        .saturating_mul(p1)
                                        .saturating_mul(p2)
                                        .saturating_mul(p3)
                                        .saturating_mul(coeffs.c4);
                                    t1.saturating_add(t2).saturating_add(t3).saturating_add(t4)
                                }
                            }
                        }
                    }
                    1 => {
                        if p0 == 0 {
                            0
                        } else {
                            let b1 = *st.b.get_unchecked(1).get_unchecked(j);
                            let t2 = a
                                .saturating_mul(p0)
                                .saturating_mul(b1)
                                .saturating_mul(coeffs.c2);
                            let p2 = *st.p.get_unchecked(2).get_unchecked(j) as u128;
                            if p2 == 0 {
                                t2
                            } else {
                                let b2 = *st.b.get_unchecked(2).get_unchecked(j);
                                let t3 = a
                                    .saturating_mul(p0)
                                    .saturating_mul(b2)
                                    .saturating_mul(p2)
                                    .saturating_mul(coeffs.c3);
                                let p3 = *st.p.get_unchecked(3).get_unchecked(j) as u128;
                                if p3 == 0 {
                                    t2.saturating_add(t3)
                                } else {
                                    let b3 = *st.b.get_unchecked(3).get_unchecked(j);
                                    let t4 = a
                                        .saturating_mul(p0)
                                        .saturating_mul(b3)
                                        .saturating_mul(p2)
                                        .saturating_mul(p3)
                                        .saturating_mul(coeffs.c4);
                                    t2.saturating_add(t3).saturating_add(t4)
                                }
                            }
                        }
                    }
                    2 => {
                        if p0 == 0 {
                            0
                        } else {
                            let p1 = *st.p.get_unchecked(1).get_unchecked(j) as u128;
                            if p1 == 0 {
                                0
                            } else {
                                let b2 = *st.b.get_unchecked(2).get_unchecked(j);
                                let t3 = a
                                    .saturating_mul(p0)
                                    .saturating_mul(p1)
                                    .saturating_mul(b2)
                                    .saturating_mul(coeffs.c3);
                                let p3 = *st.p.get_unchecked(3).get_unchecked(j) as u128;
                                if p3 == 0 {
                                    t3
                                } else {
                                    let b3 = *st.b.get_unchecked(3).get_unchecked(j);
                                    let t4 = a
                                        .saturating_mul(p0)
                                        .saturating_mul(p1)
                                        .saturating_mul(b3)
                                        .saturating_mul(p3)
                                        .saturating_mul(coeffs.c4);
                                    t3.saturating_add(t4)
                                }
                            }
                        }
                    }
                    3 => {
                        let p1 = *st.p.get_unchecked(1).get_unchecked(j) as u128;
                        let p2 = *st.p.get_unchecked(2).get_unchecked(j) as u128;
                        if p0 == 0 || p1 == 0 || p2 == 0 {
                            0
                        } else {
                            let b3 = *st.b.get_unchecked(3).get_unchecked(j);
                            a.saturating_mul(p0)
                                .saturating_mul(p1)
                                .saturating_mul(p2)
                                .saturating_mul(b3)
                                .saturating_mul(coeffs.c4)
                        }
                    }
                    _ => 0,
                };
                if delta == 0 {
                    continue;
                }

                let dynamic_weight = if i == 0 {
                    1.0
                } else {
                    (inp.cost_scale[j] / rem_f).powi(i as i32)
                };
                let eff = (delta as f64) / (cost as f64) * dynamic_weight;
                out.push(eff, Action::Upgrade { level: i, id: j });
            }
        }
    }
}

// ========== Rolling Horizon Beam Search ==========
fn plan_next_action(
    inp: &ProblemInput,
    cur: &State,
    turn: usize,
    rng: &mut XorShift64,
    beam_buf: &mut Vec<Node>,
    next_buf: &mut Vec<Node>,
    cand_buf: &mut CandidateBuf,
) -> Action {
    let remaining = inp.t.saturating_sub(turn);
    if remaining == 0 {
        return Action::Wait;
    }
    let horizon = HORIZON.min(remaining);

    beam_buf.clear();
    let coeffs_now = calc_coeffs(remaining);
    beam_buf.push(Node {
        st: cur.clone(),
        first: Action::Wait,
        score: score_state_fast(inp, cur, remaining, &coeffs_now),
        is_wait_line: true,
    });

    for depth in 0..horizon {
        let rem_time = remaining - depth;
        let next_rem = rem_time.saturating_sub(1);

        let coeffs_curr = calc_coeffs(rem_time);
        let coeffs_next = calc_coeffs(next_rem);

        next_buf.clear();

        for node in beam_buf.iter() {
            gen_top_candidates_fast(inp, &node.st, rem_time, &coeffs_curr, cand_buf);

            // Wait
            {
                let mut st2 = node.st.clone();
                let _ = apply_action_checked(inp, &mut st2, Action::Wait);
                let first = if depth == 0 { Action::Wait } else { node.first };
                let sc =
                    score_state_fast(inp, &st2, next_rem, &coeffs_next) + rng.next_f64() * 1e-9;

                next_buf.push(Node {
                    st: st2,
                    first,
                    score: sc,
                    is_wait_line: node.is_wait_line,
                });
            }

            // Upgrades
            for i in 0..cand_buf.len {
                let act = cand_buf.data[i].1;
                let mut st2 = node.st.clone();
                if !apply_action_checked(inp, &mut st2, act) {
                    continue;
                }
                let first = if depth == 0 { act } else { node.first };
                let sc =
                    score_state_fast(inp, &st2, next_rem, &coeffs_next) + rng.next_f64() * 1e-9;

                next_buf.push(Node {
                    st: st2,
                    first,
                    score: sc,
                    is_wait_line: false,
                });
            }
        }

        next_buf.sort_unstable_by(|a, b| b.score.partial_cmp(&a.score).unwrap_or(Ordering::Equal));

        let has_wait_line_in_top = next_buf.iter().take(BEAM_WIDTH).any(|n| n.is_wait_line);
        if next_buf.len() > BEAM_WIDTH {
            if !has_wait_line_in_top {
                if let Some(pos) = next_buf.iter().position(|n| n.is_wait_line) {
                    next_buf.swap(BEAM_WIDTH - 1, pos);
                }
            }
            next_buf.truncate(BEAM_WIDTH);
        }

        std::mem::swap(beam_buf, next_buf);
        if beam_buf.is_empty() {
            break;
        }
    }

    beam_buf.first().map(|n| n.first).unwrap_or(Action::Wait)
}

fn greedy_fallback(
    inp: &ProblemInput,
    st: &State,
    turn: usize,
    cand_buf: &mut CandidateBuf,
) -> Action {
    let rem = inp.t.saturating_sub(turn);
    let coeffs = calc_coeffs(rem);
    gen_top_candidates_fast(inp, st, rem, &coeffs, cand_buf);
    if cand_buf.len > 0 {
        cand_buf.data[0].1
    } else {
        Action::Wait
    }
}

// ========== SA helpers ==========
#[inline(always)]
fn score_final(apples: u128) -> f64 {
    ((apples.max(1)) as f64).ln()
}

fn simulate_full_inplace(
    inp: &ProblemInput,
    actions: &[Action],
    state_before: &mut Vec<State>,
) -> (bool, u128) {
    state_before.clear();
    let mut st = State {
        apples: inp.k0,
        b: [[1u128; N]; L],
        p: [[0u32; N]; L],
    };
    state_before.push(st.clone());
    for t in 0..inp.t {
        if !apply_action_checked(inp, &mut st, actions[t]) {
            return (false, 0);
        }
        state_before.push(st.clone());
    }
    (true, st.apples)
}

#[inline(always)]
fn temperature(elapsed: f64, deadline: f64) -> f64 {
    let x = (elapsed / deadline).min(1.0);
    SA_T0 * (SA_T1 / SA_T0).powf(x)
}

#[inline(always)]
fn sample_affordable_action(
    rng: &mut XorShift64,
    inp: &ProblemInput,
    st_before: &State,
    current: Action,
) -> Action {
    let mut opts: [Action; 41] = [Action::Wait; 41];
    let mut m: usize = 0;

    unsafe {
        for level in 0..L {
            for id in 0..N {
                let cost = inp.c.get_unchecked(level).get_unchecked(id).saturating_mul(
                    (*st_before.p.get_unchecked(level).get_unchecked(id) as u128).saturating_add(1),
                );
                if cost <= st_before.apples {
                    opts[m] = Action::Upgrade { level, id };
                    m += 1;
                }
            }
        }
    }
    opts[m] = Action::Wait;
    let total = m + 1;

    if total == 1 {
        return Action::Wait;
    }

    loop {
        let cand = opts[rng.gen_usize(total)];
        if cand != current {
            return cand;
        }
        if total < 5 {
            // fallback
            let mut candidates: [Action; 41] = [Action::Wait; 41];
            let mut k: usize = 0;
            for i in 0..total {
                if opts[i] != current {
                    candidates[k] = opts[i];
                    k += 1;
                }
            }
            if k == 0 {
                return current;
            }
            return candidates[rng.gen_usize(k)];
        }
    }
}

// 出力前の安全弁：払えない upgrade を wait に落として必ず合法化
fn repair_to_valid(inp: &ProblemInput, actions: &mut [Action]) -> u128 {
    let mut st = State {
        apples: inp.k0,
        b: [[1u128; N]; L],
        p: [[0u32; N]; L],
    };
    for t in 0..inp.t {
        if !apply_action_checked(inp, &mut st, actions[t]) {
            actions[t] = Action::Wait;
            let _ = apply_action_checked(inp, &mut st, Action::Wait);
        }
    }
    st.apples
}

// ========== Main ==========
fn main() {
    input! {
        _n_in: usize, _l_in: usize,
        t: usize, k: u64,
        a_in: [u64; N],
        c_in: [[u64; N]; L],
    }

    let mut a = [0u128; N];
    for j in 0..N {
        a[j] = a_in[j] as u128;
    }
    let mut c = [[0u128; N]; L];
    for i in 0..L {
        for j in 0..N {
            c[i][j] = c_in[i][j] as u128;
        }
    }

    let mut cost_scale = [0.0; N];
    for j in 0..N {
        let c0 = c[0][j].max(1) as f64;
        let c3 = c[3][j].max(1) as f64;
        cost_scale[j] = (c3 / c0).powf(1.0 / 3.0);
    }

    let inp = ProblemInput {
        t,
        k0: k as u128,
        a,
        c,
        cost_scale,
    };

    let start = Instant::now();
    let deadline = TIME_LIMIT_SEC - SA_SAFE_MARGIN;

    let mut rng = XorShift64::new(RNG_SEED);

    // ===== 1) 初期解（元ビーム） =====
    let mut beam_buf: Vec<Node> = Vec::with_capacity(BEAM_WIDTH * (BRANCH + 1));
    let mut next_buf: Vec<Node> = Vec::with_capacity(BEAM_WIDTH * (BRANCH + 1));
    let mut cand_buf = CandidateBuf::new();

    let mut actions: Vec<Action> = vec![Action::Wait; inp.t];
    let mut state_before: Vec<State> = Vec::with_capacity(inp.t + 1);

    let mut current_st = State {
        apples: inp.k0,
        b: [[1u128; N]; L],
        p: [[0u32; N]; L],
    };

    for turn in 0..inp.t {
        let elapsed = start.elapsed().as_secs_f64();
        let mode = if elapsed > deadline {
            2
        } else if elapsed > deadline - 0.10 {
            1
        } else {
            0
        };

        let act = match mode {
            2 => Action::Wait,
            1 => greedy_fallback(&inp, &current_st, turn, &mut cand_buf),
            _ => plan_next_action(
                &inp,
                &current_st,
                turn,
                &mut rng,
                &mut beam_buf,
                &mut next_buf,
                &mut cand_buf,
            ),
        };

        let mut next_st = current_st.clone();
        if apply_action_checked(&inp, &mut next_st, act) {
            actions[turn] = act;
            current_st = next_st;
        } else {
            actions[turn] = Action::Wait;
            step_unchecked(&inp, &mut current_st, Action::Wait);
        }
    }

    // 初期解を state_before に落とす
    let (ok_init, final_apples_init) = simulate_full_inplace(&inp, &actions, &mut state_before);
    if !ok_init {
        actions.fill(Action::Wait);
        let _ = simulate_full_inplace(&inp, &actions, &mut state_before);
    }

    let mut cur_actions = actions.clone();
    let mut cur_score = score_final(final_apples_init);
    let mut best_actions = cur_actions.clone();
    let mut best_score = cur_score;

    // ===== 2) SA =====
    let mut iters: u64 = 0;
    let mut accepted: u64 = 0;
    let mut improved: u64 = 0;

    // 区間リライト用バッファ（スタックに置くとでかいのでここで確保）
    let mut new_seg: Vec<Action> = Vec::with_capacity(REWRITE_MAX_LEN);

    while start.elapsed().as_secs_f64() < deadline {
        iters += 1;

        let elapsed = start.elapsed().as_secs_f64();
        let temp = temperature(elapsed, deadline);

        let u = rng.next_f64();

        if u < P_MOVE_POINT {
            // ========== 近傍1: 1点変更 ==========
            let t0 = rng.gen_usize(inp.t);
            let old_act = cur_actions[t0];
            let st_start = unsafe { state_before.get_unchecked(t0) };

            let new_act = sample_affordable_action(&mut rng, &inp, st_start, old_act);
            if new_act == old_act {
                continue;
            }

            // Dry run
            let mut dry_st = st_start.clone();
            if !apply_action_checked(&inp, &mut dry_st, new_act) {
                continue;
            }
            let mut valid = true;
            for t in (t0 + 1)..inp.t {
                let act = unsafe { *cur_actions.get_unchecked(t) };
                if !apply_action_checked(&inp, &mut dry_st, act) {
                    valid = false;
                    break;
                }
            }
            if !valid {
                continue;
            }

            let new_score = score_final(dry_st.apples);
            let delta = new_score - cur_score;
            let accept = if delta >= 0.0 {
                true
            } else {
                let p = (delta / temp.max(SA_FORCE_ACCEPT_EPS)).exp();
                rng.next_f64() < p
            };

            if accept {
                accepted += 1;
                cur_score = new_score;
                cur_actions[t0] = new_act;

                // Commit: recompute state_before from t0
                let mut commit_st = st_start.clone();
                step_unchecked(&inp, &mut commit_st, new_act);
                unsafe {
                    *state_before.get_unchecked_mut(t0 + 1) = commit_st.clone();
                    for t in (t0 + 1)..inp.t {
                        let act = *cur_actions.get_unchecked(t);
                        // dry run で合法保証されてるので unchecked
                        step_unchecked(&inp, &mut commit_st, act);
                        *state_before.get_unchecked_mut(t + 1) = commit_st.clone();
                    }
                }

                if cur_score > best_score {
                    best_score = cur_score;
                    best_actions = cur_actions.clone();
                    improved += 1;
                }
            }
        } else if u < P_MOVE_POINT + P_MOVE_SWAP {
            // ========== 近傍2: swap ==========
            let t1 = rng.gen_usize(inp.t);
            let mut t2 = rng.gen_usize(inp.t);
            while t2 == t1 {
                t2 = rng.gen_usize(inp.t);
            }
            let (l, r) = if t1 < t2 { (t1, t2) } else { (t2, t1) };

            let a_l = unsafe { *cur_actions.get_unchecked(l) };
            let a_r = unsafe { *cur_actions.get_unchecked(r) };
            if a_l == a_r {
                continue;
            }

            let st_start = unsafe { state_before.get_unchecked(l) };

            // Dry run with swapped actions
            let mut dry_st = st_start.clone();
            let mut valid = true;
            for t in l..inp.t {
                let act = if t == l {
                    a_r
                } else if t == r {
                    a_l
                } else {
                    unsafe { *cur_actions.get_unchecked(t) }
                };
                if !apply_action_checked(&inp, &mut dry_st, act) {
                    valid = false;
                    break;
                }
            }
            if !valid {
                continue;
            }

            let new_score = score_final(dry_st.apples);
            let delta = new_score - cur_score;
            let accept = if delta >= 0.0 {
                true
            } else {
                let p = (delta / temp.max(SA_FORCE_ACCEPT_EPS)).exp();
                rng.next_f64() < p
            };

            if accept {
                accepted += 1;
                cur_score = new_score;

                // Commit swap in cur_actions
                cur_actions[l] = a_r;
                cur_actions[r] = a_l;

                // Commit states from l
                let mut commit_st = st_start.clone();
                for t in l..inp.t {
                    let act = unsafe { *cur_actions.get_unchecked(t) };
                    step_unchecked(&inp, &mut commit_st, act);
                    unsafe {
                        *state_before.get_unchecked_mut(t + 1) = commit_st.clone();
                    }
                }

                if cur_score > best_score {
                    best_score = cur_score;
                    best_actions = cur_actions.clone();
                    improved += 1;
                }
            }
        } else {
            // ========== 近傍3: 区間リライト ==========
            let l = rng.gen_usize(inp.t);
            let max_len = REWRITE_MAX_LEN.min(inp.t - l);
            let len = 1 + rng.gen_usize(max_len);
            let r = l + len - 1;

            let st_start = unsafe { state_before.get_unchecked(l) };

            // segment を生成（その時点で払える行動からサンプルし、区間内で順に状態更新）
            new_seg.clear();
            let mut seg_st = st_start.clone();
            for t in l..=r {
                let old_act = unsafe { *cur_actions.get_unchecked(t) };
                let new_act = sample_affordable_action(&mut rng, &inp, &seg_st, old_act);
                // ここで払えないのが出たら候補生成ロジックがおかしいので弾く
                if !apply_action_checked(&inp, &mut seg_st, new_act) {
                    new_seg.clear();
                    break;
                }
                new_seg.push(new_act);
            }
            if new_seg.len() != len {
                continue;
            }

            // Dry run from l with rewritten segment
            let mut dry_st = st_start.clone();
            let mut valid = true;
            // apply segment
            for k in 0..len {
                let act = new_seg[k];
                if !apply_action_checked(&inp, &mut dry_st, act) {
                    valid = false;
                    break;
                }
            }
            if !valid {
                continue;
            }
            // apply tail
            for t in (r + 1)..inp.t {
                let act = unsafe { *cur_actions.get_unchecked(t) };
                if !apply_action_checked(&inp, &mut dry_st, act) {
                    valid = false;
                    break;
                }
            }
            if !valid {
                continue;
            }

            let new_score = score_final(dry_st.apples);
            let delta = new_score - cur_score;
            let accept = if delta >= 0.0 {
                true
            } else {
                let p = (delta / temp.max(SA_FORCE_ACCEPT_EPS)).exp();
                rng.next_f64() < p
            };

            if accept {
                accepted += 1;
                cur_score = new_score;

                // Commit segment into cur_actions
                for k in 0..len {
                    cur_actions[l + k] = new_seg[k];
                }

                // Commit states from l
                let mut commit_st = st_start.clone();
                for t in l..inp.t {
                    let act = unsafe { *cur_actions.get_unchecked(t) };
                    step_unchecked(&inp, &mut commit_st, act);
                    unsafe {
                        *state_before.get_unchecked_mut(t + 1) = commit_st.clone();
                    }
                }

                if cur_score > best_score {
                    best_score = cur_score;
                    best_actions = cur_actions.clone();
                    improved += 1;
                }
            }
        }
    }

    if LOG {
        eprintln!(
            "[LOG] elapsed={:.3}s iters={} accepted={} improved={} best_score={:.6}",
            start.elapsed().as_secs_f64(),
            iters,
            accepted,
            improved,
            best_score
        );
    }

    // ===== 3) 出力前に必ず合法化（WA防止）=====
    let mut out_actions = best_actions;
    let final_apples = repair_to_valid(&inp, &mut out_actions);
    if LOG {
        eprintln!(
            "[LOG] repaired_final_apples={} repaired_log_score={:.6}",
            final_apples,
            score_final(final_apples)
        );
    }

    let mut out = String::with_capacity(inp.t * 8);
    for act in out_actions {
        out.push_str(&act.format());
        out.push('\n');
    }
    print!("{out}");
}

Submission Info

Compile Error

warning: constant `P_MOVE_REWRITE` is never used
  --> src/main.rs:29:7
   |
29 | const P_MOVE_REWRITE: f64 = 0.20; // 区間リライト
   |       ^^^^^^^^^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

Judge Result