Codeforces Beta Round #95 (Div. 2) C : The World is a Theatre

問題概要

男がN(4<=N<30)人、女がM(1<=M<30)人いる。男が最低4人、女が最低1人いるように丁度T人選ぶ。選び方が何通りあるか求める問題。

解法

もちろん男が何人選ばれるか全通り試せば(前処理を除いて)O(N)で解けるんだけど、なぜか本番中は別の解き方で解いた。選んだ男どもと女どもをそれぞれ番号でソートする。4人目の男と1人目の女がだれになるかを全通り試す。

本番で通ったコード

計算量O(M*N)。

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long int64;

const int MAX_N = 60;

int N, M, T;
int64 comb[MAX_N+1][MAX_N+1];

void init(){
	for(int n=0; n<=MAX_N; n++){
		comb[n][0] = comb[n][n] = 1;
		for(int k=1; k<n; k++){
			comb[n][k] = comb[n-1][k-1] + comb[n-1][k];
		}
	}
}

int64 solve(){
	int64 ans = 0;

	for(int i=4; i<=N; i++){
		for(int j=1; j<=M; j++){
			ans += comb[i-1][3] * comb[j-1][0] * comb[N-i + M-j][T-5];
		}
	}


	return ans;
}

int main(){

	init();
	scanf("%d%d%d", &N, &M, &T);
	cout << solve() << endl;

	return 0;
}