読者です 読者をやめる 読者になる 読者になる

kmjp's blog

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

TopCoder SRM 592 Div1 Medium LittleElephantAndPermutationDiv1

本番はそもそもEasyでテンパってまともに見られなかったし、本番ではこれは思いつかないなーと思った問題。
まだEditorialは出ていないが、Forumの解説を見て解いてみた。
http://community.topcoder.com/stat?c=problem_statement&pm=12735

問題

数Nが与えられるので、1~Nのpermutationとなる2つの数列A,Bを考える。
magic(A,B) = max(A[0],B[0]) + max(A[1],B[1]) + ... + max(A[N-1],B[N-1])
で関数magicを定義した場合、magic(A,B)>=KとなるA・Bの組み合わせ数を答えよ。

解法

AとBの要素をを1個ずつ格納できるスロットがN個あるとする。
数値の大きい順、すなわちNから順にスロットに詰める。
大きい順に詰めるので、AとBで先に数値を埋めたらその数はmagic(A,B)の計算に寄与する。

あとは[AもBも埋まってないスロット数][Aだけ埋まったスロット数][Bだけ埋まったスロット数][AもBも埋まったスロット数]に関してDPを行う。
実際は処理し終わった数と、[AもBも埋まってないスロット数]だけわかれば他のスロット数は計算で求められるので、[AもBも埋まってないスロット数][ここまでのmagicの値]でDPの状態を持つ。

ここでAおよびBの数jをスロットに埋める際、以下の埋め方が考えられる。

  • [AもBも埋まってないスロット]を1個選びにAもBも数jを埋める。[AもBも埋まってないスロット]が1個[AもBも埋まったスロット]になり、magicの値がj増える。
  • [AもBも埋まってないスロット]を2つ選び、AもBも数jを埋める。[AもBも埋まってないスロット]が2個減り、[Aだけ埋まったスロット][Bだけ埋まったスロット]が1個ずつ増え、magicの値が2*j増える。
  • [AもBも埋まってないスロット]を1個選んでにAから数jを埋め、[Aだけ埋まったスロット]を1個選んでにBから数jを埋める。[AもBも埋まってないスロット]が[Aだけ埋まったスロット]になり、[Aだけ埋まったスロット]が[AもBも埋まったスロット]になり、magicの値がj増える。
  • 上記をAとB逆にしたもの
  • [Bだけ埋まったスロット]と[Aだけ埋まったスロット]を1つずつ選び、AとBから数jを埋める。両スロットは[AもBも埋まったスロット]になるが、magicの値は変化しない。

上にも書いた通り、実際は[AもBも埋まってないスロット数]だけ管理すればよいのでコードは短い。
あとは最後にmagicの値がK以上のものを数えればよい。
数がN個、途中までのmagicの値がN^2、[AもBも埋まってないスロット数]がNでO(N^4)で処理できる。

class LittleElephantAndPermutationDiv1 {
	public:
	int getNumber(int N, int K) {
		int i,s2,s1,tot=0,k;
		
		ZERO(dpdp);
		dpdp[0][N][0]=1;
		FOR(i,N) {
			int cur=i%2,tar=(i+1)%2;
			ZERO(dpdp[tar]);
			int j=N-i;
			FOR(k,tot+1) {
				for(s2=0;s2<=N;s2++) {
					if(dpdp[cur][s2][k]==0) continue;
					int s0=2*i-(N-s2);
					int s1=N-s2-s0;
					if(s0<0 || s0>N || s1<0 || s1>N) continue;
					
					if(s2>=1)          dpdp[tar][s2-1][k+j]   = (dpdp[tar][s2-1][k+j]   + s2*dpdp[cur][s2][k]) % mo; // s2
					if(s2>=2)          dpdp[tar][s2-2][k+2*j] = (dpdp[tar][s2-2][k+2*j] + s2*(s2-1)*dpdp[cur][s2][k]) % mo; // s2,s2
					if(s2>=1 && s1>=1) dpdp[tar][s2-1][k+j]   = (dpdp[tar][s2-1][k+j]   + 2*s2*(s1/2)*dpdp[cur][s2][k]) % mo; // s2,s1
					if(s1>=2)          dpdp[tar][s2][k]       = (dpdp[tar][s2][k]       + (s1/2)*(s1/2)*dpdp[cur][s2][k]) % mo; // s1,s1
				}
			}
			tot=min(tot+2*j,2500);
		}
		
		ll r=0;
		for(i=K;i<=2500;i++) r+=dpdp[N%2][0][i];
		return (int)(r%mo);
	}
};

まとめ

シンプルな問題だけど、解法すごい面白いな。

広告を非表示にする