Codeforces #761 : Div2 E. Christmas Chocolates

これは本番中に解けているな。
https://codeforces.com/contest/1617/problem/E

問題

distinctな整数列Aが与えられる。
1つ要素A[x]を選び、以下の手順を繰り返してA[x]=A[y]となるようにしたい。

• 2^k≧A[x]となるkを選び、A[x]=2^k-A[x]とする。

処理回数の最小値が最大となる(x,y)の対を求めよ。

解法

この手順は同じ作業を2回行うと元に戻る。
そのため、A[x]をA[y]にするのではなく、A[x]とA[y]に作業を繰り返し、同じ値になるようにしよう。

kの選びかたは、常に最小となるようにする。
そうすると、A[x]は処理毎に半分以下になるので、高々O(log(A[x]))回の作業で0になる。
それぞれ値を列挙して、処理回数の和が最大となる対を求めよう。

int N;
int A[202020];
map<int,vector<pair<int,int>>> V;

int ma,X,Y;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		V[A[i]]={{0,i}};
	}
	int cur=1<<30;
	while(V.size()) {
		auto a=*V.rbegin();
		V.erase(a.first);
		sort(ALL(a.second));
		reverse(ALL(a.second));
		if(a.second.size()>=2) {
			if(a.second[0].first+a.second[1].first>ma) {
				ma=a.second[0].first+a.second[1].first;
				X=a.second[0].second+1;
				Y=a.second[1].second+1;
			}
		}
		auto b=a.second[0];
		b.first++;
		x=a.first;
		if(x==0) break;
		y=1;
		while(y<x) y*=2;
		V[y-x].push_back(b);
	}
	
	cout<<X<<" "<<Y<<" "<<ma<<endl;
	
}

まとめ

よくすんなり思いついたな。