TopCoder SRM 843 : Div1 Easy ChristmasSongTrauma

久々に0ptやらかしてしまった。
https://community.topcoder.com/stat?c=problem_statement&pm=17947

問題

ショッピングモールでは、N個の曲の並びを繰り返し再生している。
入力として、各曲の再生時間とショッピングモールの滞在時間Tが与えられる。

ショッピングモールにとあるランダムな整数時間のタイミングで入り、入力の滞在時間で出るとする。
1秒でも曲を聞ける数が、最小となる確率はいくらか。

解法

コーナーケースとして、滞在時間が曲1周以上であれば、必ず全曲聞ける。
以下そうでない場合を考える。

まず最小の曲数を求めよう。
これは、各曲の初めのタイミングで入場したとき何曲聞けるかを求めればよい。
この曲数をXとする。

次に各曲の開始時点で入場したとき、あとどのぐらいの間X聞けるかをカウントしよう。
入場したときの曲の長さをA、その場合T経過後時点でその曲があとBだけ残っているとする。
その場合min(A,B+1)の間だけ、開始を遅らせてもX曲聞ける。

もう一つコーナーケースがあり、X=Nの場合はBを無限大としてよい。これは、B以上経過して入場した場合、曲順が1周して同じ曲を2回聞くだけで、曲数が増えるわけではないためである。

class ChristmasSongTrauma {
	public:
	double fewest(vector <int> playTime, int visitTime) {
		int N=playTime.size();
		ll sum=0;
		FORR(p,playTime) sum+=p;
		if(visitTime>=sum) return 1;
		int mi=N;
		int i,j;
		FOR(i,N) {
			ll lef=visitTime;
			FOR(j,N) {
				lef-=playTime[(i+j)%N];
				if(lef<=0) break;
			}
			mi=min(mi,j);
		}
		ll tot=0;
		FOR(i,N) {
			ll lef=visitTime;
			FOR(j,N) {
				lef-=playTime[(i+j)%N];
				if(lef<=0) break;
			}
			if(mi==j) {
				if(mi==N-1) lef=-1<<30;
				tot+=min(playTime[i],1+(int)-lef);
			}
		}
		return tot*1.0/sum;
		
	}
}

まとめ

久々の0ptで確かにトラウマを植え付ける問題でした。