kmjp's blog

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

TopCoder SRM 758 Div1 Hard PrettyLiar

これ方針は合ってたので最後まで解ききれなかったの残念。
https://community.topcoder.com/stat?c=problem_statement&pm=15405

問題

整数Sと、2つのN要素の整数列A,Bが与えられる。A,Bの総和はS以上である。
SからA[0],B[0],A[1],B[1],....と順に値を引いていき、Sが0以下になったところで止める、ということを考える。

A,Bそれぞれ並び順を変えることを考えると、(N!)^2通りの並べ替え方がある。
この時、B側の値を引いた段階でS以下になる、という状態は何通りあるか。

解法

(並べ替え前の)値B[i]が、並べ替え後(0-originで)j番目に来た場合に条件を満たすのは何通りか、(i,j)を列挙することを考える。

その場合、Aから選ぶ先頭(j+1)個と、Bから選ぶ先頭(j)個の和が、S-B[i]以上S-1以下であればB[i]を(j+1)回目に引いた時点でSが0以下になる。
よってこの組み合わせを列挙しよう。
必要なのは和だけなので、並び順はあとで考えるとしてまずは以下をDPで求める。

f(n,k) := Aからn個選択して和がkとなる組み合わせ数
g(n,k) := Bからn個選択して和がkとなる組み合わせ数

ここで、
g'(n,k) := Bから「元のB[i]以外で」n個選択して和がkとなる組み合わせ数
とするものを考えよう。
すると \displaystyle \sum_{S-B_i \le k+l < S-1} f(j+1,k)\times g'(j,l)が求まれば、Aの先頭(j+1)個およびBの先頭(j)個の組み合わせが列挙できるので、そこに (j+1)! \times j! \times (N-(j+1))! \times (N-(j+1))!を掛ければ並び順も含めた組み合わせが求められる。
総和の式は、g'(j,l)についてはlの累積和を取っておけば、kだけ総当たりすればよくなる。

あとはg'(n,k)だが、これはいわゆる戻すDPである。
g(n,k) = g'(n,k) + g'(n-1, k-B[i])なので、g'(n,k) = g(n,k)-g'(n-1,k-B[i])となる。
g'(0,l)はl=0なら1、それ以外0で明らかなので、nの小さい順にg'(n,k)を確定させていくことができる。

ll X[101][10101];
ll Y[101][10101];
ll Z[101][10101];
ll W[10101],SS[10101];
ll mo=1000000007;
ll fact[201];

class PrettyLiar {
	public:
	int count(int S, vector <int> A, vector <int> B) {
		ZERO(X);
		ZERO(Y);
		ZERO(Z);
		int N=A.size();
		
		int i,a,b,j,x,y;
		fact[0]=1;
		for(i=1;i<=200;i++) fact[i]=fact[i-1]*i%mo;
		X[0][0]=Y[0][0]=Z[0][0]=1;
		FOR(i,N) {
			for(a=i;a>=0;a--) FOR(b,a*100+1) {
				X[a+1][b+A[i]]+=X[a][b];
				if(X[a+1][b+A[i]]>=mo) X[a+1][b+A[i]]-=mo;
				Y[a+1][b+B[i]]+=Y[a][b];
				if(Y[a+1][b+B[i]]>=mo) Y[a+1][b+B[i]]-=mo;
			}
		}
		ll ret=0;
		FOR(i,N) {
			int b=B[i];
			for(x=1;x<=N;x++) {
				ll pat=fact[x]%mo*fact[N-x]%mo*fact[x-1]%mo*fact[N-x]%mo;
				FOR(j,x*100+1) {
					Z[x][j]=Y[x][j];
					if(j>=b) {
						Z[x][j]+=mo-Z[x-1][j-b];
						if(Z[x][j]>=mo) Z[x][j]-=mo;
					}
					W[j]=Z[x-1][j];
					if(j) W[j]+=W[j-1];
					if(W[j]>=mo) W[j]-=mo;
				}
				FOR(j,x*100+1) if(X[x][j]) {
					int L=S-b-j,R=min(x*100,S-j-1);
					if(R<0 || R<L) continue;
					ll sum=W[R];
					if(L>0) sum+=mo-W[L-1];
					if(sum) ret+=X[x][j]*sum%mo*pat%mo;
				}
				ret%=mo;
			}
		}
		return ret;
	}
}

まとめ

戻すDPを使うことまでは到達したのに、そのやり方を間違えてアウトだった。
もったいないけど勉強にはなったか。