結果

問題 No.3429 Palindromic Path (Hard)
コンテスト
ユーザー ID 21712
提出日時 2026-04-24 01:22:43
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 233 ms / 2,000 ms
コード長 1,169 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 11,381 ms
コンパイル使用メモリ 277,248 KB
実行使用メモリ 7,040 KB
最終ジャッジ日時 2026-04-24 01:22:58
合計ジャッジ時間 12,218 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"

const M = 998244353

func main() {
	var n int
	Scan(&n)
	
	grid := make([][]byte, n)
	for i := range grid {
		var s string
		Scan(&s)
		grid[i] = []byte(s)
	}
	
	pack := func(x1,y1,x2,y2 int) int {
		return (x1 << 0) | (y1 << 8) | (x2 << 16) | (y2 << 24)
	}
	unpack := func(p int) (x1,y1,x2,y2 int) {
		x1 = (p >> 0) & 0xFF
		y1 = (p >> 8) & 0xFF
		x2 = (p >> 16) & 0xFF
		y2 = (p >> 24) & 0xFF
		return
	}
	
	update := func(m map[int]int, x1,y1,x2,y2,c int) {
		if 0 <= x1 && x1 < n && 0 <= y1 && y1 < n {
			if 0 <= x2 && x2 < n && 0 <= y2 && y2 < n {
				if grid[y1][x1] == grid[y2][x2] {
					p := pack(x1, y1, x2, y2)
					m[p] = (m[p] + c) % M
				}
			}
		}
	}
	
	
	tmp1 := map[int]int{}
	for i := 0; i < n; i++ {
		x, y := i, (n-1)-i
		p := pack(x,y,x,y)
		tmp1[p] = 1
	}
	
	for i := 1; i < n; i++ {
		tmp2 := map[int]int{}
		for p, c := range tmp1 {
			x1,y1,x2,y2 := unpack(p)
			update(tmp2,x1-1,y1,x2+1,y2,c)
			update(tmp2,x1-1,y1,x2,y2+1,c)
			update(tmp2,x1,y1-1,x2+1,y2,c)
			update(tmp2,x1,y1-1,x2,y2+1,c)
		}
		tmp1 = tmp2
	}
	
	if len(tmp1) == 0 {
		Println(0)
	} else {
		for _, c := range tmp1 {
			Println(c)
		}
	}
}
0