ARC100 D - Equal Cut - seica

ARCももう三桁回数開いてるんですね。

問題

D - Equal Cut

感想

本番中全く頭が働いていませんでしたが、、、。

数列を四つに分ける(= 数列に仕切りを三つ入れる)というのですが、普通にやると間に合わないので一つ固定したときにどうなるかを見てみます。

状態を1つ進めるといい、という感覚ですね。今回どこを固定するかというと(端っこというのも考えたくなりますが)真ん中の仕切りを決めるのがよさそうですね。

では真ん中を決めたときに、そのあとどうするかという話ですが。

右の部分と左の部分、それぞれなるべく二つの差が小さくなるように分けるのがベストです。

最も均等になるように分けた際の二つの数列の和がそれぞれA、B(A < Bとします)だった時、Aの中の要素を1つBに移す操作はAが余計小さく、またBが余計大きく成るだけで無駄です。

また、Bの中の中の要素を1つAに移す操作を考えたとき、もともとAとBの差が最小になるようにとっているので、その要素の値はabs(A-B)以上です。したがってこの場合BがもとのAより小さく、AがもとのBより大きく成り、やはり無駄になることがわかります。

それがわかってしまうとそんなにむつかしくないですね。

[1,i]の要素の中で二つに区切る場所はiに対して広義単調増加ですね、[i,n]に関しても同じなので尺取り法が使えます。

と、言うことで。

[1,i]、[i,n]の各範囲について最適な分け方を求めてから(O(n)) ,

真ん中の区切りについて全探索(O(n))

となります。

コード

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

pair<ll,ll> L[222222];
pair<ll,ll> R[222222];

int main(){
	
	int n;cin >> n;
	
	vector<ll> v(n);
	vector<ll> sv(n);
	
	REP(i,n){
		cin >> v[i];
		sv[i] = v[i];
	}
	
	REP(i,n-1)sv[i+1] += sv[i];
	
	ll now_s = v[0];
	ll now_p = 0;
	for(ll i = 1;i < n;i++){
		while(now_p < i-1 && abs(2*now_s-sv[i]) > abs(2*(now_s+v[now_p+1]) - sv[i])){
			now_p++;
			now_s += v[now_p];
		}
		L[i] = MP(now_s,sv[i] - now_s);
	}
	
	now_p = n-1;
	now_s = v[n-1];
	
	for(ll i = n-2;i > 0;i--){
		while(now_p > i+1 && abs(2*now_s-(sv[n-1]-sv[i-1])) > abs(2*(now_s+v[now_p-1]) - (sv[n-1]-sv[i-1]))){
			now_p--;
			now_s += v[now_p];
		}
		R[i] = MP(now_s,(sv[n-1] - sv[i-1]) - now_s);
	}
	
	ll ans = LLINF;
	
	for(int i = 1;i < n-2;i++){
		ll ma = max(max(L[i].FI,L[i].SE),max(R[i+1].FI,R[i+1].SE));
		ll mi = min(min(L[i].FI,L[i].SE),min(R[i+1].FI,R[i+1].SE));
		ans = min(ans,ma - mi);
	}
	
	cout << ans << endl;
	
	return 0;
}

尺取り、慣れてきた感があります。