ちょっと変わった形でDiv1との差をつけてある。
http://community.topcoder.com/stat?c=problem_statement&pm=13630
問題
何チームかで繰り返し試合を行っている。
現時点で、自分のチームの得点はYである。
他、得点がS[i]のチームがT[i]チームずつある。
各チームはあと2回ずつ試合を行う。
試合は必ず勝者と敗者が現れ、勝者は3得点を得られる。
各チームが行う2試合の相手と勝者を任意に選択できる場合、自分のチームの最高順位が何位になるか答えよ。
解法
全チーム数合計をNチームとする。
自分のチームは残り2試合勝つと仮定すると、6点追加できる。
残り2*(N-1)試合分の勝利得点が残り(N-1)チームに分配されることになる。
あと1・2試合勝利すると自分のチームの得点を超えそうなチームには、勝利得点を与えないようにしたい。
逆にすでに自分のチームより得点が多いチームや、自分のチームより6点以上得点の小さいチームは、今更2試合勝利しても自分のチームの順位には影響しない。
よって、後者に相当するチームにはまず2勝分ずつ勝利得点を与えてしまう。
まだ勝利得点が残っている場合、あと2勝すると自分の得点を超えるチームに1勝ずつ勝利得点を与えてしまおう。
これでもまだ勝利得点が残っている場合、あとはもう1勝で自分の得点を超えるチームしか残っていないので、それらに勝利得点を割り振るしかない。
その場合、自分のチームの得点を超えるチームを最小限にするため、元々1勝で自分のチームを超えるチームに2勝分ずつ得点を与えてしまい、それでも残った勝利得点はあきらめて(すでに1勝分得点を与えてある)2勝必要なチームにもう1勝ずつ与えればよい。
補足:こちらの方が図付きでわかりやすいです。
SRM 646 Div2 (練習) - tatanaideyo's blog
class TheFootballDivTwo { public: int find(int Y, vector <int> S, vector <int> T) { int N=S.size(); int i,j,x,y,P[4]={},t=1,more=0; Y+=6; FOR(i,N) { if(S[i]>Y) P[0]+=T[i], more+=T[i]; else if(S[i]+3>Y) P[1]+=T[i]; else if(S[i]+6>Y) P[2]+=T[i]; else P[3]+=T[i]; t+=T[i]; } int l=t-(1+P[0]+P[3])*2-P[2]; if(l>=P[1]*2) more += P[1] + (l-P[1]*2); else if(l>0) more += (l+1)/2; return more+1; } }
まとめ
Div1 Hardは同点が存在するんだよなぁ。