AOJ 2751 BaseBall (野球観戦)
問題概要
2つのチーム（X と Y と呼ぶことにする）が，合計 A + B + C 回試合を行った．
A は X が勝利した回数 B は Y が勝利した回数，C は引き分けた回数である．
また，X と Y はそれぞれ合計して Sx と Sy を得点したとする．
このような途中試合結果は何通り考えられるか？（試合の順番も考慮する）
解法
何対何でどちらが勝った，などを正直に考えてそれぞれ求めていくのは非常に困難．
こういうときは，何かわかりやすい基準を定めてしまうことで，簡単な問題に落とすのが良い．
今回は，引き分け分の得点をその基準に使う．ただし，引き分け分の得点とは，真に引き分けの試合でそれぞれ何点獲得したか（これは X と Y で等しい）だけでなく，引き分けでない試合も含めて考える．
どういうことかというと，例えば 5 対 3 の試合は 2 対 0 と 3 対 3 に分ける（本当に分けるわけではないですが）ことができる．
こうすると，勝ち負けが決まった試合に対して，どちらが何点だけ上回ったか，という問題に落とせる．
これは重複組合せの問題である．
例えば，X が 3試合勝ったとして，勝った試合だけ考えると合計 4 点勝ち越したとすると，3試合に4点をどう分配するか（ただしどれも少なくとも1点は振り分ける必要がある）という問題になる．これは典型的な重複組合せの問題．
以上のアイデアをまとめると，
1. まず（広義の）引き分けの分の総得点 Sc を決め打ちする
2. X と Y の勝ち越し合計はそれぞれ Sx - Sc 点，Sy - Sc 点．これを総試合のうち A 試合，B試合にそれぞれ分配する．ただし，少なくとも1点はそれぞれに分配されている必要がある．
3. 引き分けの分を分配する．これは C だけ分配するのではなくて，A + B + Cにだけ分配し，全く分配されない試合があっても良い．
これですべての試合を網羅できる．
得点の合計は 10^6 * 3 なのでまあ間に合う．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; const int MOD = 1000000007; using mod = modulo<MOD, true>; // mod のライブラリ．略 int main() { ll A, B, C, X, Y; while(cin >> A >> B >> C >> X >> Y, A + B + C > 0) { ll const match = A + B + C; mod res; ll const lim = min(X - A, Y - B); for(ll draw = 0; draw <= lim; ++draw) { ll x_win_point = X - draw; ll y_win_point = Y - draw; mod t = 1; // 広義の引き分け分を分配 t *= comb<MOD>(match + draw - 1, draw); if(x_win_point > 0 && A == 0 || x_win_point - A < 0) { t = 0; } if(y_win_point > 0 && B == 0 || y_win_point - B < 0) { t = 0; } // A と B にそれぞれ分配．最低1点は振り分ける． t *= comb<MOD>(x_win_point - 1, A - 1) * comb<MOD>(match, A); t *= comb<MOD>(y_win_point - 1, B - 1) * comb<MOD>(match - A, B); res += t; } cout << (ll)res << endl; } }
感想
なんか重複組合せは試合の順番を考慮できないとか意味不明なことを考えていたせいで手間取った．悲しいね．
