#1162533 (Rust) No.5024 魔法少女うなと宝集め

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: tomerun
• 提出日時: 2026-05-02 17:28:23
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 11 ms / 2,000 ms
• コード長: 9,393 bytes
• コンパイル時間: 1,427 ms
• コンパイル使用メモリ: 201,288 KB
• 実行使用メモリ: 6,400 KB
• スコア: 2,045,688
• 最終ジャッジ日時: 2026-05-02 17:28:29
• 合計ジャッジ時間: 4,945 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_1

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

ソースコード

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

const TIMELIMIT: u64 = 900;
const INF: usize = 1 << 28;
const N: usize = 20;

#[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 next_line(&mut self) -> String {
        let mut line = String::new();
        self.reader.read_line(&mut line).unwrap();
        if let Some(s) = line.strip_suffix("\n") { s.to_string() } else { line }
    }

    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 i32(&mut self) -> i32 {
        self.next_as::<i32>().unwrap()
    }

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

    pub fn u64(&mut self) -> u64 {
        self.next_as::<u64>().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
    }
}

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)
    }
}

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

#[derive(Debug, Clone)]
struct Input {
    T: usize,
    A: Vec<Vec<usize>>,
}

impl Input {
    fn new() -> Input {
        let mut sc = scanner();
        let _ = sc.usize();
        let T = sc.usize();
        let mut A = vec![vec![0; N]; N];
        for i in 0..N {
            for j in 0..N {
                A[i][j] = sc.usize();
            }
        }
        Input { T, A }
    }
}

#[derive(Debug, Clone)]
struct Result {
    path: Vec<Pos>,
    score: usize,
}

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

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

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

struct Solver {
    input: Input,
    timer: Timer,
    rng: XorShift32,
    acc: Vec<Vec<usize>>,
}

impl Solver {
    fn new(input: Input) -> Solver {
        let tl = env::var("TL").map_or(TIMELIMIT, |v| v.parse().unwrap());
        let timer = Timer::new(tl);
        let rng = XorShift32::from_seed(2);
        let mut acc = vec![];
        for i in 0..N {
            let mut row = vec![0];
            for j in 0..N {
                row.push(row.last().unwrap() + input.A[i][j]);
            }
            acc.push(row);
        }
        Solver { input, timer, rng, acc }
    }

    fn solve_dp(&mut self) -> Result {
        let mut dp = vec![vec![vec![(0, 0); self.input.T + 1]; N]; N];
        for i in 0..N {
            for l in 0..N {
                for r in l..N {
                    let sum = self.acc[i][r + 1] - self.acc[i][l];
                    if r - l + 1 <= self.input.T && sum > dp[i][r][r - l + 1].0 {
                        dp[i][r][r - l + 1] = (sum, l);
                    }
                    if r - l + 1 <= self.input.T && sum > dp[i][l][r - l + 1].0 {
                        dp[i][l][r - l + 1] = (sum, r);
                    }
                }
            }
            if i == 0 {
                continue;
            }
            for px in 0..N {
                for pt in 0..self.input.T {
                    if dp[i - 1][px][pt].0 == 0 {
                        continue;
                    }
                    for nx in 0..px {
                        let sum = self.acc[i][px + 1] - self.acc[i][nx] + dp[i - 1][px][pt].0;
                        let nt = pt + px - nx + 1;
                        if nt <= self.input.T && sum > dp[i][nx][nt].0 {
                            dp[i][nx][nt] = (sum, px);
                        }
                    }
                    for nx in (px + 1)..N {
                        let sum = self.acc[i][nx + 1] - self.acc[i][px] + dp[i - 1][px][pt].0;
                        let nt = pt + nx - px + 1;
                        if nt <= self.input.T && sum > dp[i][nx][nt].0 {
                            dp[i][nx][nt] = (sum, px);
                        }
                    }
                }
            }
        }
        let mut max_y = 0;
        let mut max_x = 0;
        let mut max_v = 0;
        let mut max_t = 0;
        for i in 0..N {
            for j in 0..N {
                for t in 0..=self.input.T {
                    if dp[i][j][t].0 > max_v {
                        max_v = dp[i][j][t].0;
                        max_y = i;
                        max_x = j;
                        max_t = t;
                    }
                }
            }
        }
        eprintln!("score:{:?} y:{} x:{}", max_v, max_y, max_x);
        let mut path = vec![];
        while max_t > 0 {
            let prev_x = dp[max_y][max_x][max_t].1;
            if prev_x < max_x {
                for x in (prev_x..=max_x).rev() {
                    path.push(Pos { y: max_y, x });
                }
            } else {
                for x in max_x..=prev_x {
                    path.push(Pos { y: max_y, x });
                }
            }
            max_t -= max_x.abs_diff(prev_x) + 1;
            max_y = max_y.wrapping_sub(1);
            max_x = prev_x;
        }
        Result::new(path, max_v)
    }

    // fn solve(&mut self, _tl: u64) -> Result {
    //     let mut best_res = self.solve(4001).unwrap();
    //     eprintln!("best_score:{}", best_res.raw_score);
    //     // let mut turn = 0;
    //     // loop {
    //     //     self.timer.checkpoint();
    //     //     if self.timer.should_stop() {
    //     //         eprintln!("total_turn: {}", turn);
    //     //         break;
    //     //     }
    //     //     turn += 1;
    //     //     let res = self.solve_3(best_res.raw_score);
    //     //     if res.is_none() {
    //     //         continue;
    //     //     }
    //     //     let res = res.unwrap();
    //     //     if res.score > best_res.score {
    //     //         best_res = res;
    //     //         eprintln!("best_score:{:?} turn:{:?}", best_res.raw_score, turn);
    //     //     }
    //     // }
    //     best_res
    // }

    // fn solve_one(&mut self, _best_raw_score: usize) -> Option<Result> {
    //     let res = Result::new(ops);
    //     Some(res)
    // }
}

fn main() {
    let input = Input::new();
    let mut solver = Solver::new(input.clone());
    let best_res = solver.solve_dp();
    best_res.output();
    eprintln!("final_score:{:?}", best_res.score);
}