Codeforces Global Round 3 : E. Earth Wind and Fire

これもDiv2EやDiv1C相当の配置にしては簡単かも。
https://codeforces.com/contest/1148/problem/E

問題

1次元座標において、N個の石が座標S[i]におかれている。
ここで、２つの石を選択し、両者の位置を同じだけ内側に動かす、ということを行う。
すなわちS[i]＜S[j]の関係にある石i,jを選んだ時、S[i]をd大きい位置に動かし、S[j]をd小さい位置に動かす。
(dは正整数で、移動後S[i]≦S[j]を保てる範囲で動かす)

最終的にN個の石がT[i]の位置に来るような動かし方があればそれを構成せよ。
なお、Tにおける石番号の並び順は問わず、座標だけ一致すればよい。

解法

この移動は、石の座標の総和は変えないのでsum(S)=sum(T)であることは確認しておこう。
次に石を座標順にソートしておいたものとする。
その後、S[i]をT[i]に動かすことを考えよう。

座標を大きくしなければならないものと、小さくしなければならないものに分ける。
前者と後者を対応付けて動かすようにすればよい。

前者のグループについて、今いる座標の小さい順に処理していこう。
この時、座標を大きくする方向に動かしたいので、今後小さくする方向に動かしたい石のうち、座標が今見ている石より大きい中で最小のものを選択する、ということを繰り返せばよい。
適切な石が無い場合、解なしとなる。

int N;
ll S[303030],T[303030];
ll D;
pair<ll,int> P[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>S[i];
		D+=S[i];
		P[i]={S[i],i};
	}
	FOR(i,N) cin>>T[i], D-=T[i];
	sort(T,T+N);
	if(D) {
		cout<<"NO"<<endl;
		return;
	}
	sort(P,P+N);
	vector<int> R;
	set<pair<int,int>> L;
	FOR(i,N) {
		if(P[i].first>T[i]) L.insert({P[i].first,i});
		if(P[i].first<T[i]) R.push_back(i);
	}
	vector<vector<int>> ret;
	reverse(ALL(R));
	FORR(r,R) {
		
		while(P[r].first<T[r]) {
			auto it=L.lower_bound({P[r].first+1,0});
			if(it==L.end()) {
				cout<<"NO"<<endl;
				return;
			}
			x=it->second;
			L.erase(it);
			ll mi=min({T[r]-P[r].first,P[x].first-T[x],(P[x].first-P[r].first)/2});
			ret.push_back({P[r].second+1,P[x].second+1,(int)mi});
			P[r].first+=mi;
			P[x].first-=mi;
			
			if(P[x].first!=T[x]) L.insert({P[x].first,x});
		}
	}
	
	_P("YES\n");
	_P("%d\n",ret.size());
	FORR(r,ret) {
		_P("%d %d %d\n",r[0],r[1],r[2]);
	}
	
}

まとめ

これだけ前の問題だとだいぶ忘れるな…。