結果

問題 No.3429 Palindromic Path (Hard)
コンテスト
ユーザー 00 Sakuda
提出日時 2026-02-04 01:13:02
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 404 ms / 2,000 ms
コード長 1,352 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,664 ms
コンパイル使用メモリ 217,604 KB
実行使用メモリ 36,352 KB
最終ジャッジ日時 2026-02-04 01:13:09
合計ジャッジ時間 4,987 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <queue>
#include <deque>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
using ll = long long;
#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;
int main() {
	int N;cin >> N;
	vector<string> S(N);
	for (int i = 0;i < N;i++) cin >> S[i];
	vector<vector<vector<mint>>> dp(N + 1, vector<vector<mint>>(N, vector<mint>(N, 0)));
	
	if (S[0][0] == S[N - 1][N - 1]) dp[0][0][N - 1] = 1;
	vector<vector<int>> df1 = {{0, 1}, {1, 0}};
	vector<vector<int>> df2 = {{-1, 0}, {0, -1}};
	for (int c = 0;c < N;c++) for (int x1 = 0;x1 < N;x1++) for (int x2 = 0;x2 < N;x2++) {
		if (dp[c][x1][x2].val() == 0) continue;
		if (x1 > c) continue;
		int y1 = c - x1;
		int d = N - 1 - x2;
		if (d > c) continue;
		int nd = c - d;
		int y2 = N - 1 - nd;
		for (auto d1 : df1) for (auto d2 : df2) {
			int nx1 = x1 + d1[0];
			int ny1 = y1 + d1[1];

			int nx2 = x2 + d2[0];
			int ny2 = y2 + d2[1];
			if (nx1 >= N or ny1 >= N) continue;
			if (nx2 < 0 or ny2 < 0) continue;
			if (S[nx1][ny1] != S[nx2][ny2]) continue;
			dp[c + 1][nx1][nx2] += dp[c][x1][x2];	
		}
	}
	
	mint res = 0;
	for (int x = 0;x < N;x++) {
		int y = N - 1 - x;
		res += dp[N - 1][x][x];
	}
	cout << res.val() << endl;
}
0