TopCoder SRM 673 Div1 Easy BearCavalry

なかなか良好な出来で、レート自己ベストをちょっとだけ更新。
https://community.topcoder.com/stat?c=problem_statement&pm=14081

問題

N人の兵士がおり、その強さはそれぞれW[i]である。
また、N頭の馬がおり、その強さはそれぞれH[i]である。

兵士に1頭ずつ馬を与え、兵士と馬のペアからなるユニットを作りたい。
ユニットの強さは兵士と馬の強さの積である。

兵士に馬を割り当てる方法はN!通りある。
このうち、先頭の兵士から作られるユニットが単独最強の強さとなるような割り当て方の数を求めよ。

解法

先頭の兵士に割り当てる馬を総当たりし、それぞれ条件を満たす残り(N-1)ユニットの組み合わせ方を求めよう。
まず先頭の兵士に割り当てる馬を決めた時点で、先頭の兵士からなるユニットの強さが決まるので、残りのユニットはその強さ未満になるようにすればよい。

強い兵士ほど割り当て可能な馬は減る。
またその割り当て可能な馬は、必ず弱い兵士に割り当てても問題ない。
そこで、残り(N-1)人の兵士に対し割り当て可能な馬の数を求めよう。

兵士を強い順にソートし、i番目が割り当て可能な馬の数をf(i)とする。
f(i)は単調増加である。
兵士を前から順に割り当てることを考えると、前の兵士が割り当てた馬は、自分も割り当て可能だった馬のはずである。
よってf(i)-iを各iに対して掛け合わせればよい。もしf(i)-iが0以下なら、そのような割り当て方は存在しないことになる。

ll mo=1000000007;

class BearCavalry {
	public:
	
	int countAssignments(vector <int> W, vector <int> H) {
		int N=W.size();
		ll ret=0;
		int t,x,y;
		
		FOR(t,N) {
			int ok[51]={};
			int master = W[0]*H[t];
			for(x=1;x<N;x++) FOR(y,N) if(y!=t && W[x]*H[y]<master) ok[x-1]++;
			
			sort(ok,ok+N-1);
			ll tret=1;
			FOR(x,N-1) (tret *= max(0,ok[x]-x))%=mo;
			ret += tret;
		}
		return ret%mo;
	}
}

まとめ

これ250ptでもいいと思ったけどな。