VK Cup 2015 Round 1 : E. The Art of Dealing with ATM

これにハマりすぎて今回ダメだった…。
http://codeforces.com/contest/529/problem/E

問題

この国にはN種類の紙幣があり、それぞれの価値はA[i]である。

今目の前にあるATMは最大で２種類K枚までの紙幣を払い出すことができる。
Q個のクエリX[i]が与えられる。
それぞれ、このATMでX[i]分の払い出しをできる最小紙幣枚数を答えよ。

解法

紙幣の種類が２枚までなので、半分全列挙で良い。
まずA[i]*j (0≦j≦K)について、mapを使ってその価格を１種類の紙幣で払う最小紙幣枚数を数える。

次に各クエリについて、価格yを１種類の紙幣で払い出しできる場合、X[i]-yをもう１種類の紙幣で払い出せるかmapで検索し、紙幣枚数の和を最小化すればよい。
計算量はO(N*K + Q*log(N*K))かな。

int N,K,Q;
int A[5010];
map<int,int> M;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>A[i];
		for(x=1;x<=K;x++) {
			if(M.count(A[i]*x)==0) M[A[i]*x]=x;
			M[A[i]*x]=min(M[A[i]*x],x);
		}
	}
	M[0]=0;
	
	cin>>Q;
	while(Q--) {
		int X;
		int mi=50;
		cin>>X;
		ITR(it,M) if(M.count(X-it->first)) mi=min(mi,it->second + M[X-it->first]);
		
		if(mi>K) mi=-1;
		cout<<mi<<endl;
	}
}

まとめ

２種類と聞いて２種類の総当たりを取りに行ったのが敗因。
なぜ半分全列挙を思い浮かばなかった。