結果

問題 No.3428 Palindromic Path (Easy)
コンテスト
ユーザー mentos_grape
提出日時 2026-01-11 14:18:37
言語 Python3
(3.14.2 + numpy 2.4.0 + scipy 1.16.3)
結果
AC  
実行時間 137 ms / 2,000 ms
コード長 1,515 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 496 ms
コンパイル使用メモリ 20,804 KB
実行使用メモリ 15,360 KB
最終ジャッジ日時 2026-01-11 14:18:44
合計ジャッジ時間 2,358 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

sys.setrecursionlimit(2000)

def solve():
    # 入力の読み込み
    try:
        input = sys.stdin.read
        data = input().split()
    except Exception:
        return

    if not data:
        return

    N = int(data[0])
    grid = data[1:]

    MOD = 998244353

    if grid[0][0] != grid[N-1][N-1]:
        print(0)
        return

 
    dp = {}
    dp[(0, N-1)] = 1

    # ステップ数 step を 0 から N-2 まで回す
    for step in range(N - 1):
        new_dp = {}
        
        for (r1, r2), count in dp.items():
            c1 = step - r1
            c2 = (2 * N - 2 - step) - r2


            next_p1 = []
            if r1 + 1 < N: # 下
                next_p1.append((r1 + 1, c1))
            if c1 + 1 < N: # 右
                next_p1.append((r1, c1 + 1))
            

            next_p2 = []
            if r2 - 1 >= 0: # 上
                next_p2.append((r2 - 1, c2))
            if c2 - 1 >= 0: # 左
                next_p2.append((r2, c2 - 1))

            # 全ての移動の組み合わせを試す
            for nr1, nc1 in next_p1:
                for nr2, nc2 in next_p2:
                    if grid[nr1][nc1] == grid[nr2][nc2]:
                        new_key = (nr1, nr2)
                        new_dp[new_key] = (new_dp.get(new_key, 0) + count) % MOD
        
        dp = new_dp


    ans = 0
    for (r1, r2), count in dp.items():
        if r1 == r2:
            ans = (ans + count) % MOD

    print(ans)

if __name__ == '__main__':
    solve()
0