SRM646div2hard:TheFootballDivTwo
各チームの勝った回数が決まればそこからある勝敗表を再現することができるということがミソ?
問題:http://community.topcoder.com/stat?c=problem_statement&pm=13630
解法:自分のチームは当然2勝する。すると、敵チームの数がNであるとすると、残っている勝ち数はN-1。これを自分のチームに都合の良いように組み合わせる。そのためには、「次の2試合がどうであれyourScore+6より点数が高いチーム」「次の2試合がどうであれyourScore+6より点数が低いチーム」「1勝するとyourScore+6より点数が高くなるチーム」「2勝するとyourScore+6より点数が高くなるチーム」の4つに場合分けすれば良い。
以下ソースコード
typedef long long ll; #define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin();itr!=c.end();itr++) class TheFootballDivTwo { public: int find(int yourScore, vector <int> scores, vector <int> numberOfTeams) { int N = 0, cnt[4] = {0,0,0,0}; int n = scores.size(); for (int i = 0; i < n; i++) { N += numberOfTeams[i]; if (scores[i] > yourScore+6) cnt[0] += numberOfTeams[i]; else if (scores[i] <= yourScore) cnt[1] += numberOfTeams[i]; else if (scores[i] <= yourScore+3) cnt[2] += numberOfTeams[i]; // 2回勝つと超える else cnt[3] += numberOfTeams[i]; // 1回勝つと超える } for (int i = 0; i < 4; i++) cout << cnt[i] << endl; int M = (N-1) - 2*(cnt[0]+cnt[1]) - cnt[2]; if (M <= 0) return cnt[0]+1; if (M <= cnt[3]*2) { return cnt[0]+1+(M+1)/2; } cout << M << endl; M -= cnt[3]*2; if (M <= cnt[2]) { return cnt[0]+1+cnt[3]+M; } return cnt[0]+1+cnt[2]+cnt[3]; } };