結果

問題 No.5024 魔法少女うなと宝集め
コンテスト
ユーザー t33f
提出日時 2026-05-02 17:55:59
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 65 ms / 2,000 ms
コード長 2,930 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 8,117 ms
コンパイル使用メモリ 193,524 KB
実行使用メモリ 25,472 KB
スコア 2,066,180
最終ジャッジ日時 2026-05-02 17:59:05
合計ジャッジ時間 17,782 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_1
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#![allow(unused_imports, non_snake_case)]
use proconio::{input, marker::*};
use itertools::*;

const N: usize = 20;

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

fn solve(input: &Input) -> (Vec<(usize, usize)>, i32) {
    let mut dp = vec![vec![vec![vec![(0, 0, 0, 0, 0); 3]; N]; N]; input.T];
    for (i, j) in iproduct!(0..N, 0..N) {
        dp[0][i][j][0] = (input.A[i][j], 0, 0, 0, 0);
    }

    const D: usize = 0;
    const R: usize = 1;
    const L: usize = 2;

    for t in 0..input.T - 1 {
        for (i, j) in iproduct!(0..N, 0..N) {
            for d in 0..3 {
                let s = dp[t][i][j][d].0;

                // down
                if i + 1 < N {
                    let s1 = s + input.A[i + 1][j];
                    if dp[t + 1][i + 1][j][D].0 < s1 {
                        dp[t + 1][i + 1][j][D] = (s1, t, i, j, d);
                    }
                }

                // left
                if d != R && j > 0 {
                    let s1 = s + input.A[i][j - 1];
                    if dp[t + 1][i][j - 1][L].0 < s1 {
                        dp[t + 1][i][j - 1][L] = (s1, t, i, j, d);
                    }
                }

                // right
                if d != L && j + 1 < N {
                    let s1 = s + input.A[i][j + 1];
                    if dp[t + 1][i][j + 1][R].0 < s1 {
                        dp[t + 1][i][j + 1][R] = (s1, t, i, j, d);
                    }
                }
            }
        }
    }

    let (mut i, mut j, mut d) = iproduct!(0..N, 0..N, 0..3)
        .max_by_key(|&(i, j, d)| dp[input.T - 1][i][j][d].0)
        .unwrap();
    let score = dp[input.T - 1][i][j][d].0;

    let mut rev_ans = vec![(i, j)];
    eprintln!("{i} {j} {d} {:?}", dp[input.T - 1][i][j][d]);
    for t in (1..input.T).rev() {
        let (_, _, i1, j1, d1) = dp[t][i][j][d];
        rev_ans.push((i1, j1));
        i = i1;
        j = j1;
        d = d1;
    }

    rev_ans.reverse();
    (rev_ans, score)
}

fn rotate_input(input: &Input) -> Input {
    let mut A = input.A.clone();
    for i in 0..N {
        for j in 0..N {
            A[i][j] = input.A[N - j - 1][i];
        }
    }
    Input{T: input.T, A}
}

fn rotate_output(ans: &Vec<(usize, usize)>) -> Vec<(usize, usize)> {
    ans.iter().map(|&(i, j)| (N - j - 1, i)).collect_vec()
}

fn main() {
    input!{
        _N: usize,
        T: usize,
        A: [[i32; N]; N],
    }

    let input = Input{T, A};

    let (ans, _score) =
        (0..2).map(|i| {
            let mut tmp_input = input.clone();
            for _ in 0..i { tmp_input = rotate_input(&tmp_input); }
            let (mut tmp_ans, score) = solve(&tmp_input);
            for _ in 0..i { tmp_ans = rotate_output(&tmp_ans); }
            (tmp_ans, score)
        })
        .max_by_key(|(_, score)| *score)
        .unwrap();

    println!("{}", ans.len());
    for (i, j) in ans { println!("{i} {j}"); }
}
0