結果

問題 No.3429 Palindromic Path (Hard)
コンテスト
ユーザー mentos_grape
提出日時 2026-01-11 13:52:45
言語 Rust
(1.92.0 + proconio + num)
結果
AC  
実行時間 386 ms / 2,000 ms
コード長 1,675 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 24,886 ms
コンパイル使用メモリ 412,232 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-11 13:53:15
合計ジャッジ時間 25,078 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#![allow(unused_imports)]

fn main() {
    input! {
        n: usize,
        s: [Chars; n],
    }
    let mut dp = HashMap::new();
    for i in 0..n {
        dp.insert((n-1-i, i, n-1-i, i), 1);
    }
    for _ in 0..n-1 {
        let mut ndp = HashMap::new();
        for ((a, b, c, d), v) in dp {
            for (da, db) in [(-1, 0), (0, -1)] {
                for (dc, dd) in [(1, 0), (0, 1)] {
                    let na = a.wrapping_add_signed(da);
                    let nb = b.wrapping_add_signed(db);
                    let nc = c.wrapping_add_signed(dc);
                    let nd = d.wrapping_add_signed(dd);
                    if na < n && nb < n && nc < n && nd < n && s[na][nb] == s[nc][nd] {
                        let e = ndp.entry((na, nb, nc, nd)).or_default();
                        *e = (*e + v) % 998244353;
                    }
                }
            }
        }
        dp = ndp;
    }
    println!("{}", dp.get(&(0, 0, n-1, n-1)).unwrap_or(&0));
}

use proconio::{input, marker::*};
use std::{cmp::Reverse, collections::*};

#[macro_export]
macro_rules! chmax {
    ($a:expr, $b:expr) => {{
        let tmp = $b;
        if $a < tmp {
            $a = tmp;
            true
        } else {
            false
        }
    }};
}

#[macro_export]
macro_rules! chmin {
    ($a:expr, $b:expr) => {{
        let tmp = $b;
        if $a > tmp {
            $a = tmp;
            true
        } else {
            false
        }
    }};
}

#[macro_export]
/// mvec![]
macro_rules! mvec {
    ($val:expr; ()) => {
        $val
    };
    ($val:expr; ($size:expr $(,$rest:expr)*)) => {
        vec![mvec![$val; ($($rest),*)]; $size]
    };
}
0