kmjp's blog

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

TopCoder SRM 663 Div1 Medium ChangingChange

解けはしたけど、色々反省点があった。
http://community.topcoder.com/stat?c=problem_statement&pm=13847

問題

プレイヤーは1~D円の価値の貨幣を幾つか持っている。
同じ価値の貨幣も複数あり得るが、それらは別物と見なされる。
ここで、これらの貨幣の部分集合を取った場合、その合計価値がi円になるような組み合わせ数W[i]がi=0~Dに対し与えられる。

この状態に対し、以下のクエリに答えよ。

  • 手持ちの貨幣のうち、V[j]円のものがN[j]個減った場合、合計価値がD円になる部分集合の組み合わせ数を求める。

なお、W[i]及び答えの値はP=(10^9+7)の剰余を答えること。

解法

パッと見で頭に思い浮かぶのは戻すDPである。
yukicoder : No.155 生放送とBGM - kmjp's blog

ただ、今回は減らすものが1個ではなくN[j]個なので戻すDPをそのまま適用は出来ない。
解法としては以下の方法がある。

進むDP解法

こちらは自分の解法。

ある価値の貨幣がP個増減しても、答えに変更はない。
なぜならある金額の部分集合を作る際にa円の貨幣をb個中c個選ぶとして、 {}_b C_c \equiv {}_{b+P} C_c (mod P)となるためである。
よって、N[j]個減るのではなく、(P-N[j])個増えると考えると、単純な進むDPに持って行ける。

すなわち、W[D-k*V[j]]円の状態で、さらに(P-N[j])個の追加貨幣中k個を追加するとD円を作れるので、解は \sum_k W[D-k*V_j] * {}_{P-N_j} C_kとなる。

戻すDP解法

こちらはEditorialの解法

W[i]を多項式の係数とし、 f(x)= \sum_{i=0}^D W_i*x^iとなる多項式を考える。
a円の貨幣を1枚追加するということは、DPの手順を考えるとf(x)に(1+x^a)を掛算することに等しい。
逆にa円の貨幣を1枚減らすということは、f(x)を(1+x^a)で割ることに相当する。
 \frac{1}{1+x^a} = 1-x^a+x^{2a}+x^{3a}-x^{4a}+...なので、割り算と言っても実際は掛算で処理できる。
よって、 f(x)*(\frac{1}{1+x^{V_j}})^{N_j}を求めてx^Dの係数を答えればよい。

 (\frac{1}{1+x^{V_j}})^{N_j}における x^{a*V_j}の係数は (-1)^a * {}_{N_j} H_aと正負が交互に来る以外は単なる重複あり組み合わせで計算できる。

以下の解法は前者の進むDP。

ll mo=1000000007;

ll modpow(ll a, ll n) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll rev[2020];
class ChangingChange {
	public:
	int D;
	vector <int> countWays(vector <int> ways, vector <int> valueRemoved, vector <int> numRemoved) {
		int D=ways.size()-1;
		int i,x,y;
		for(i=1;i<=2000;i++) rev[i]=modpow(i,mo-2);
		
		vector<int> R;
		FOR(i,valueRemoved.size()) {
			ll v=valueRemoved[i],nn=mo-numRemoved[i];
			if(nn<2000) nn+=mo;
			ll res=0;
			ll tr=1;
			for(x=0;x*v<=D;x++) {
				if(x) tr=tr*(nn+1-x)%mo*rev[x]%mo;
				(res += tr*ways[D-x*v])%=mo;
			}
			R.push_back((res+mo)%mo);
		}
		return R;
	}
}

解法

最初余分なコードを他に書いていたため、TLE対策でresubmitしたのが裏目に出た。