kmjp's blog

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

TopCoder SRM 585 Div1 Medium LISNumber

SRM

本番、正解に近いところまで行ったものの最後まで詰められなかった。
http://community.topcoder.com/stat?c=problem_statement&pm=12419

問題

1～36番の番号がついたカードがそれぞれ最大36枚ある。
これらの全部のカードを１列に並べたとき、数値が真に単調増加になるような最小の部分列の数をLIS numberとする。

カード枚数が与えられたとき、LIS numberがKとなる並べ方の組み合わせを答えよ。

解法

どう並べるかを考えると難しいので、K個の単調増加数列に数を割り当てていくことを考える。
小さい順にDPで解いていく。

数Aまでの数字を合計P枚並べた段階でLIS numberがYである組み合わせ数をDP[A][Y]とする。
ここにA+1のカードをQ枚追加することを考える。

カードを１枚追加したとき、LIS numberが追加しないのは、すでに部分列の最後尾の次にカードを置いたときである。
それ以外の場所に置くとLIS numberが増加する。

よって、Q枚のうちZ枚をLIS numberが増えない場所、(Q-Z)枚をLIS numberが増える場所に置くとすると、LIS numberが増えない場所をY箇所中Z箇所選択し、それ以外の(Q-Z)枚はLIS numberが増えるP+1-(Y-Z)箇所から(Q-Z)箇所重複ありで選択すればよい。
P[A+1][Y+(Q-Z)] += DP[A][Y] \times {}_Y C_Z \times {}_{P+1-(Y-Z)} H_{Q-Z}

最大でO(N^5)程度かかるが、実際はだいぶ小さ目のO(N^5)なので時間は大丈夫。

ll dpdp[46][1300];
ll mo=1000000007;

ll comb(int P_,int Q_) {
	static const int N_=1300;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	return C_[P_][Q_];
}
ll hcomb(int P_,int Q_) { return comb(P_+Q_-1,Q_);}

class LISNumber {
	int N;
	public:
	int count(vector <int> cardsnum, int K) {
		int i,x,y,z;
		N=cardsnum.size();
		
		ZERO(dpdp);
		dpdp[0][0]=1;
		
		int larger=0,la;
		FOR(x,N) {
			for(y=0;y<=larger;y++) { // cur K
				if(dpdp[x][y]==0) continue;
				for(z=0;z<=y;z++) { // select z
					int lef=cardsnum[x]-z;
					if(lef<0) continue;
					//_P("%lld %d %d (%d %d %d %d):",dpdp[x+1][y+lef],x+1,y+lef,x,y,z,lef);
					dpdp[x+1][y+lef] = (dpdp[x+1][y+lef] + ((dpdp[x][y]*comb(y,z))%mo)*hcomb(larger+1-(y-z),lef)) % mo;
					//_P("%lld \n",dpdp[x+1][y+lef]);
				}
			}
			
			larger+=cardsnum[x];
		}
		
		return (int)(dpdp[N][K]%mo);
	}

};

まとめ

本番は、K個の数列を作ることは思いついたものの、なぜか大きい方から配置した方がいいかと考えてしまいDPを作りきれなかった。
でも前回の600ptの数え上げと言い、割と良い線で考えられるようになってきたのは良い傾向。