KEYENCE Programming Contest 2019 : E - Connecting Cities

そうそう、ドワンゴの問題とこれでブルーフカ法を知ったんだよね。
https://atcoder.jp/contests/keyence2019/tasks/keyence2019_e

問題

N個の頂点がある。
ここに(N-1)本の辺を張り木を構成したい。
各点iにはパラメータA[i]が設定されている。
頂点i-j間に辺を張るときのコストは定数Dを用いて|i-j|*D+A[i]+A[j]とするとき、最小全域木のコストを求めよ。

解法

複数の解法がある。

１つ目はブルーフカ法。
まずここで重要な知見として、辺は互いに交差しない。
つまりLa-Ra間とLb-Rb間を結ぶ辺があるとき、La＜Lb＜Ra＜Rbのようにはならない。

これは、ブルーフカ法で徐々に連結成分を求めていくとき、連結成分は常にある連続区間になることを示す。
ということは、次のステップでは各頂点から連結成分の外側、つまり最大２つの連続区間におけるコストの最小値を求めればよく、これはSegTreeで容易に計算できる。

もう一つは辺の張り替え。
まず頂点(0,N-1)間で辺を張っているとする。
以後、1～(N-2)の各点について、左右いずれかコストの最も低い点に辺を張る、ということを行う。
これで全体が連結になる。

例えば頂点3-4間が極端にコストが低く、互いに辺を張ろうとした場合、元々(0,N-1)間に辺があるので、(0,N-1)と(3,4)間に辺があるのは、(0,3)(3,4)(4,N-1)間に辺があるのとコストは同じで、かつ登場する頂点間を連結にできる。
同じ要領で全頂点これだけで連結にできる。
こちらはSegTreeすら要らない。

int N;
ll D;
ll A[202020];
ll L[202020],R[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>D;
	ll ret=0;
	FOR(i,N) {
		cin>>A[i];
		ret+=A[i];
		
		L[i]=max((i?L[i-1]:-1LL<<60),i*D-A[i]);
	}
	ret+=(N-1)*D;
	
	for(i=N-1;i>=0;i--) {
		R[i]=min((i<N-1?R[i+1]:1LL<<60),i*D+A[i]);
		if(i>0 && i<N-1) ret+=min(i*D-L[i],R[i]-(i*D));
	}
	
	cout<<ret<<endl;
	
}

まとめ

後者の解法もちらっと思い浮かんだのだけどなぁ。