TopCoder SRM 853 : Div1 Easy CollectTrash

解法考えるより入力部分を書くのがめんどい。
https://community.topcoder.com/stat?c=problem_statement&pm=18169

問題

直線上にT個のごみがあり、それぞれ現在地からの距離が与えられる。
これらのごみを、P人で拾い集めたい。
各人は1秒毎に

• 距離1進む
• 今いる位置にあるごみを1つ拾う

のいずれかを行える。
P人が全部のごみを拾い上げるのにかかる最小時間を求めよ。

解法

二分探索で解く。
各人以下のようにふるまえばよい。

• 残されたゴミのうち、一番通りものを拾いに行く。その際時間が余るなら、現在地から遠い順に拾い上げて行く。

class CollectTrash {
	public:
	int optimize(int P, int T, int M, int C, vector <int> Lprefix, int seed) {
		ll state=seed;
		int PL=Lprefix.size();
		vector<ll> L;
		FORR(a,Lprefix) L.push_back(a);
		
		int i;
		for(i=PL;i<T;i++) {
			if(C==1&&i) {
				state = (state * 1103515245 + 12345) % (1LL<<31);
		        ll old = L[state%i];
				state = (state * 1103515245 + 12345) % (1LL<<31);
		        ll spread = (state%21)-10;
		        L.push_back(max(0LL, min(M-1LL, old+spread)));
		    }
		    else {
				state = (state * 1103515245 + 12345) % (1LL<<31);
		        L.push_back(state%M);
		    }
		}
		sort(ALL(L));
		ll ret=1LL<<60;
		for(i=59;i>=0;i--) {
			ll tmp=ret-(1LL<<i);
			ll num=0;
			ll cur=L.size()-1;
			while(cur>=0) {
				num++;
				ll lef=tmp-(L[cur]+1);
				if(lef<0) break;
				cur-=lef+1;
			}
			if(cur<0&&num<=P) ret=tmp;
		}
		return ret;
	}
}

まとめ

いい加減入力に10^5要素入れられるようにするか、コピペで使える入力にしてくれないかな…。