Codeforces #264 Div2 D. Gargari and Permutations

これは割とあっさり解けた。
http://codeforces.com/contest/463/problem/D

問題

1～NのPermutationとなっているK個の数列が与えられる。
K個すべての数列の部分列となる最長部分列の要素数を答えよ。

解法

K個の数列をそれぞれ見ると、「この数字はこの数字の後に来てはいけない」というのがわかる。
この手順はO(K*N^2)。

あとはDFS+DPで「今の数字を先頭にした際の最長列」を求めるだけ。これはO(N^2)。

「この数字はこの数字の後に来てはいけない」関係がループすることはあっても、「この数字はこの数字の後に来てもよい」がループすることはないので、閉路は気にしなくてよい。

int N,K;
int mat[1001][1001],A[1001];
int memo[1001];

int dfs(int cur){
	int i;
	if(memo[cur]>=0) return memo[cur];
	memo[cur]=1;
	FOR(i,N) if(mat[cur][i]) memo[cur]=max(memo[cur],1+dfs(i));
	return memo[cur];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(y,N) FOR(x,N) mat[x][y]=1;
	FOR(y,N) mat[y][y]=0;
	FOR(j,K) {
		FOR(i,N) cin>>A[i],A[i]--;
		FOR(x,N) for(y=x+1;y<N;y++) mat[A[y]][A[x]]=0;
	}
	
	MINUS(memo);
	int ma=0;
	FOR(i,N) ma=max(ma,dfs(i));
	cout << ma <<endl;
}

まとめ

わかってしまえばあっさりの割と面白い問題。