F - Candy Redistribution 解説
by 
balakrishnan_v
First lets discard the cases where the sum is not divisible by N. Now if the sum is divisible by N, it is always possible to divide equally. Let \(L\) be the set of children who have more candies and \(R\) be the set of children who have less candies.
Lets first solve this greedily:
- First sort \(L\) in ascending order of surplus candies. Similarly, sort \(R\) in ascending order of deficit candies.
- Now consider the greedy way to distributing where we given candies from the child with the current fewest surplus to the current fewest deficit until either of them reaches the target.
- At each step, either the left child reaches target, or right child reaches target or both reach target. In the end where one child is left on each side, by construction both have the same candies which finish in one operation. Hence the distribution of candies form a tree structure and there are atmost \(|L|+|R|-1\) operations to satisfy everyone. Now we can only go fewer.
The only way to get better than this greedy is to have a forest instead of a tree to connect the children from left to right. Once it becomes a forest, we can have partitions of L and R as \(L',L \setminus L'\) and \(R',R \setminus R'\) such that we can distribute from \(L'\) to \(R'\) and \(L \setminus L'\) to \(R \setminus R'\). So iterate over each non-empty subset \(L' \subset L\) and subset \(R' \subset R\) such that their sums are the same and compute the answer for \((L',R')\) and \((L\setminus L',R\setminus R')\) and update the current answer with the sum of the two. If there is no \((L',R')\) such that sum(L’)==sum(R’), the best way is to do the greedy distribution for the current L and R as described above.
This can be posed as a dp which can be solved in O( 2^N) states.
Code
#include <bits/stdc++.h>
using namespace std;
bool HasBit(int mask, int bit) {
return (mask & (1<<bit)) != 0;
}
vector<vector<int>> dp;
vector<vector<pair<int,int>>> best_next_pair;
vector<int> sum_delta1, sum_delta2;
int Solve(int mask1, int mask2, const vector<int>& delta1, const vector<int>& delta2) {
int N1 = delta1.size();
int N2 = delta2.size();
if (mask1==0) return 0;
if (dp[mask1][mask2]!=-1) {
return dp[mask1][mask2];
}
vector<int> V, W;
for(int i=0;i<N1;i++) {
if (HasBit(mask1,i)) {
V.push_back(delta1[i]);
}
}
for(int i=0;i<N2;i++) {
if (HasBit(mask2,i)) {
W.push_back(delta2[i]);
}
}
sort(V.begin(),V.end());
sort(W.begin(),W.end());
int i = 0;
int j = 0;
int ans = 0;
while(i<V.size() && j<W.size()) {
// i and j
int mn = min(V[i], W[j]);
V[i]-=mn;
W[j]-=mn;
ans++;
if (V[i]==0) i++;
if (W[j]==0) j++;
}
pair<int,int> nxt_pair = {-1,-1};
for(int submask1=mask1;submask1!=0;submask1=(submask1-1)&mask1) {
for(int submask2=mask2;submask2!=0;submask2=(submask2-1)&mask2) {
if (submask1==mask1 && submask2==mask2) continue;
if (sum_delta1[submask1]!=sum_delta2[submask2]) continue;
int res1 = Solve(mask1^submask1, mask2^submask2, delta1, delta2);
int res2 = Solve(submask1, submask2, delta1, delta2);
int curr = res1 + res2;
if (curr < ans) {
ans = curr;
nxt_pair = {submask1, submask2};
}
}
}
best_next_pair[mask1][mask2] = nxt_pair;
return dp[mask1][mask2] = ans;
}
vector<tuple<int,int,int>> GetPairings(int mask1, int mask2, const vector<int>& delta1, const vector<int>& delta2) {
int N1 = delta1.size();
int N2 = delta2.size();
pair<int,int> nxt_pair = best_next_pair[mask1][mask2];
if (nxt_pair.first == -1 && nxt_pair.second == -1) {
vector<pair<int,int>> V, W;
for(int i=0;i<N1;i++) {
if (HasBit(mask1,i)) {
V.push_back({delta1[i],i});
}
}
for(int i=0;i<N2;i++) {
if (HasBit(mask2,i)) {
W.push_back({delta2[i],i});
}
}
sort(V.begin(),V.end(), [](pair<int,int> a, pair<int,int> b) {
return a.first < b.first;
});
sort(W.begin(),W.end(), [](pair<int,int> a, pair<int,int> b) {
return a.first < b.first;
});
int i = 0;
int j = 0;
int ans = 0;
vector<tuple<int,int, int>> curr_pairing;
while(i<V.size() && j<W.size()) {
// i and j
int mn = min(V[i].first, W[j].first);
V[i].first-=mn;
W[j].first-=mn;
curr_pairing.push_back({V[i].second, W[j].second, mn});
ans++;
if (V[i].first==0) i++;
if (W[j].first==0) j++;
}
return curr_pairing;
}
auto res1 = GetPairings(mask1^nxt_pair.first, mask2^nxt_pair.second, delta1, delta2);
auto res2 = GetPairings(nxt_pair.first, nxt_pair.second, delta1, delta2);
res1.insert(res1.end(), res2.begin(), res2.end());
return res1;
}
int main() {
int N;
cin>>N;
vector<int> A(N);
for(int i=0;i<N;i++) cin>>A[i];
int s = accumulate(A.begin(), A.end(), 0);
if (s%N != 0) {
cout<<-1<<endl;
return 0;
}
vector<int> delta1, delta2;
vector<int> left_ids_to_orig, right_ids_to_orig;
for(int i=0;i<N;i++) {
if (A[i]>s/N) {
delta1.push_back(A[i]-s/N);
left_ids_to_orig.push_back(i);
} else if (A[i]<s/N) {
delta2.push_back(s/N - A[i]);
right_ids_to_orig.push_back(i);
}
}
int N1 = delta1.size();
int N2 = delta2.size();
sum_delta1 = vector<int>(1<<N1, 0);
for(int mask=0;mask<(1<<N1);mask++) {
int sum = 0;
for(int i=0;i<N1;i++) {
if (HasBit(mask,i)) {
sum += delta1[i];
}
}
sum_delta1[mask] = sum;
}
sum_delta2 = vector<int>(1<<N2, 0);
for(int mask=0;mask<(1<<N2);mask++) {
int sum = 0;
for(int i=0;i<N2;i++) {
if (HasBit(mask,i)) {
sum += delta2[i];
}
}
sum_delta2[mask] = sum;
}
if (N1==0 && N2==0) {
cout<<0<<endl;
return 0;
}
int mask1 = (1<<N1)-1;
int mask2 = (1<<N2)-1;
dp = vector<vector<int>>(1<<N1, vector<int>(1<<N2, -1));
best_next_pair = vector<vector<pair<int,int>>>(1<<N1, vector<pair<int,int>>(1<<N2, {-1,-1}));
int ans = Solve(mask1, mask2, delta1, delta2);
cout<<ans<<endl;
vector<tuple<int,int,int>> pairings = GetPairings(mask1, mask2, delta1, delta2);
for(auto p: pairings) {
int i, j, cnt;
tie(i, j, cnt) = p;
printf("%d %d %d\n", left_ids_to_orig[i]+1, right_ids_to_orig[j]+1, cnt);
}
}
投稿日時:
最終更新: