TopCoder SRM 757 Div1 Easy CentipedeSocks

方針ガチャをミスってEasyもMediumも低スコア。辛うじてResubmitでMediumのミスを防ぎレート微減で済んだ。
https://community.topcoder.com/stat?c=problem_statement&pm=15445

問題

F個の足を持つムカデがC匹いる。
ここでたくさんの靴下が入った袋がある。
この袋には、i番目の色の靴下がS[i]個ずつ入っている。

この袋から適当に靴下を何個か取ったとき、各ムカデがF足とも同じ色の靴下を割り当てられるようにするには、最小で何個靴下を取ればよいか。

解法

貪欲解法でも行けるらしいが、自分は戸惑ったうえでDPで回避した。
全部取り出してもC匹分揃わないケースを除けば、C匹分揃わないケース、すなわち(C-1)匹分揃う最大の靴下数を求めれば、そこに1足せば解になる。

以下の状態を考えて更新していけばよい。
dp(i,j) := i番目までの色の靴下をいくつか抜き出したところ、j匹分のムカデに充当するような最大靴下数
dp(|S|,C-1)+1が解。

int dp[101][51];

class CentipedeSocks {
	public:
	
	int fewestSocks(int C, int F, vector <int> S) {
		
		MINUS(dp);
		dp[0][0]=0;
		int i;
		FOR(i,S.size()) {
			int j,x;
			FOR(j,C+1) if(dp[i][j]>=0) {
				FOR(x,min(S[i]+1,C*F+1)) {
					if(j+x/F>C) break;
					dp[i+1][j+x/F]=max(dp[i+1][j+x/F],dp[i][j]+x);
				}
			}
		}
		
		if(dp[S.size()][C]==-1) return -1;
		return dp[S.size()][C-1]+1;
	}
}

まとめ

これ貪欲法にこだわったのタイムロスでかいなぁ。