AOJ 2751 Baseball 野球観戦

これはなかなか難しいね

問題

野球観戦 | Aizu Online Judge

感想

どれも10^6なので、二重ループは回せなさそうです。

したがって、何かしら共通の基準を用意したいのですが。

例えばCのみ(同点の試合)考えるのであればただの組み合わせですよね、N個のものをM個に分ける(重複を考えた)組み合わせはN+M-1個からM-1個選ぶ操作で考えられます。

AとBについて(どちらかのチームが勝つ試合)の処理が面倒なんです。

AとBをどうにかしたいと考えると、両チーム同じ点数を取った後、片方が余分にまた点数を取るという見方ができます。

そこから「全ての試合が同点だったと仮定したときの、各チームがとった点数の合計」を基準としてみると。

全ての試合が同点だと仮定して組み合わせを考えた後、A試合分のチームXが勝つ試合を選び、組み合わせを計算、B試合分のチームYが勝つ試合を選び、組み合わせを計算。という感じで処理できそうな感じがしてきますね。

各事象について、共通部分を抽出するとうまいこと行きますよ、って感じでしょうか。

難しいですね。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef DEBUG_MODE
    #define DBG(n) n;
#else
    #define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int WWW = 0;WWW < (n);WWW++)cerr << v[WWW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007
 
typedef long long ll;
typedef pair<ll,ll> P;
 
//ａをbで割る
long long mod_div(ll a,ll b){
    if(a % b == 0)return a/b;
    long long tmp = MOD - 2,c = b,ret = 1;
    while(tmp > 0){
        if(tmp & 1){
            ret *= c;ret %= MOD;
        }
        c *= c;c %= MOD;tmp >>= 1;
    }
    return a*ret%MOD;
}
  
#define MAX_K 3333333
vector<long long> kaijo(MAX_K);
long long combination(long long n, long long r){
    if(n < r || n < 0 || r < 0)
        return 0;
    if(kaijo[0] != 1){
        kaijo[0] = 1;
        for(long long i = 1;i < MAX_K;i++)kaijo[i] = (kaijo[i-1] * i) % MOD;
    }
    long long ret = kaijo[n];
    long long tmp = (kaijo[r] * kaijo[n-r]) % MOD;
    return mod_div(ret,tmp);
}
 
int main(){
    ll a,b,c,x,y;
     
    while(cin >> a >> b >> c >> x >> y,a+b+c+x+y){
         
        ll ans = 0;
        ll seica = combination(a+b+c,c) * combination(a+b,b) % MOD;
        for(ll i = 0;i <= min(x,y);i++){
            ll X = x-i-a;
            ll Y = y-i-b;
            if(X < 0 || y < 0)continue;
            if(a == 0 && X > 0)continue;
            if(b == 0 && Y > 0)continue;
            ll tmp = seica;
            if(a+b+c+i-1 >= i)tmp = (tmp * combination(a+b+c+i-1,i)) % MOD;
            if(a+X-1 >= X)tmp = (tmp * combination(a+X-1,X)) % MOD;
            if(b+Y-1 >= Y)tmp = (tmp * combination(b+Y-1,Y)) % MOD;
            ans = (ans+tmp) % MOD;
        }
         
        cout << ans << endl;
    }
    return 0;
}

コード自体は短いですね。