TopCoder SRM 588 Div1 Medium KeyDungeonDiv1

さてMedium。450ptと油断させておいて、何気に撃沈率が高い。
http://community.topcoder.com/stat?c=problem_statement&pm=12714

問題

N個のドアがあり、i番目のドアを開けるのにdoorR[i]個の赤または白の鍵と、doorG[i]個の緑または白の鍵を消費する。
ドアを開けると、赤・緑・白の鍵をそれぞれroomR[i],roomG[i],roomW[i]個手に入れることができる。
鍵の初期状態を与えられたとき、各ドアを開けて到達できる最大鍵数を答えよ。

解法

N<=12ということでbitDPを使うことがまず思いつく。
あるA個のドアを開けた状態にたどり着くには、A通りの(A-1)個のドアを開けた状態から、できるだけ白鍵を使わないように最後の１個のドアを開けられる方法を選べばよい。

ここで最初、「持てる白鍵が最多な状態がベスト」として早々にsubmitした。
これでpretestは通るのだが、後でこれではだめなことに気づいた。(同じアプローチの人は他にもいて撃沈したようだ)
たとえば、あるA個のドアを開ける順番によって得られる鍵数のバリエーションとして、(R,G,W)=(3,9,3)と(9,4,2)では白い鍵は前者のほうが多いが、その後赤鍵が多数求められる展開がある場合には前者では対応できない。

結局、bitDPを使うこと自体は正しいが、もてる鍵パターンは全部列挙しておく必要がある。
ここで、各鍵は最大130個であること、そしてA個のドアを開けた状態の総鍵数は計算で求められることから、状態をDP[開けたドアのbitmask][赤い鍵の個数]=緑の鍵の個数、とすればよい。
白い鍵の数は(総鍵数-赤鍵数-緑鍵鍵)からわかるので、保持する必要はない。
また、赤い鍵の数は固定なら、緑の鍵は少ないほうが(その分オールマイティーな白い鍵を持っているということなので)よい。

	int maxKeys (vector <int> DR, vector <int> DG, vector <int> RR, vector <int> RG, vector <int> RW, vector <int> K) {
		int N=DR.size();
		
		int mask,bi,i;
		FOR(mask,1<<N) {
			FOR(i,131) nr[mask][i]=1000;
		}
		nr[0][K[0]]=K[1];
		int ma=tot[0]=K[0]+K[1]+K[2];
		FOR(mask,1<<N) {
			if(mask==0) continue;
			tot[mask]=K[0]+K[1]+K[2];
			FOR(bi,N) if(mask & (1<<bi)) tot[mask]+=RR[bi]+RG[bi]+RW[bi]-DR[bi]-DG[bi];
			
			FOR(bi,N) {
				if((mask & (1<<bi))==0) continue;
				int lm=mask ^ (1<<bi);

				FOR(i,131) {
					if(nr[lm][i]>=1000) continue;
					int rw = max(0,DR[bi]-i);
					int gw = max(0,DG[bi]-nr[lm][i]);
					if(i+rw >= DR[bi] && nr[lm][i]+gw>=DG[bi] && rw+gw <= tot[lm]-i-nr[lm][i]) {
						int nnr=i-(DR[bi]-rw)+RR[bi];
						int nng=nr[lm][i]-(DG[bi]-gw)+RG[bi];
						if(nng<nr[mask][nnr]) {
							nr[mask][nnr]=nng;
							ma=max(ma,tot[mask]);
						}
					}
					
				}
				
			}
		}
		return ma;
	}

まとめ

「白鍵が最多」という考え方でpretestが通るのが曲者。
また、状態数として鍵１個分だけ配列を持てば十分なことに気づくのが重要だね。
幸い、submit後に「鍵の数の制限厳しすぎない？」と思って考え直し、終了間際にresubmitした。

せっかくここまで気づいたのに、本番鍵の総数を120個と勘違いしてミスした…。