読者です 読者をやめる 読者になる 読者になる

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