UVa12001 UVa Panel Discussion
問題文
http://uva.onlinejudge.org/external/120/12001.html
解法
問題の否定を取って全体の場合から引けば O(N^2) で答えが出る。
O(N^4) でも通るみたいだけど、多分それだとコードが書きにくくなる気がする。
下で組み合わせは パスカルの三角形のDP でなく別の関数で求めている。(これにより Runtime Error などのミスが無くなる)
反省
comb(num[i], 2) と書くところが2つあるが、一つを書き間違いで comb(i, 2) と書いていた 〜完〜
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MAX (300) ll comb(ll n, ll r) { ll res = 1; if(n-r < r) r=n-r; for(int i=1; i<=r; i++, n--) { res *= n; res /= i; } return res; } int main(){ int N, M, arr[MAX]; int num[51]; while(cin >> N >> M && (N | M)){ memset(num, 0, sizeof num); ll sum = 0; for(int i=0; i<N; i++){ cin >> arr[i]; num[arr[i]-1] ++; } for(int i=0; i<M; i++) { sum += num[i]; } ll three = comb(sum, 3), four = comb(sum, 4); for(int i=0; i<M; i++) { if(num[i]-1> 0) { for(int j=0; j<M; j++) { if(j == i) continue; if(num[j] == 0) continue; three -= comb(num[i], 2)*num[j]; } } } /////////////////////////////////////////////////// if(N == 3) { cout << three << " 0" << endl; continue; } for(int i=0; i<M; i++) { if(num[i] >= 2) { for(int j=i+1; j<M; j++) { if(i == j) continue; if(num[j] >= 2) { four -= comb(num[i], 2)*comb(num[j], 2); } } } } cout << three << " " << four << endl; } return 0; }