AtCoder ARC #130 : F - Replace by Average

なるほど…。
https://atcoder.jp/contests/arc130/tasks/arc130_f

問題

整数列Aが与えられる。
以下の処理を任意に行えるとする。

• 3つのindex i,j,kをj-i=k-jを満たすように選び、A[j]=floor((A[i]+A[k])/2)で更新する

Aの総和を最小化せよ。

解法

細かい考察ステップはEditorialを参照頂くとして、Aは以下のようにできる。
(i,A[i])を順につないだ2次元の折れ線を考える。
ここに、整数の傾きを持つ直線の集合、上記折れ線の下で接するものを考える。
すると、A[i]はこれらの直線の下に来ない範囲で下げることができる。

これを実装すると、折れ線のうち下半分の凸包を求め、その点で接する整数傾きの直線の傾きの範囲を求めよう。
あとはConvex-Hull-Trickの要領で、これらの直線群の最大値までA[i]を下げる。

int N;
ll A[303030];

const ll EPS=0;
__int128 veccross(pair<__int128,__int128> p1,pair<__int128,__int128> p2,pair<__int128,__int128> p3) {
	p3.first-=p1.first;p2.first-=p1.first;
	p3.second-=p1.second;p2.second-=p1.second;
	return p3.first*p2.second-p2.first*p3.second;
}

template<class C> vector<int> convex_hull_bottom(vector< pair<C, C> >& vp) {
	vector<pair<pair<C, C>, int> > sorted;
	vector<int> res;
	int i,k=0,rb;
	
	if(vp.size()<=2) {
		if(vp.size()>=1) res.push_back(0);
		if(vp.size()>=2) res.push_back(1);
		return res;
	}
	
	FOR(i,vp.size()) sorted.push_back(make_pair(vp[i],i));
	sort(sorted.begin(),sorted.end());
	
	res.resize(vp.size()*2);
	/* bottom */
	FOR(i,vp.size()) {
		while(k>1 && veccross(vp[res[k-2]],vp[res[k-1]],sorted[i].first)<=0) k--;
		res[k++]=sorted[i].second;
	}
	res.resize(k);
	return res;
}

template<typename V> struct ConvexHull {
	deque<pair<V,V>> Q;
	V calc(pair<V,V> p, V x) {
		return p.first*x+p.second;
	}
	int dodo(pair<V,V> A,pair<V,V> B, pair<V,V> C) {
		return ((__int128)(B.second-C.second)*(B.first-A.first)<=(__int128)(A.second-B.second)*(C.first-B.first));
	}
	void add(V a, V b) { // add ax+b
		if(Q.size() && Q.back().first==a) {
			//aが同じ場合
			//if(b>=Q.back().second) return; //minの場合
			if(b<=Q.back().second) return; //maxの場合
			Q.pop_back();
		}
		Q.push_back({a,b});
		int v;
		while((v=Q.size())>=3 && dodo(Q[v-3],Q[v-2],Q[v-1]))
			Q[v-2]=Q[v-1], Q.pop_back();
	}
	void add(vector<pair<V,V>> v) {
		sort(v.begin(),v.end());
		for(auto r=v.begin();r!=v.end();r++) add(r->first,r->second);
	}
	
	
	V query(V x) {
		int L=-1,R=Q.size()-1;
		while(R-L>1) {
			int M=(L+R)/2;
			(0^((calc(Q[M],x)<=calc(Q[M+1],x)))?L:R)=M;
		}
		return calc(Q[R],x);
	}
};
ConvexHull<__int128> ch;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll mi=1LL<<41;
	A[0]=1LL<<41;
	FOR(i,N) {
		cin>>A[i+1];
		mi=min(mi,A[i+1]);
	}
	A[N+1]=1LL<<41;
	
	vector<pair<ll,ll>> V;
	FOR(i,N+2) V.push_back({i,-A[i]});
	vector<int> W=convex_hull_bottom(V);
	
	vector<pair<__int128,__int128>> L;
	for(i=1;i<W.size()-1;i++) {
		ll dy=A[W[i]]-A[W[i-1]];
		ll dx=W[i]-W[i-1];
		__int128 a1=dy/dx;
		if(dx*a1<dy) a1++;
		
		dy=A[W[i+1]]-A[W[i]];
		dx=W[i+1]-W[i];
		
		__int128 a2=dy/dx;
		if(dx*a2>dy) a2--;
		
		
		if(a1<=a2) {
			L.push_back({a1,A[W[i]]-a1*W[i]});
			L.push_back({a2,A[W[i]]-a2*W[i]});
		}
	}
	L.push_back({0,mi});
	ch.add(L);
	
	ll ret=0;
	for(i=1;i<=N;i++) {
		ret+=ch.query(i);
	}
	cout<<ret<<endl;
}

まとめ

実装はともかく、考察がさっとできないなぁ。