yukicoder : No.1402 ビル街

考察に割と手間取った。
https://yukicoder.me/problems/no/1402

問題

N+2個のビルが左右一列に並んでいる。
両端のビルは、無限大の高さを持つものとする。
それ以外のビルに任意の高さを割り当てたとする。

各ビルから、左右最寄りの自身以上の高さのビルに対し、通路を設ける。
全ビル対の最短経路の総和を最小化する高さの配置を求めよ。

解法

両端の無限大の高さのビルを除くと、左右の経路が無駄にならない（＝経路長１で移動できるビルが存在する）で、かつ他の頂点が全部経路長２で移動できるとよい。
そこで、2番目と(N+1)番目のビルを無限大よりちょっと小さくしよう。
そして3～N番目のビルを徐々に高くするようにすれば、いずれもビルからも2番目のビルに通路が張られるので条件を満たせる。

int N;
ll D[2020];
int mi=1010;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	D[0]=D[N+1]=2000000000;
	for(i=2;i<=N-1;i++) D[i]=5+i-1;
	D[1]=5+N-1;
	D[N]=5+N;
	FOR(i,N+2) {
		if(i) cout<<" ";
		cout<<D[i];
	}
	cout<<endl;
}

まとめ

わかっちゃえば★2.5でもいいかな…という感じなんだけどね。