#1195239 (Rust) No.5025 Forest Fire

• 問題: No.5025 Forest Fire
• ユーザー: tomerun
• 提出日時: 2026-10-24 20:20:00
• 言語: Rust (1.99.0 + proconio + num + itertools + ACL)
• 結果: AC
• 実行時間: 1,912 ms / 2,000 ms
• コード長: 15,615 bytes
• コンパイル時間: 4,686 ms
• コンパイル使用メモリ: 199,512 KB
• 実行使用メモリ: 9,928 KB
• スコア: 186,380,184
• 最終ジャッジ日時: 2026-10-24 20:22:43
• 合計ジャッジ時間: 162,385 ms
• ジャッジサーバーID （参考情報）: judge1_0 / <nil>

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

ソースコード

#![allow(unused_imports)]
#![allow(dead_code)]
#![allow(non_snake_case)]
use std::cmp::Ordering;
use std::env;
use std::io::{self, BufReader, Read, Stdin};
use std::str::FromStr;
use std::string::String;
use std::time;

const TIMELIMIT: u64 = 1950;
const N: usize = 50;
const K: usize = 100;
const DIR_U: usize = 0;
const DIR_L: usize = 1;
const DIR_D: usize = 2;
const DIR_R: usize = 3;
const DY: [usize; 4] = [!0, 0, 1, 0];
const DX: [usize; 4] = [0, !0, 0, 1];
const DY2: [usize; 8] = [!0, !0, !0, 0, 1, 1, 1, 0];
const DX2: [usize; 8] = [!0, 0, 1, 1, 1, 0, !0, !0];

#[derive(Debug)]
pub struct Scanner<R> {
    reader: BufReader<R>,
}

fn scanner() -> Scanner<Stdin> {
    Scanner::new(io::stdin())
}

impl<R: io::Read> Scanner<R> {
    pub fn new(read: R) -> Scanner<R> {
        Scanner { reader: BufReader::new(read) }
    }

    pub fn next_str(&mut self) -> Option<String> {
        let mut buf = [0; 1];
        let size = self.reader.read(&mut buf).unwrap();
        if size == 0 {
            None
        } else {
            self.skip_whitespace(&mut buf)?;
            let mut v = vec![buf[0]];
            loop {
                let size = self.reader.read(&mut buf).unwrap();
                if size == 0 || buf[0].is_ascii_whitespace() {
                    break;
                }
                v.push(buf[0]);
            }
            Some(String::from_utf8(v).unwrap())
        }
    }

    pub fn vec<S: FromStr>(&mut self, size: i32) -> Vec<S> {
        let mut v: Vec<S> = vec![];
        for _ in 0..size {
            let token = self.next_str().unwrap();
            v.push(S::from_str(&token).ok().unwrap());
        }
        v
    }

    pub fn next_as<S: FromStr>(&mut self) -> Option<S> {
        let s = self.next_str()?;
        S::from_str(&s).ok()
    }

    pub fn str(&mut self) -> String {
        self.next_str().unwrap()
    }

    pub fn usize(&mut self) -> usize {
        self.next_as::<usize>().unwrap()
    }

    fn skip_whitespace(&mut self, mut buf: &mut [u8]) -> Option<u8> {
        loop {
            if !buf[0].is_ascii_whitespace() {
                return Some(buf[0]);
            }
            let size = self.reader.read(&mut buf).unwrap();
            if size == 0 {
                return None;
            }
        }
    }
}

#[derive(Debug)]
struct Timer {
    start_time: time::Instant,
    limit: time::Instant,
    before_time: Option<time::Instant>,
    worst_time: time::Duration,
}

impl Timer {
    fn new(tl: u64) -> Timer {
        let start_time = time::Instant::now();
        Timer {
            start_time,
            limit: start_time + time::Duration::from_millis(tl),
            before_time: None,
            worst_time: time::Duration::from_millis(0),
        }
    }

    fn elapsed(&self) -> u64 {
        self.start_time.elapsed().as_millis() as u64
    }

    fn checkpoint(&mut self) {
        if let Some(before_time) = self.before_time {
            let elapsed = before_time.elapsed();
            self.worst_time = self.worst_time.max(elapsed);
        }
        self.before_time = Some(time::Instant::now());
    }

