TopCoder SRM 646 Div2 Hard TheFootballDivTwo

ちょっと変わった形でDiv1との差をつけてある。
http://community.topcoder.com/stat?c=problem_statement&pm=13630

問題

何チームかで繰り返し試合を行っている。
現時点で、自分のチームの得点はYである。
他、得点がS[i]のチームがT[i]チームずつある。

各チームはあと２回ずつ試合を行う。
試合は必ず勝者と敗者が現れ、勝者は３得点を得られる。

各チームが行う２試合の相手と勝者を任意に選択できる場合、自分のチームの最高順位が何位になるか答えよ。

解法

全チーム数合計をNチームとする。
自分のチームは残り２試合勝つと仮定すると、６点追加できる。

残り2*(N-1)試合分の勝利得点が残り(N-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は同点が存在するんだよなぁ。