TopCoder SRM475 Div1Hard

Algorithm TopCoder

問題

うさぎがプログラミングコンテストに参加した。コンテストはいくつかの問題からなり、そのうちいくつかは採点され全うさぎについての正誤が判明しているが、それ以外の問題についてはまだどのうさぎの正誤も判明していない。
このコンテストの上位 qualified 匹を選び（同点のときは番号の早い順）、そのうち selected 匹を代表チームに選ぶ。チームの組み合わせは何通り考えられるか求めよ。

解法

各うさぎについて、得られる最低得点と最高得点がわかるのでまず求める。同点の場合の処理は、得点を 50 倍くらいして、番号の早い順に 49, 48, … と足してやるとよい。
ある組み合わせがチームとして有りうるかを考えたとき、そのチームのうさぎは全て最高得点、他のうさぎは全て最低得点であったとしてよい。
そこで、うさぎを最高得点の昇順にソートする。あるうさぎが最も低い得点で代表になったうさぎだとするとき、他のうさぎは次の 3 通りに分類できる。

  1. どうやっても最低点うさぎより点数が高くならないうさぎ
  2. 絶対に最低点うさぎより点数が高くなるうさぎ
  3. 最低点うさぎより点数が高くなったり高くならなかったりするうさぎ

1. は考える必要はない。2. と 3. から合わせて selected-1 匹のうさぎを選ぶ必要がある。2. と 3. について選ぶ数を固定したとき、何通りのチームができるかはすぐに分かる。但し、上位 qualified 匹中 qualified-selected 匹しか 2. からは除外できないので、これを満たさないときはチームは作れない。
以上のことをすべてのうさぎを最低点うさぎとして考えて組み合わせを求めればよい。

コード

#include<vector>
#include<string>
#include<algorithm>
using namespace std;
typedef long long i64;

class RabbitProgramming
{
	int N;
	vector<pair<int, int> > P;
	i64 C[51][51];
public:
	i64 getTeams(vector<int> pt, vector<string> stand, int Q, int S)
	{
		for(int i=1;i<=50;i++) C[0][i] = 0; C[0][0] = 1;
		for(int i=1;i<=50;i++){
			C[i][0] = 1;
			for(int j=1;j<=50;j++) C[i][j] = C[i-1][j-1] + C[i-1][j];
		}
		
		N = stand.size();
		
		for(int i=0;i<N;i++){
			//pMin[i] = 0; pMax[i] = 0;
			int mn=0, mx=0;
			for(int j=0;j<pt.size();j++) if(stand[i][j]=='Y'){
				if(pt[j]>0){ mn += pt[j]; mx += pt[j]; }
				else mx -= pt[j];
			}
			P.push_back(make_pair(mx*50+49-i, mn*50+49-i));
		}
		
		sort(P.begin(), P.end());
		
		i64 ret = 0;
		for(int i=0;i<N;i++){
			printf("%d, %d\n", P[i].first, P[i].second);
			int alSelect = 0, maySelect = 0;
			for(int j=0;j<N;j++){
				if(P[j].second > P[i].first) alSelect++;
				else if(P[j].first > P[i].first) maySelect++;
			}
			
			for(int j=0;j<S;j++){
				//choose j from alSelect, (S-1-j) from maySelect
				if(Q-S < alSelect-j) continue;
				ret += C[alSelect][j] * C[maySelect][S-1-j];
			}
		}
		
		return ret;
	}
};