    fn tl(&self) -> u64 {
        (self.limit - self.start_time).as_millis() as u64
    }

    fn tl_exceeded(&self) -> bool {
        self.limit < time::Instant::now()
    }

    fn should_stop(&self) -> bool {
        self.limit < time::Instant::now() + self.worst_time
    }

    fn should_stop_with_margin(&self, margin: u64) -> bool {
        self.limit < time::Instant::now() + self.worst_time + time::Duration::from_millis(margin)
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Pos {
    y: usize,
    x: usize,
}

impl Pos {
    fn new(y: usize, x: usize) -> Pos {
        Pos { y, x }
    }
}

#[derive(Debug)]
struct FastClearingArray<T> {
    v: [T; N * N],
    generation: [i32; N * N],
    cur_gen: i32,
}

impl<T: Copy> FastClearingArray<T> {
    fn new(init: T) -> FastClearingArray<T> {
        FastClearingArray { v: [init; N * N], generation: [0; N * N], cur_gen: 0 }
    }

    fn clear(&mut self) {
        self.cur_gen += 1;
    }

    fn visited(&self, idx: usize) -> bool {
        self.generation[idx] == self.cur_gen
    }

    fn get(&self, idx: usize) -> T {
        self.v[idx]
    }

    fn set(&mut self, idx: usize, v: T) {
        self.v[idx] = v;
        self.generation[idx] = self.cur_gen;
    }
}

struct XorShift32 {
    state: u32,
}

impl XorShift32 {
    fn from_seed(seed: u32) -> Self {
        let initial_state = if seed == 0 { 1 } else { seed };
        XorShift32 { state: initial_state }
    }

    fn next_u32(&mut self) -> u32 {
        let mut x = self.state;
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
        self.state = x;
        x
    }

    fn next_u64(&mut self) -> u64 {
        ((self.next_u32() as u64) << 32) | (self.next_u32() as u64)
    }

    fn next_f64(&mut self) -> f64 {
        self.next_u32() as f64 / (u32::MAX as f64 + 1.0)
    }

    fn random_range(&mut self, range: std::ops::Range<usize>) -> usize {
        let range_size = range.end - range.start;
        let random_value = self.next_u32() as usize % range_size;
        range.start + random_value
    }
}

#[derive(Debug, Clone)]
struct Input {
    d: [[usize; N]; N],
}

impl Input {
    fn new<T: io::Read>(sc: &mut Scanner<T>) -> Input {
        let _ = sc.usize();
        let _ = sc.usize();
        let mut d = [[0; N]; N];
        for i in 0..N {
            let row = sc.str();
            for (j, c) in row.chars().enumerate() {
                d[i][j] = c.to_digit(10).unwrap() as usize;
            }
        }
        Input { d }
    }
}

struct Result {
    cut: Vec<Pos>,
    score: usize,
}

impl Result {
    fn new_empty() -> Result {
        Result { cut: vec![], score: 0 }
    }

    fn new(cut: Vec<Pos>, score: usize) -> Result {
        Result { cut, score }
    }

    fn output(&self) {
        println!("{}", self.cut.len());
        for &p in &self.cut {
            println!("{} {}", p.y, p.x);
        }
    }
}

struct Solver {
    input: Input,
    timer: Timer,
    rng: XorShift32,
    buf: FastClearingArray<bool>,
    cut: Vec<Vec<usize>>,
    ok_sur: [bool; 256],
}

impl Solver {
    fn new() -> Solver {
        let mut scanner = scanner();
        let input = Input::new(&mut scanner);
        let tl = env::var("TL").map(|v| v.parse().unwrap()).unwrap_or(TIMELIMIT);
        let timer = Timer::new(tl);
        let rng = XorShift32::from_seed(2);
        let cut = vec![vec![0; N]; N];
        let mut ok_sur = [false; 256];
        for i in 1usize..256 {
            let popcnt = i.count_ones();
            if popcnt > 5 {
                continue;
            }
            let mut cnt = 0;
            for j in 0..8 {
                if (i >> j) & 1 == 1 && (i >> ((j + 1) % 8)) & 1 == 0 {
                    cnt += 1;
                }
            }
            ok_sur[i] = cnt == 1;
        }
        Solver { input, timer, rng, buf: FastClearingArray::new(false), cut, ok_sur }
    }

    fn solve(&mut self) -> Result {
        let mut start_pos = vec![];
        let mut paths = vec![];
        let th_low = 5;
        for i in 0..N {
            for j in 0..N {
                if self.input.d[i][j] <= th_low {
                    continue;
                }
                let mut sur = 0;
                for k in 0..8 {
                    let ny = i.wrapping_add(DY2[k]);
                    let nx = j.wrapping_add(DX2[k]);
                    if ny >= N || nx >= N || self.input.d[ny][nx] <= th_low {
                        sur |= 1 << k;
                    }
                }
                if self.ok_sur[sur] {
                    let mut dirs = vec![];
                    for k in 0..8 {
                        if (sur >> k) & 1 == 0 && (sur >> ((k + 1) % 8)) & 1 == 0 && (sur >> ((k + 7) % 8)) & 1 == 0 && k % 2 == 0
                        {
                            dirs.push(k);
                        }
                    }
                    // eprintln!("y:{} x:{} sur:{:b} dirs:{:?}", i, j, sur, dirs);
                    if !dirs.is_empty() {
                        start_pos.push((Pos::new(i, j), dirs));
                    }
                } else if 1 < sur.count_ones() && sur.count_ones() <= 5 && self.input.d[i][j] > 6 {
                    paths.push(vec![Pos::new(i, j)]);
                }
            }
        }
        for _ in 0..1000 {
            let (pos, dirs) = &start_pos[self.rng.random_range(0..start_pos.len())];
            let start_dir = dirs[self.rng.random_range(0..dirs.len())];
            let th = self.rng.random_range(4..6);
            if let Some(path) = self.find_path(pos, start_dir, th) {
                paths.push(path);
            }
        }
        let mut cut_cnt = 0;
        let mut use_path = vec![];
        for _ in 0..100 {
            let pi = self.rng.random_range(0..paths.len());
            if use_path.contains(&pi) {
                continue;
            }
            use_path.push(pi);
            for p in &paths[pi] {
                self.cut[p.y][p.x] += 1;
                if self.cut[p.y][p.x] == 1 {
                    cut_cnt += 1;
                }
            }
            if cut_cnt > K {
                use_path.pop();
                for p in &paths[pi] {
                    self.cut[p.y][p.x] -= 1;
                    if self.cut[p.y][p.x] == 0 {
                        cut_cnt -= 1;
                    }
                }
            }
        }
        let mut cur_val = self.evaluate();
        let mut best_cut = self.cut.clone();
        let mut turn = 0;
        let mut remove_pis = vec![];
        while self.timer.elapsed() < self.timer.tl() {
            turn += 1;
            let add_pi = self.rng.random_range(0..paths.len());
            if use_path.contains(&add_pi) {
                continue;
            }
            for p in &paths[add_pi] {
                self.cut[p.y][p.x] += 1;
                if self.cut[p.y][p.x] == 1 {
                    cut_cnt += 1;
                }
            }
            remove_pis.clear();

            while cut_cnt > K {
                let remove_pii = self.rng.random_range(0..use_path.len());
                if remove_pis.contains(&remove_pii) {
                    continue;
                }
                remove_pis.push(remove_pii);
                for p in &paths[use_path[remove_pii]] {
                    self.cut[p.y][p.x] -= 1;
                    if self.cut[p.y][p.x] == 0 {
                        cut_cnt -= 1;
                    }
                }
            }

            let new_val = self.evaluate();
            if new_val <= cur_val {
                cur_val = new_val;
                remove_pis.sort();
                remove_pis.reverse();
                for &remove_pii in &remove_pis {
                    use_path.swap_remove(remove_pii);
                }
                use_path.push(add_pi);
                for i in 0..N {
                    best_cut[i].copy_from_slice(&self.cut[i]);
                }
                eprintln!("val:{} cut_cnt:{} turn:{:?} ", cur_val, cut_cnt, turn);
            } else {
                for &remove_pii in &remove_pis {
                    for p in &paths[use_path[remove_pii]] {
                        self.cut[p.y][p.x] += 1;
                        if self.cut[p.y][p.x] == 1 {
                            cut_cnt += 1;
                        }
                    }
                }
                for p in &paths[add_pi] {
                    self.cut[p.y][p.x] -= 1;
                    if self.cut[p.y][p.x] == 0 {
                        cut_cnt -= 1;
                    }
                }
            }
        }
        eprintln!("turn:{:?}", turn);

        let mut cut_pos = vec![];
        for i in 0..N {
            for j in 0..N {
                if best_cut[i][j] > 0 {
                    cut_pos.push(Pos::new(i, j));
                }
            }
        }
        for i in 0..N {
            for j in 0..N {
                if cut_pos.len() < K && best_cut[i][j] == 0 && self.input.d[i][j] == 9 {
                    cut_pos.push(Pos::new(i, j));
                }
            }
        }

        Result::new(cut_pos, 0)
    }

    fn evaluate(&mut self) -> i64 {
        let mut val = 0;
        let mut q = vec![];
        for th in 5..=8 {
            self.buf.clear();
            for y in 0..N {
                for x in 0..N {
                    if self.input.d[y][x] < th || self.cut[y][x] > 0 || self.buf.visited(y * N + x) {
                        continue;
                    }
                    q.clear();
                    q.push((y, x));
                    self.buf.set(y * N + x, true);
                    let mut qi = 0;
                    while qi < q.len() {
                        let (cy, cx) = q[qi];
                        qi += 1;
                        for k in 0..4 {
                            let ny = cy.wrapping_add(DY[k]);
                            let nx = cx.wrapping_add(DX[k]);
                            if ny >= N
                                || nx >= N
                                || self.input.d[ny][nx] < th
                                || self.cut[ny][nx] > 0
                                || self.buf.visited(ny * N + nx)
                            {
                                continue;
                            }
                            self.buf.set(ny * N + nx, true);
                            q.push((ny, nx));
                        }
                    }
                    val += (qi * qi * th) as i64;
                }
            }
        }
        val
    }

    fn find_path(&mut self, sp: &Pos, dir: usize, th_stop: usize) -> Option<Vec<Pos>> {
        let mut cy = sp.y;
        let mut cx = sp.x;
        // let mut cur_dir = dir;
        let mut path = vec![*sp];
        loop {
            if path.len() > 1
                && (0..8).any(|k| {
                    let ny = cy.wrapping_add(DY2[k]);
                    let nx = cx.wrapping_add(DX2[k]);
                    ny >= N || nx >= N || self.input.d[ny][nx] <= th_stop
                })
            {
                break;
            }
            // let mut weight = [0; 8];
            // for nd in 0..8 {
            //     let p0 = DY2[nd] as i32 * DY2[dir] as i32 + DX2[nd] as i32 * DX2[dir] as i32;
            //     let p1 = DY2[nd] as i32 * DY2[cur_dir] as i32 + DX2[nd] as i32 * DX2[cur_dir] as i32;
            //     if p0 <= 0 && p1 <= 0 {
            //         continue;
            //     }
            //     let dv = self.input.d[cy.wrapping_add(DY2[nd])][cx.wrapping_add(DX2[nd])];
            //     weight[nd] = (p0 * 3 + p1 + 3).max(0) as usize + dv * dv;
            // }
            // let weight_sum: usize = weight.iter().sum();
            // let mut r = self.rng.random_range(1..weight_sum + 1);
            // let mut nd = 0;
            // for i in 0..8 {
            //     r = r.saturating_sub(weight[i]);
            //     if r == 0 {
            //         nd = i;
            //         break;
            //     }
            // }
            let nd = dir;
            cy = cy.wrapping_add(DY2[nd]);
            cx = cx.wrapping_add(DX2[nd]);
            // cur_dir = nd;
            path.push(Pos::new(cy, cx));
        }
        if path.len() > 30 {
            return None;
        }
        Some(path)
    }
}

fn main() {
    let mut solver = Solver::new();
    let res = solver.solve();
    res.output();
    eprintln!("final_score:{:5} elapsed:{:4}", res.score, solver.timer.elapsed(),);
}