Codeforces LATOKEN Round 1 : G. A New Beginning

一転してコードは短い。
https://codeforces.com/contest/1534/problem/G

問題

2次元座標で第1象限の中でN個の座標にそれぞれ芋がある。
ここで、プレイヤーは原点から右または上の隣接する格子点に移動していくものとする。

途中、プレイヤーは芋を回収できる。
その際、プレイヤーが(x,y)にいて芋が(X,Y)にある場合、max(|X-x|,|Y-y|)のエネルギーを消費する。
最適な移動経路と回収タイミングを選ぶ場合、全芋を回収する総エネルギーの最小値を求めよ。

解法

各点の座標を45度右に回転して√2倍する。
プレイヤーは、(x,y)→(x+1,y+1)か(x+1,y-1)に移動することになるし、(X,Y)の芋を回収するタイミングは、プレイヤーが(X,y)にいるときに|Y-y|/2のエネルギーを消費することになる。

これは、Slope Trickの要領で、現在のY座標におけるこれらのエネルギーの総和を管理できるので、その最小値を取ろう。

int N;
int X[1010100],Y[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<pair<ll,ll>> ev;
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		ev.push_back({x+y,y-x});
	}
	sort(ALL(ev));
	ll ret=0;
	priority_queue<ll,vector<ll>,greater<ll>> U;
	priority_queue<ll,vector<ll>,less<ll>> D;
	U.push(0);
	D.push(0);
	FORR2(x,y,ev) {
		// 傾きがマイナスとなるy座標の最大値からの距離と、傾きがプラスとなるy座標の最小値からの距離
		ret+=max({0LL,D.top()-x-y,y-(U.top()+x)});
		if(U.empty()||U.top()+x>y) {
			//追加は傾きが0かマイナスのところ
			D.push(x+y);
			D.push(x+y);
			U.push(D.top()-2*x);
			D.pop();
		}
		else {
			//追加は傾きがプラスのところ
			U.push(y-x);
			U.push(y-x);
			D.push(U.top()+2*x);
			U.pop();
		}
		
	}
	cout<<ret/2<<endl;
}

まとめ

Slope Trick、コードは難しくないんだけどいつも実装に戸惑う。