結果
| 問題 | No.5024 魔法少女うなと宝集め |
| コンテスト | |
| ユーザー |
 tomerun
|
| 提出日時 | 2026-05-02 17:48:10 |
| 言語 | Rust (1.94.0 + proconio + num + itertools) |
| 結果 |
AC
|
| 実行時間 | 174 ms / 2,000 ms |
| コード長 | 11,047 bytes |
| 記録 | |
| コンパイル時間 | 2,365 ms |
| コンパイル使用メモリ | 202,072 KB |
| 実行使用メモリ | 6,400 KB |
| スコア | 2,111,020 |
| 最終ジャッジ日時 | 2026-05-02 17:49:30 |
| 合計ジャッジ時間 | 8,594 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge2_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,
}
impl Pos {
fn rot(&mut self) {
let tmp = self.y;
self.y = self.x;
self.x = N - 1 - tmp;
}
}
#[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,
}
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);
Solver { input, timer, rng }
}
fn solve(&mut self) -> Result {
let mut best_res = Result::new_empty();
for i in 0..4 {
let mut res = self.solve_dp();
if res.score > best_res.score {
for pos in &mut res.path {
for _ in 0..(4 - i) {
pos.rot();
}
}
eprintln!("rot:{:?} score:{:?}", i, res.score);
best_res = res;
}
// rot A
let mut tmp_A = vec![vec![0; N]; N];
for y in 0..N {
for x in 0..N {
tmp_A[y][x] = self.input.A[N - 1 - x][y];
}
}
self.input.A = tmp_A;
}
best_res
}
fn solve_dp(&mut self) -> Result {
let mut acc = vec![];
for i in 0..N {
let mut row = vec![0];
for j in 0..N {
row.push(row.last().unwrap() + self.input.A[i][j]);
}
acc.push(row);
}
let mut dp = vec![vec![vec![(0, 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 = acc[i][r + 1] - 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, INF);
}
if r - l + 1 <= self.input.T && sum > dp[i][l][r - l + 1].0 {
dp[i][l][r - l + 1] = (sum, r, INF);
}
}
}
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;
}
let ppx = dp[i - 1][px][pt].1;
for nx in 0..px {
let sum = acc[i][px + 1] - 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, INF);
}
for ux in nx..px - 1 {
if ux + 1 < ppx {
let sum = acc[i][px + 1] - acc[i][nx]
+ dp[i - 1][px][pt].0
+ self.input.A[i - 1][ux]
+ self.input.A[i - 1][ux + 1];
let nt = pt + px - nx + 3;
if nt <= self.input.T && sum > dp[i][nx][nt].0 {
dp[i][nx][nt] = (sum, px, ux);
}
}
}
}
for nx in (px + 1)..N {
let sum = acc[i][nx + 1] - 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, INF);
}
for ux in px + 1..nx - 1 {
if ppx < ux {
let sum = acc[i][nx + 1] - acc[i][px]
+ dp[i - 1][px][pt].0
+ self.input.A[i - 1][ux]
+ self.input.A[i - 1][ux + 1];
let nt = pt + nx - px + 3;
if nt <= self.input.T && sum > dp[i][nx][nt].0 {
dp[i][nx][nt] = (sum, px, ux + 1);
}
}
}
}
}
}
}
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;
let ux = dp[max_y][max_x][max_t].2;
if prev_x < max_x {
for x in (prev_x..=max_x).rev() {
path.push(Pos { y: max_y, x });
if x == ux {
path.push(Pos { y: max_y - 1, x });
path.push(Pos { y: max_y - 1, x: x - 1 });
}
}
} else {
for x in max_x..=prev_x {
path.push(Pos { y: max_y, x });
if x == ux {
path.push(Pos { y: max_y - 1, x });
path.push(Pos { y: max_y - 1, x: x + 1 });
}
}
}
max_t -= max_x.abs_diff(prev_x) + 1;
if ux != INF {
max_t -= 2;
}
max_y = max_y.wrapping_sub(1);
max_x = prev_x;
}
Result::new(path, max_v)
}
}
fn main() {
let input = Input::new();
let mut solver = Solver::new(input.clone());
let best_res = solver.solve();
best_res.output();
eprintln!("final_score:{:?}", best_res.score);
}