#1194370 (Rust) No.3429 Palindromic Path (Hard)

• 問題: No.3429 Palindromic Path (Hard)
• ユーザー: 👑 cologne
• 提出日時: 2026-10-23 15:03:31
• 言語: Rust (1.99.0 + proconio + num + itertools + ACL)
• 結果: AC
• 実行時間: 55 ms / 2,000 ms
• コード長: 3,510 bytes
• コンパイル時間: 1,028 ms
• コンパイル使用メモリ: 187,232 KB
• 実行使用メモリ: 34,816 KB
• 最終ジャッジ日時: 2026-10-23 15:03:42
• 合計ジャッジ時間: 3,122 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge5_0

ファイルパターン	結果
sample	AC * 3
other	AC * 7

コンパイルメッセージ

warning: unused variable: `pb`
  --> src/main.rs:35:30
   |
35 |                     let Some(pb) = mpos(i - 1, pa) else { continue };
   |                              ^^ help: if this is intentional, prefix it with an underscore: `_pb`
   |
   = note: `#[warn(unused_variables)]` (part of `#[warn(unused)]`) on by default

warning: unused variable: `pd`
  --> src/main.rs:37:34
   |
37 |                         let Some(pd) = ppos(i - 1, pc) else { continue };
   |                                  ^^ help: if this is intentional, prefix it with an underscore: `_pd`

ソースコード

use fio::*;

const M: u32 = 998_244_353;

fn main() {
    let n: usize = read();
    let mut st = vec![];
    for _ in 0..n {
        let s = read_line();
        st.push(s.bytes().collect::<Vec<_>>());
    }

    let mpos = |i: usize, a: usize| {
        (n - 1 - i)
            .checked_sub(a)
            .and_then(|x| (x < n).then_some(x))
    };
    let ppos = |i: usize, c: usize| (n - 1 + i - c < n).then_some(n - 1 + i - c);

    let mut dp = vec![vec![vec![0u32; n]; n]; n];

    for i in 0..n {
        dp[0][i][i] = 1;
    }

    for i in 1..n {
        for a in 0..n {
            let Some(b) = mpos(i, a) else { continue };
            for c in 0..n {
                let Some(d) = ppos(i, c) else { continue };
                if st[a][b] != st[c][d] {
                    continue;
                };
                for pa in a..=(a + 1).min(n - 1) {
                    let Some(pb) = mpos(i - 1, pa) else { continue };
                    for pc in c.saturating_sub(1)..=c {
                        let Some(pd) = ppos(i - 1, pc) else { continue };
                        dp[i][a][c] += dp[i - 1][pa][pc];
                        if dp[i][a][c] >= M {
                            dp[i][a][c] -= M;
                        }
                    }
                }
            }
        }
    }

    println!("{}", dp[n - 1][0][n - 1])
}

mod fio {
    use std::{
        cell::RefCell,
        convert::TryInto,
        fmt::Debug,
        io::{BufRead, BufWriter, StdinLock, StdoutLock, stdin, stdout},
        str::FromStr,
    };
    thread_local! {
        pub static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
        pub static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
    }

    #[allow(dead_code)]
    pub fn read<T: FromStr>() -> T
    where
        <T as FromStr>::Err: Debug,
    {
        read_line().parse().unwrap()
    }

    /// If there is a performance concern, use direct
    /// `read_line().spilt_ascii_whitespace().map(|x| x.parse().unwrap())`
    #[allow(dead_code)]
    pub fn read_vec<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        read_line()
            .split_ascii_whitespace()
            .map(|x| x.parse().unwrap())
            .collect()
    }

    /// If there is a performance concern, use direct
    /// `read_line().spilt_ascii_whitespace().map(|x| x.parse().unwrap())`
    #[allow(dead_code)]
    pub fn read_tuple<T, const N: usize>() -> [T; N]
    where
        T: FromStr + Debug,
        <T as FromStr>::Err: Debug,
    {
        read_vec::<T>().try_into().unwrap()
    }

    /// whitespace at the end of the line is ignored
    pub fn read_line() -> String {
        let mut s = String::new();
        STDIN.with(|cell| {
            cell.borrow_mut().read_line(&mut s).unwrap();
        });
        String::from_str(s.trim_end()).unwrap()
    }
}

#[macro_export]
macro_rules! print {
    ($($t:tt)*) => {
        fio::STDOUT.with(|cell|{
            use std::io::Write;
            write!(cell.borrow_mut(), $($t)*).unwrap()
        })};
}

#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        fio::STDOUT.with(|cell| {
            use std::io::Write;
            writeln!(cell.borrow_mut(), $($t)*).unwrap()
        })
    };
}

#[macro_export]
macro_rules! flush {
    () => {
        fio::STDOUT.with(|cell| {
            use std::io::Write;
            cell.borrow_mut().flush().unwrap()
        });
    };
}