TopCoder SRM 658 Div1 Medium Mutalisk、Div2 Medium MutaliskEasy

本番枝刈り不十分で時間切れ。
http://community.topcoder.com/stat?c=problem_statement&pm=13761
http://community.topcoder.com/stat?c=problem_statement&pm=13782

問題

N個の基地があり、各耐久力はX[i]である。
1回のターンでプレイヤーは最大３個の異なる基地に攻撃ができ、それぞれ耐久力を1,3,9減少させることができる。

全部の基地の耐久力を0以下にするのにかかる最小ターン数を求めよ。
Nの上限がはDiv1 Mediumで20、Div2 Mediumで3である。

解法

Div2 Mediumは基地が3つなので、1回の攻撃でどの基地の耐久力を9,3,1減少させるかのパターンは6通りしかない。
また、最大ケースでも総攻撃回数は15回以下である。

よって、6通りのうち5通りの攻撃パターンの実行回数を0～15回で総当たりし、残った耐久力を残りの攻撃パターンで削りきることを考え、総攻撃回数の最小値を求めればよい。

Div1 MediumはNが20なのでこれでは不可。
色々な方法でDPができるだろうが、自分は以下のDPを行った。

状態としてdp[基地番号][9の攻撃回数][3の攻撃回数][1の攻撃回数]=1つの基地を破壊するのにかかるターンの最大値 を持ち、これを順次更新していく。

X[i]は1～60と小さいので、まずDPで1～60を削りきるときの9,3,1の攻撃回数を列挙する。
基地毎のDPフェーズでは、[9の攻撃回数][3の攻撃回数][1の攻撃回数]を全通り試すとTLEするのでより攻撃回数の少ないパターンが存在するなら、多い方のパターンは省略するようちょっとした枝刈りを行っている。
また、最大ケースでも93ターンで終了することがサンプルケースからわかるので、どこかの攻撃回数が94回を超えたものも無視する。

class Mutalisk {
	public:
	int minimalAttacks(vector <int> X) {
		set<int> T[61];
		int N=X.size();
		int i,x,y,z;
		int thr=93;
		
		for(i=1;i<=60;i++) {
			for(x=0;x*9<=i+8;x++) {
				for(y=0;y==0 || x*9+y*3<=i+2;y++) {
					z = max(0,i-x*9-y*3);
					if(x+y+z<=thr) T[i].insert(x*10000+y*100+z);
				}
			}
		}
		
		map<int,int> S;
		S[0]=0;
		
		FOR(i,N) {
			map<int,int> S2;
			FORR(r2,T[X[i]]) {
				int x2=r2/10000, y2=r2/100%100, z2=r2%100;
				FORR(r,S) {
					int x=x2+r.first/10000;
					int y=y2+r.first/100%100;
					int z=z2+r.first%100;
					if(x>thr || y>thr || z>thr) continue;
					int tar=x*10000+y*100+z;
					if(S2.count(tar)==0) S2[tar]=10000;
					S2[tar]=min(S2[tar],max(x2+y2+z2,r.second));
				}
			}
			S.clear();
			FORR(r,S2) {
				int x2=r.first/10000, y2=r.first/100%100, z2=r.first%100;
				if(x2 && S2.count(r.first-10000)) continue;
				if(y2 && S2.count(r.first-100)) continue;
				if(z2 && S2.count(r.first-1)) continue;
				if(x2&&y2&&S2.count(r.first-10100)) continue;
				if(x2&&z2&&S2.count(r.first-10001)) continue;
				if(y2&&z2&&S2.count(r.first-101)) continue;
				S.insert(r);
			}
		}
		
		int mi=100;
		FORR(r,S) mi=min(mi,max(r.first/10000,max(r.first/100%100,max(r.first%100,r.second))));
		
		return mi;
	}
}

class MutaliskEasy {
	public:
	int minimalAttacks(vector <int> x) {
		int pat[6][3]={{1,3,9},{1,9,3},{3,1,9},{3,9,1},{9,1,3},{9,3,1}};
		int A[6],i,j,mi=100;
		while(x.size()<3) x.push_back(0);
		FOR(A[0],16) FOR(A[1],16) FOR(A[2],16) FOR(A[3],16) FOR(A[4],16) {
			vector <int> y=x;
			FOR(i,3) FOR(j,5) y[i] -= A[j]*pat[j][i];
			A[5]=0;
			A[5]=max(A[5],(y[0]+8)/9);
			A[5]=max(A[5],(y[1]+2)/3);
			A[5]=max(A[5],y[2]);
			mi=min(mi,A[0]+A[1]+A[2]+A[3]+A[4]+A[5]);
		}
		return mi;
		
	}
}

まとめ

本番枝刈りしてなくてTLEしていた。
最大ケースで通ったので問題ないと思ったのだが、もったいなかったな…。