Codeforces #323 Div1 B. Once Again...

ちょっと迷ったけど、無事解けて良かった。
http://codeforces.com/contest/582/problem/B

問題

N要素の数列Aが与えられる。
この数列をT回繰り返した数列から生成できる、単調増加な部分列の最大要素数を求めよ。

解法

Aの要素は高々N通りなので、最初に座標圧縮しておこう。
まず簡単なDPの要領で、元のAに対し F(x,y) := (Aの部分列のうち、最小要素がx以上、最大要素がy以下である単調増加列の最大長)を求める。

ここからは２種類の解法がある。
１つは、Tは非常に大きいがAの取り得る値は小さいことから、T回Aを繰り返した数列のうち、最小(T-N)回分は同じ値だけを抽出する部分があるはずである。
よって、その同じ値を抽出する値を総当たりしながら、残りN回分のAの繰り返しの最長部分列を求める。

もう一つは自分の解法。
F(x,y)から、ダブリングの要領でAを2,4,8,...,2^i回繰り返した場合の最小要素がx以上、最大要素がy以下である単調増加列の最大長が求められる。
あとは整数累乗テクの要領で、(T & (2^i)) != 0となるiに対する結果を連結させ、最終的にT回繰り返した場合の題意を満たす最大長を求める。

int N,T,M;
map<int,int> MM;
int A[3030];
int pat[26][101][101];
int res[26][101][101];

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>N>>T;
	FOR(i,N) cin>>A[i], MM[A[i]]++;
	M=0;
	FORR(r,MM) r.second=M++;
	FOR(i,N) A[i]=MM[A[i]];
	FOR(i,N) FOR(x,A[i]+1) for(y=A[i];y>=x;y--) pat[0][x][A[i]] = max(pat[0][x][A[i]],pat[0][x][y]+1);
	FOR(i,101) FOR(y,M) FOR(x,y) pat[0][x][y] = max(pat[0][x][y],max(pat[0][x+1][y],pat[0][x][y-1]));
	
	FOR(i,25) FOR(y,M) FOR(x,y+1) {
		for(z=x;z<=y;z++) pat[i+1][x][y] = max(pat[i+1][x][y],pat[i][x][z]+pat[i][z][y]);
		if(T&(1<<i)) {
			for(z=x;z<=y;z++) res[i+1][x][y] = max(res[i+1][x][y], res[i][x][z]+pat[i][z][y]);
		}
		else res[i+1][x][y]=res[i][x][y];
	}
	
	cout<<res[25][0][M-1]<<endl;
}

まとめ

最初前者の方法を思いついたけど、それはそれで実装めんどそうなのでダブリングに行った。
最初平方分割しようと思ったけど、ダブリングで正解だったかな？