こっちはすんなり。
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最終問題。