yukicoder : No.3429 Palindromic Path (Hard)

こちらはすんなり。
https://yukicoder.me/problems/no/3429

問題

N*Nのグリッドがあり、各セルには１文字が置かれている。
左上マスから右下マスに、右または下の隣接マスをたどるパスを通ったとき、置かれた文字をつなげた文字列が回文となるものは何通りか。

解法

パスの真ん中、すなわち左下から右上の対角線上のセルから始め、両端を左上。右下に伸ばしていこう。

dp(i,a,b) := パスの両端が左下から右上の対角線上のセルから見て左上にiマス、右下にiマス移動した場所のうち、それぞれ行番号がa番目、b番目であるような、回文を成すパスの数
とし、dp(0,x,x)からdp(N-1,0,N-1)を求めて行こう。

int N;
string S[402];

ll from[202][202];
ll to[202][202];
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,N) {
		cin>>s;
		FOR(x,N) S[y+x].push_back(s[x]);
	}
	
	FOR(y,N) from[y][y]=1;
	for(i=1;i<=N-1;i++) {
		ZERO(to);
		FOR(x,N) FOR(y,N) if(from[x][y]) {
			int x2,y2;
			for(x2=max(0,x-1);x2<=min(x,(int)S[N-1-i].size()-1);x2++) for(y2=max(0,y-1);y2<=min(y,(int)S[N-1+i].size()-1);y2++) {
				if(S[N-1-i][x2]==S[N-1+i][y2]) (to[x2][y2]+=from[x][y])%=mo;
			}
		}
		
		swap(from,to);
	}
	cout<<from[0][0]<<endl;
	
	
}

まとめ

どこかで同じ問題見てそう。