TopCoder SRM 758 Div1 Medium LollipopHoney

これはなんかスムーズに解けた。
https://community.topcoder.com/stat?c=problem_statement&pm=15409

問題

N個の飴があり、それぞれ風味F[i]とおいしさD[i]が与えられる。
これらの飴を、K人に2個ずつ与えたいので、N個から2K個選ぶとする。

その際、下記条件を満たすおいしさの総和とそれを満たす選び方の組み合わせ数を答えよ。

• 1人に同じ風味の飴が2個くる与え方がないようにしたい。
• おいしさの総和を最大化したい。

解法

前者については、結局1つの風味からはK個までしか選択できない、とすると単純なナップサック問題になる。
ある風味の飴からいくつか選択する場合、当然ながらおいしさが上位のものから順に選択するが、例えばm個選ぶときにm番目と(m+1)番目以降のおいしさが同一である場合、m個の選び方が一通りでなくなるので注意。

ll from[52][2];
ll to[52][2];
ll mo=1000000007;

static const int N_=1020;
static ll C_[N_][N_];


class LollipopHoney {
	public:
	vector <int> count(int K, vector <int> F, vector <int> D) {
		int i,j;
		
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
		
		map<int,vector<int>> M;
		
		FOR(i,F.size()) M[F[i]].push_back(D[i]);
		
		from[0][0]=0;
		from[0][1]=1;
		for(i=1;i<=51;i++) from[i][0]=-1,from[i][1]=0;
		
		FORR(m,M) {
			for(i=0;i<=51;i++) to[i][0]=-1,to[i][1]=0;
			
			vector<int> V=m.second,P,S;
			sort(ALL(V));
			reverse(ALL(V));
			S.push_back(0);
			FORR(v,V) S.push_back(S.back()+v);
			P.push_back(1);
			FOR(i,V.size()) {
				int ins=0,tot=0;
				FOR(j,V.size()) if(V[i]==V[j]) {
					tot++;
					if(j<=i) ins++;
				}
				P.push_back(C_[tot][ins]);
				
			}
			
			for(i=0;i<=2*K;i++) if(from[i][0]>=0) {
				for(j=0;j<=min(K,(int)S.size()-1) && (i+j)<=2*K;j++) {
					int sc=from[i][0]+S[j];
					if(sc>to[i+j][0]) {
						to[i+j][0]=sc;
						to[i+j][1]=0;
					}
					if(sc==to[i+j][0]) (to[i+j][1]+=from[i][1]*P[j])%=mo;
				}
			}
			
			swap(from,to);
		}
		
		if(from[2*K][0]<0) return {};
		return {(int)from[2*K][0],(int)from[2*K][1]};
	}
}

まとめ

総和の最大化じゃなく、各個人に割り当てられる飴のおいしさの和の最小値の最大化、とかだとどうなってたかな。