TopCoder SRM 854 : Div1 Easy Div2 Hard CollectBoxes

コーナーケースに見事にはまった。
https://community.topcoder.com/stat?c=problem_statement&pm=18172

問題

1次元座標上にN個の箱がある。
プレイヤーは最初に原点におり、時速1で正または負の方向に移動可能である。
またその際1個まで箱を持つことができる。箱を持ったり下ろしたりするのには時間はかからない。

どこか任意の座標に全部の箱を集めたい場合、必要な最小時間を求めよ。

解法

集める場所を、いずれかの箱の初期位置または原点で総当たりしよう。
仮に集める座標が正の場合、初手は原点から最も座標の小さい箱を取りに行くようにすればよい。

コーナーケースとして、最初から全部の箱が同じ座標にある場合がある。
この場合解は0なので注意。

ll B[505050];
ll BS[505050];

class CollectBoxes {
	public:
	long long collect(int N, vector <int> Bprefix, int seed, int blo, int bhi) {
		int i;
		FOR(i,Bprefix.size()) B[i]=Bprefix[i];
		ll state=seed;
		ll spread = bhi - blo + 1;

		for(i=Bprefix.size();i<N;i++) {
		    state = (state * 1103515245 + 12345) % (1LL<<31);
		    B[i] = blo + (state %spread);
		}
		ll ret=1LL<<60;
		int j;
		ll a=0;
		FOR(i,N) a+=abs(B[i])*2;
		ret=min(ret,a);
		
		FOR(j,2) {
			sort(B,B+N);
			if(B[0]==B[N-1]) return 0;
			FOR(i,N) BS[i+1]=BS[i]+B[i];
			FOR(i,N) if(B[i]>=0) {
				ll sum=0;
				if(B[0]>=0) {
					sum+=B[i];
				}
				else {
					sum+=B[i]+abs(B[0])*2;
				}
				sum+=2*(B[i]*(i-1)-(BS[i]-BS[1]));
				sum+=2*((BS[N]-BS[i])-B[i]*(N-i));

				ret=min(ret,sum);
				
			}
			FOR(i,N) B[i]=-B[i];
		}
		
		return ret;
		
	}
}

まとめ

うーん。コーナーケース抜いてもこれ300ptぐらいで良い気がするんだけどな。