結果

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

ソースコード

diff #
raw source code 

use proconio::{fastout, input, marker::Bytes};

#[fastout]
fn main() {
    input! {
        n: usize,
        c: [Bytes; n],
    }

    println!("{}", output(solve(c)))
}

fn solve(c: Vec<Vec<u8>>) -> u32 {
    let n = c.len();
    let mut dp = [vec![vec![0; n]; n], vec![vec![0; n]; n]];
    if c[0][0] == c[n - 1][n - 1] {
        dp[0][0][n - 1] = 1;
    }
    for i in 0..(n - 1) {
        for j in 0..=(i + 1) {
            dp[(i & 1) ^ 1][j].fill(0);
        }
        
        for j in 0..=i {
            for k in (n - 1 - i)..=(n - 1) {
                if c[j][i - j + 1] == c[k][(n - 1) - i + ((n - 1) - k) - 1] {
                    dp[(i & 1) ^ 1][j][k] = (dp[(i & 1) ^ 1][j][k] + dp[i & 1][j][k]) % 998244353;
                }
                if c[j + 1][i - j] == c[k][(n - 1) - i + ((n - 1) - k) - 1] {
                    dp[(i & 1) ^ 1][j + 1][k] = (dp[(i & 1) ^ 1][j + 1][k] + dp[i & 1][j][k]) % 998244353;
                }
                if c[j][i - j + 1] == c[k - 1][(n - 1) - i + ((n - 1) - k)] {
                    dp[(i & 1) ^ 1][j][k - 1] = (dp[(i & 1) ^ 1][j][k - 1] + dp[i & 1][j][k]) % 998244353;
                }
                if c[j + 1][i - j] == c[k - 1][(n - 1) - i + ((n - 1) - k)] {
                    dp[(i & 1) ^ 1][j + 1][k - 1] = (dp[(i & 1) ^ 1][j + 1][k - 1] + dp[i & 1][j][k]) % 998244353;
                }
            }
        }
    }
    (0..=(n - 1))
        .map(|i| dp[(n - 1) & 1][i][i])
        .fold(0, |acc, x| (acc + x) % 998244353)
}

fn output(ans: u32) -> u32 {
    ans
}
0