kmjp's blog

競技プログラミング参加記です

MemSQL start[c]up Round 2 : B. Palindrome

これはまた変な問題だな。
http://codeforces.com/contest/335/problem/B

問題

アルファベットの小文字で構成される文字列Sが与えられる。
Sの部分文字列で、100文字の回文があればそれを答えよ。
100文字未満の回文しかなければ、最長の回文を答えよ。

解法

S中に同じアルファベットが100個以上あれば、それを答えて終わり。
そうでない場合、Sの長さは26*99以下である。

後は最長の回文判定は、Sとそれを反転させた部分文字列で最長共通部分文字列を求めればよいので、O(length(S))で処理できる。

string S,SR;
int oc[26],N;
int dp[2601][2601],dir[2601][2601];

int dpdp(int x,int y) {
	if(x>=N || y<0) return 0;
	if(dp[x][y]==-1) {
		if(S[x]==S[y]) {
			dir[x][y]=0;
			dp[x][y]=1+dpdp(x+1,y-1);
		}
		else {
			if(dpdp(x,y-1)>=dpdp(x+1,y)) {
				dir[x][y]=1;
				dp[x][y]=dpdp(x,y-1);
			}
			else {
				dir[x][y]=2;
				dp[x][y]=dpdp(x+1,y);
			}
		}
	}
	return dp[x][y];
}

void solve() {
	int f,r,i,j,k,l,x,y;
	
	cin>>S;
	N=S.size();
	FOR(i,N) oc[S[i]-'a']++;
	FOR(i,26) {
		if(oc[i]>=100) {
			FOR(j,100) _P("%c",'a'+i);
			_P("\n");
			return;
		}
	}
	
	reverse(SR.begin(),SR.end());
	FOR(y,2600) FOR(x,2600) dp[y][x]=-1;
	FOR(x,N) dpdp(x,x);
	FOR(x,N-1) dpdp(x+1,x);
	
	int ml=0,ty=-1,tx=-1;
	FOR(y,N) FOR(x,N) {
		if(dp[x][y]==-1) continue;
		l = dp[x][y]*2-(x==y);
		if(l>100) l=100-(x==y);
		if(ml<l) ml=l,ty=y,tx=x;
	}
	
	string R="";
	while(tx<N && ty>=0) {
		if(dir[tx][ty]==0) {
			if(tx==ty) R=S[tx];
			else R=S[ty]+R+S[tx];
			tx++;
			ty--;
			if(R.size()>=99) break;
			
		}
		else if(dir[tx][ty]==1) ty--;
		else tx++;
	}
	cout << R << endl;
}

まとめ

復元付DP、面倒で苦手…。