kmjp's blog

競技プログラミング参加記です

AtCoder ABC #254 : Ex - Multiply or Divide by 2

こっちはすんなり。
https://atcoder.jp/contests/abc254/tasks/abc254_h

問題

2つのN要素の非負整数の多重集合A,Bが与えられる。
Aから1つ要素を選び、2倍にするか半分(端数は切り下げ)する処理を繰り返しAをBに一致できるか。
できるなら、処理回数の最小値を求めよ。

解法

Aの要素を2倍する代わりに、Bの要素を(偶数なら)半分にしても同じであることに着目する。

Aが空になるまで、以下の手順を繰り返そう。

  • Aの最大値とBの最大値が一緒なら、両方1個ずつ取り除く。
  • Aの最大値がBの最大値より大きいなら、それを半分にする。
  • Bの最大値がAの最大値より大きいなら、それを半分にする。ただし、半分にする前の値が奇数なら、AはBに一致させられない。
int N;
multiset<int> A,B;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		A.insert(x);
	}
	FOR(i,N) {
		cin>>x;
		B.insert(x);
	}
	ll ret=0;
	while(A.size()) {
		if(*A.rbegin()==*B.rbegin()) {
			x=*A.rbegin();
			A.erase(A.find(x));
			B.erase(B.find(x));
			continue;
		}
		else if(*A.rbegin()>*B.rbegin()) {
			ret++;
			x=*A.rbegin();
			A.erase(A.find(x));
			A.insert(x/2);
		}
		else {
			ret++;
			x=*B.rbegin();
			if(x%2) break;
			B.erase(B.find(x));
			B.insert(x/2);
		}
	}
	
	if(A.size()) {
		cout<<-1<<endl;
	}
	else {
		cout<<ret<<endl;
	}
	
}

まとめ

久々に軽めのABC最終問題。