AtCoder ARC #070 : E - NarrowRectangles

こういうシンプルな問題設定はいいね。
http://arc070.contest.atcoder.jp/tasks/arc070_c

問題

2次元座標上にN個の矩形がある。
(0-originで)i番の矩形は(i,L[i])-(i+1,R[i])を頂点とする軸に平行な矩形である。

各矩形をX軸方向に任意にスライドできるとする。
全矩形を連結させるのに必要なスライド量の総和の最小値を求めよ。

解法

以下を考える。
dp(i,x) := 0～i番目までの矩形の位置を決めたとき、i番の矩形の左辺のX座標がxである状態のスライド量の総和の最小値

この値は、下記の通りに定まる。

部分点であれば、この処理を愚直に行えばよい。

満点を取るにはもう少し工夫する必要がある。
minを除くと、dp(i,x)は|L[j]-x|の形の式をi個加えたものなので、下に凸となる。
xが極端に大きいときは傾きが(i+1)、逆にxが極端に小さいときは(-i-1)となる。

ここにminを適用したときの形状を考える。
傾きが0の部分が広がり、傾きが負の位置の値は全体的に左にスライドし、正の位置の値は全体的に右にスライドする。

移動量の総和を最小にするには、各矩形は傾きが0となる範囲のxのうち移動量が最小の位置に動かすようにすればよい。

以後、傾きが1変化する点のmultisetを、傾きが正・負のそれぞれで管理していこう。
また、それぞれスライド量の総和を管理する。

各矩形について、以下の手順で処理していく。

• 矩形の横幅から、スライド量を求める。
• 2つのmultisetから、傾きが0の範囲となるxを求め、移動量の最小値を更新。
• |L[i]-x|を加えるということは、位置L[i]に傾きが1変化する点が2個増えることになる。よってこれらを2つ追加する。
  • これにより、今まで傾きが-1だったところが1になることがなど、正負入れ替わることがある。その際はその点を2つのmultiset間で移動しよう。

int N;
int L[101010],R[101010];

multiset<ll> LS,RS;
ll ofl,ofr;
ll ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>L[i]>>R[i];
	
	LS.insert(-1LL<<60);
	RS.insert(1LL<<60);
	
	FOR(i,N) {
		if(i) {
			ofl -= R[i]-L[i];
			ofr += R[i-1]-L[i-1];
		}
	
		if(L[i]<*LS.rbegin()+ofl) ret+=*LS.rbegin()+ofl-L[i];
		else if(*RS.begin()+ofr<L[i]) ret+=L[i]-(*RS.begin()+ofr);
		
		if(L[i]<*LS.rbegin()+ofl) {
			RS.insert(*LS.rbegin()+ofl-ofr);
			LS.insert(L[i]-ofl);
			LS.insert(L[i]-ofl);
			LS.erase(LS.find(*LS.rbegin()));
			
		}
		else if(*RS.begin()+ofr<L[i]) {
			LS.insert(*RS.begin()+ofr-ofl);
			RS.insert(L[i]-ofr);
			RS.insert(L[i]-ofr);
			RS.erase(RS.begin());
		}
		else {
			LS.insert(L[i]-ofl);
			RS.insert(L[i]-ofr);
		}
		
	}
	cout<<ret<<endl;
}

まとめ

図形の形状は思いついたが、それを管理するデータ構造に落とし込めなかった。