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; }