TopCoder SRM 838 : Div1 Easy Div2 Hard FlippingCoinSum

Easyを手間取った末に落としたけど、Medium/Hard通してレート増減1桁だった。
https://community.topcoder.com/stat?c=problem_statement&pm=17816

問題

N枚のコインがあり、それぞれ価格が設定されている。
初期状態でいくつかが表向きとなっている。

この状態で、コインを何枚か表裏反転させ、表面を向いたコインの価格の合計がGとなるようにしたい。
最小の反転枚数となる反転のさせ方を1つ答えよ。

解法

f(n,k) := n枚目までのコインを考えたとき、表を向いたコインの総価格がkとなるような最小のコイン反転枚数
とするDPを行い、最後にf(N,G)の状態から復元すればよい。

int num[101][101010];
int from[101][101010];


class FlippingCoinSum {
	public:
	vector <int> flip(vector <int> faceUp, vector <int> faceDown, int goal) {
		int i,j;
		
		FOR(i,101) FOR(j,101000) num[i][j]=1<<30;
		
		num[0][0]=0;
		FOR(i,faceUp.size()) {
			int f=faceUp[i];
			FOR(j,100001) if(num[i][j]<1<<30) {
				if(num[i+1][j]>num[i][j]+1) {
					num[i+1][j]=num[i][j]+1;
					from[i+1][j]=j;
				}
				if(num[i+1][j+f]>num[i][j]) {
					num[i+1][j+f]=num[i][j];
					from[i+1][j+f]=j;
				}
			}
		}
		int k;
		FOR(k,faceDown.size()) {
			int f=faceDown[k];
			i=faceUp.size()+k;
			FOR(j,100001) if(num[i][j]<1<<30) {
				if(num[i+1][j]>num[i][j]) {
					num[i+1][j]=num[i][j];
					from[i+1][j]=j;
				}
				if(num[i+1][j+f]>num[i][j]+1) {
					num[i+1][j+f]=num[i][j]+1;
					from[i+1][j+f]=j;
				}
			}
		}
		
		if(num[faceUp.size()+faceDown.size()][goal]>=1<<30) return {-123456789};
		vector<int> V;
		for(i=faceUp.size()+faceDown.size();i>0;i--) {
			if(i<=faceUp.size()&&from[i][goal]==goal) V.push_back(-faceUp[i-1]);
			if(i>faceUp.size()&&from[i][goal]!=goal) V.push_back(faceDown[i-faceUp.size()-1]);
			goal=from[i][goal];
		}
		return V;
		
	}
}

まとめ

Easy手間取ってスコア低かったけど、結局落としたから結果的には関係ないのか…。