結果

問題 No.5024 魔法少女うなと宝集め
コンテスト
ユーザー t33f
提出日時 2026-05-02 17:42:50
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 38 ms / 2,000 ms
コード長 2,139 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,480 ms
コンパイル使用メモリ 203,264 KB
実行使用メモリ 25,472 KB
スコア 2,053,994
最終ジャッジ日時 2026-05-02 17:43:02
合計ジャッジ時間 6,886 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: structure field `T` should have a snake case name
 --> src/main.rs:8:5
  |
8 |     T: usize,
  |     ^ help: convert the identifier to snake case: `t`
  |
  = note: `#[warn(non_snake_case)]` (part of `#[warn(nonstandard_style)]`) on by default

warning: structure field `A` should have a snake case name
 --> src/main.rs:9:5
  |
9 |     A: Vec<Vec<i32>>,
  |     ^ help: convert the identifier to snake case: `a`

warning: variable `_N` should have a snake case name
  --> src/main.rs:74:9
   |
74 |         _N: usize,
   |         ^^ help: convert the identifier to snake case: `_n`

warning: variable `T` should have a snake case name
  --> src/main.rs:75:9
   |
75 |         T: usize,
   |         ^ help: convert the identifier to snake case: `t`

warning: variable `A` should have a snake case name
  --> src/main.rs:76:9
   |
76 |         A: [[i32; N]; N],
   |         ^ help: convert the identifier to snake case: `a`

ソースコード

diff #
raw source code 

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

const N: usize = 20;

struct Input {
    T: usize,
    A: Vec<Vec<i32>>,
}

fn solve(input: &Input) -> Vec<(usize, usize)> {
    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 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
}

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

    let input = Input{T, A};

    let ans = solve(&input);
    println!("{}", ans.len());
    for (i, j) in ans { println!("{i} {j}"); }
}
0