TopCoder SRM 755 Div1 Medium OneHandRoadPainting

これも400ptぐらいでよさそう。
https://community.topcoder.com/stat?c=problem_statement&pm=15418

問題

１次元の数直線上で、いくつかの区間が与えられる。
ブラシを使ってその区間に色を塗りたい。
座標0にバケツがあり、そこにブラシを浸すと、以後距離Pの間色を塗ることができる。
なお、このPは連続している必要はなく、複数の区間で合計P以下の距離の色を塗ることができる。

初期状態で座標0におり、終了時0で戻るようにブラシを動かす場合、全ての区間の色を塗るのに必要な最小移動量を求めよ。

解法

遠い順に塗りつぶしていくとよい。
もし１回で塗り切れない長い区間がある場合、複数回掛けて塗るとしてその移動量の総和は等差数列の総和なのでO(1)で求められる。

class OneHandRoadPainting {
	public:
	long long fastest(vector <int> S, vector <int> E, int P_) {
		ll P=P_;
		ll ret=0;
		while(S.size()) {
			if(S.back()==E.back()) {
				S.pop_back();
				E.pop_back();
				continue;
			}
			if(E.back()-S.back()>=P) {
				ll num=(E.back()-S.back())/P;
				ll e=E.back();
				ll f=e-(num-1)*P;
				ret+=(e+f)*num/2;
				E.back()-=P*num;
			}
			else {
				ret+=E.back();
				ll lef=P;
				while(lef&&S.size()) {
					ll m=min(E.back()-S.back(),(int)lef);
					lef-=m;
					E.back()-=m;
					if(E.back()==S.back()) {
						E.pop_back();
						S.pop_back();
					}
				}
			}
		}
		return 2*ret;
	}
	
}

まとめ

なんで毎回片手けがするんですかね。