AtCoder AGC #030 : B - Tree Burning

うーん、AGC振るわないなぁ…。
https://atcoder.jp/contests/agc030/tasks/agc030_b

問題

円周上でN個の木の位置が与えられる（座標は反時計回り順で振られている）。
始点から始め、時計回りか反時計まわりを指定すると、木にぶつかるまで移動し、木にぶつかると停止して木を抜き、また方向を指定する…という作業を木がなくなるまで繰り返す。
総移動量の最大値を求めよ。

解法

基本的に時計回りと反時計回りを交互に繰り返すのがよさそう…というのは推測がつく。
反時計回りでぶつかる木を座標の小さい順L個とし、残りR=(N-L)個は時計回りでぶつかるとする。
Lを総当たりし、それぞれの移動量の最大値を求めよう。

• L＞Rの場合、まず反時計回りからはじめ、反時計回り側は原点から遠い(R+1)箇所と、時計回り側で原点から遠いR箇所を交互に辿るのが良い。
• L＜Rの場合、まず時計回りからはじめ、時計回り側は原点から遠い(L+1)箇所と、反時計回り側で原点から遠いL箇所を同様にたどる。
• L==Rの場合、時計回りと反時計回り両方で開始するケースを両方辿る。

それぞれのケースは累積和を取っておけばO(1)で求められるので、全体でO(N)で済む。

ll L;
ll N;
ll X[202020];
ll LL[202020];
ll RR[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>L>>N;
	for(i=1;i<=N;i++) cin>>X[i];
	
	for(i=1;i<=N;i++) {
		LL[i]=LL[i-1]+(L-X[N+1-i]);
		RR[i]=RR[i-1]+X[i];
	}
	
	ll ma=max(X[N],L-X[1]);
	for(int le=1;le<=N-1;le++) {
		int ri=N-le;
		
		ll pat=0;
		x=min(le,ri+1);
		y=x-1;
		pat=(LL[le]+LL[le-1]-2*LL[le-x]);
		pat+=2*(RR[ri]-RR[ri-y]);
		ma=max(ma,pat);

		y=min(le+1,ri);
		x=y-1;
		pat=2*(LL[le]-LL[le-x]);
		pat+=RR[ri]+RR[ri-1]-2*RR[ri-y];
		ma=max(ma,pat);
		
		x=y=min(le,ri);
		pat=2*(LL[le]-LL[le-x]);
		pat+=RR[ri]+RR[ri-1]-2*RR[ri-y];
		ma=max(ma,pat);

		pat=(LL[le]+LL[le-1]-2*LL[le-x]);
		pat+=2*(RR[ri]-RR[ri-y]);
		ma=max(ma,pat);
		
	}
	cout<<ma<<endl;
	
	
}

まとめ

まぁここまではいいのだが…。