2035-It Prefokery Pio

問題概要

文字列Aの部分列のうち最長の回文となるものを求めよ．

解法

文字列とその反転文字列に対しLCSのアルゴリズムを適用する．
最長共通部分列が回文ならば明らかに，それは最長回文になり，そして最長共通部分列は必ず回文になる．

以下簡単な証明
対象文字列をA，対象文字列を反転したものをRev(A)とする．
AとRev(A)の部分列をTとすると，Rev(A)とRev(Rev(A))=Aの部分列にRev(T)は含まれる．
よって，Tが最長共通部分列の時に回文では無かったと過程すると，それより長い部分列が考えつくので矛盾する．
ゆえにTが最長共通部分列の時は回文となる．

実装(C++)

#include <algorithm>
#include <vector>
#include <iostream>
#include <cstring>
using namespace std;

typedef long long int lli;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define rep(i,s,x) for(int i=s;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
string a,b;
vector<int> lcs(const vector<int>& a, const vector<int>& b) {
  const int n = a.size(), m = b.size();
  vector< vector<int> > X(n+1, vector<int>(m+1));
  vector< vector<int> > Y(n+1, vector<int>(m+1));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (a[i] == b[j]) {
        X[i+1][j+1] = X[i][j] + 1;
        Y[i+1][j+1] = 0;
      } else if (X[i+1][j] < X[i][j+1]) {
        X[i+1][j+1] = X[i][j+1];
        Y[i+1][j+1] = +1;
      } else {
        X[i+1][j+1] = X[i+1][j];
        Y[i+1][j+1] = -1;
      }
    }
  }
  vector<int> c;
  for (int i = n, j = m; i > 0 && j > 0; ) {
    if      (Y[i][j] > 0) --i;
    else if (Y[i][j] < 0) --j;
    else { c.push_back(a[i-1]); --i; --j; }
  }
  reverse(c.begin(), c.end());
  return c;
}
int main(){
	for(;cin>>a;){
		a;
		int n=a.size();
		vector<int> k1,k2;
		REP(i,n)k1.push_back(a[i]);
		REP(i,n)k2.push_back(a[n-i-1]);
		vector<int> t=lcs(k1,k2);
		REP(i,t.size()){
			cout<<(char)t[i];
		}
		cout<<endl;
	}
}