TopCoder SRM 750 Div1 Hard PurpleSubsequences

これは900-950ptでもいい気がするが。
https://community.topcoder.com/stat?c=problem_statement&pm=15306

問題

N要素の1～20からなる数列Aのsubsequenceのうち、以下の条件を満たすものは何通りか。
なお、抜き出す位置が異なっても、結果得られるsubsequenceが等しいものは同一とみなす。

• subsequence中に含まれるLIS長がL以上

解法

distinctなsubsequenceを数える問題なので、基本的には「現在の列に新たな値を末尾に追加するとき、最寄の位置にある要素を選ぶ」という定番テクを用いる。
状態としては、LIS計算の上で用いる昇順列を用いよう。

Aの最大値が20で、Lが6なので、LIS長がLに到達していない場合、途中経過となる昇順列の組み合わせは高々C(20,5)+C(20,4)+C(20,3)+C(20,2)+C(20,1)+C(20,0)で20000通りない。
よってこれらをの状態を全探索しても間に合う。
貪欲に1～20を現在のsubsequenceに追加しながら、昇順列の状態変化を考えてDPすればよい。

int nex[65][25];
vector<vector<int>> V[6];
map<vector<int>,int> id;
ll dp[62][20200];

class PurpleSubsequences {
	public:
	long long count(vector <int> A, int L) {
		int N=A.size();
		int i,j,x;
		
		
		V[0].clear();
		V[0].push_back(vector<int>());
		FOR(i,L-1) {
			V[i+1].clear();
			FORR(v,V[i]) {
				for(j=(v.empty()?1:min(20,v.back()+1));j<=20;j++) {
					v.push_back(j);
					V[i+1].push_back(v);
					v.pop_back();
				}
			}
		}
		sort(ALL(V[L-1]));
		
		id.clear();
		FOR(i,V[L-1].size()) id[V[L-1][i]]=i;
		
		FOR(i,22) nex[N+1][i]=N+1;
		for(i=N;i>=0;i--) {
			FOR(j,21) nex[i][j]=nex[i+1][j];
			if(i<N) nex[i][A[i]]=i+1;
		}
		
		ZERO(dp);
		int T=V[L-1].size();
		dp[0][T-1]=1;
		ll ret=0;
		int x;
		
		FOR(i,N+1) {
			FOR(j,T) if(dp[i][j]) {
				for(x=1;x<=20;x++) if(nex[i][x]<=N) {
					vector<int> CV=V[L-1][j];
					int y=lower_bound(ALL(CV),x)-CV.begin();
					
					if(y==L-1) {
						dp[nex[i][x]][T]+=dp[i][j];
					}
					else {
						CV[y]=x;
						dp[nex[i][x]][id[CV]]+=dp[i][j];
					}
				}
			}
			ret+=dp[i][T];
			for(x=1;x<=20;x++) dp[nex[i][x]][T]+=dp[i][T];
		}
		
		
		return ret;
		
		
	}
}

まとめ

状態数が意外に小さいってこと以外は、余りややこしい点はなさそう。