yukicoder : No.794 チーム戦

Editorialと違う解法だった。
https://yukicoder.me/problems/no/794

問題

N人(偶数人)で２人組をN/2個作る。
i番目の人のレートがA[i]であるとき、各組の合計レートはK以下でなければならないとする。
条件を満たす組み合わせは何通りか。

解法

まず、N人をK/2を超える人の組と超えない人の組に分ける。
前者は後者の人と組まなければならず、後者同士は任意の組み方ができる。

まず前者を降順ソートしよう。
前者のうちi番目の人は、後者のうちn人と組めるとする(これは後者の人をソートしておけばlower_boundで高速に求められる)。
n人中(i-1)番は自身より前の人の誰かとすでに組んでいるはずなので、i番目の人の候補は(n-(i-1))通りである。

後者の方がm人多かったとすると、その人たちはm人内で任意に２人ずつ組めるので、(m-1)!!通り。

int N;
ll K;
vector<ll> A,B;
ll mo=1000000007;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>x;
		if(x*2<=K) A.push_back(x);
		else B.push_back(x);
	}
	sort(ALL(A));
	sort(ALL(B));
	if(B.size()>A.size()) return _P("0\n");
	
	reverse(ALL(B));
	ll ret=1;
	FOR(i,B.size()) {
		x=lower_bound(ALL(A),K-B[i]+1)-A.begin();
		if(x<=i) return _P("0\n");
		ret=ret*(x-i)%mo;
	}
	
	x=A.size()-B.size();
	while(x) {
		ret=ret*(x-1)%mo;
		x-=2;
	}
	cout<<ret<<endl;
	
}

まとめ

なんか最近まともにyukicoderを時間通りに出られていないな。