Eに手こずってちょっと順位が下がった。
https://csacademy.com/contest/round-57/task/distinct-palindromes/
問題
文字列Sが与えられる。
Sの部分文字列のうち、uniqueな回文は何通りあるか。
解法
uniqueな部分列の数え上げ問題はO(|S|w) (wは文字種類数)で解ける典型DP問題。
S[i]=S[j]のとき、以下を考える。
f(i.j) := S[i],S[j]を両端とする部分文字列のうちuniqueな回文の数
ある文字cについて、S[i]の後ろにある最も近い物をS[x]、S[j]の前にある最も近い物をS[y]とすると
f(i,j) += 1 + f(x,y)
となるので、これを用いて計算していこう。(1足すは中央が1文字の場合)
最初にダミーの文字を先頭と末尾に追加しておくと、f(0,|S|-1)が解となるのでわかりやすい。
ll memo[1010][1010]; ll mo=1000000007; int ri[1010][27]; int le[1010][27]; int N; string S; ll hoge(int L,int R) { if(memo[L][R]>=0) return memo[L][R]; ll ret=1; int i; FOR(i,26) if(ri[L][i]<R && le[R][i]>L) { ret++; if(ri[L][i]<le[R][i]) ret+=hoge(ri[L][i],le[R][i]); } return memo[L][R]=ret%mo; } void solve() { int i,j,k,l,r,x,y; string s; cin>>S; S=(char)('a'+26)+S+(char)('a'+26); N=S.size(); MINUS(memo); FORR(c,S) c-='a'; FOR(i,27) ri[N-1][i]=N, le[0][i]=-1; for(i=N-2;i>=0;i--) { FOR(j,27) { if(S[i+1]==j) ri[i][j]=i+1; else ri[i][j]=ri[i+1][j]; } } for(i=1;i<N;i++) { FOR(j,27) { if(S[i-1]==j) le[i][j]=i-1; else le[i][j]=le[i-1][j]; } } cout<<(hoge(0,N-1)+mo-1)%mo<<endl; }
まとめ
部分列の数え上げな時点で解法は割とすぐ思いつけた。