本番はそもそも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); } };
まとめ
シンプルな問題だけど、解法すごい面白いな。
