Prob No.066E : 균형잡힌 부분집합 [CH03.4.USACO(Gold)]

Prob No.066E : 균형잡힌 부분집합 [CH03.4.USACO(Gold)]

balanced cow subset
http://koistudy.net/?mid=prob_page&NO=1646
https://www.acmicpc.net/problem/5879

구재현 선배님의 도움으로 푼 문제다.
문제에서 미리 전처리를 해주는 것이 매우 중요하다.

이 방법은 각 원소를 앞의 반은 흰색, 나머지는 갈색으로 칠한다.
만약 집합 S가 균형이 잡혀있으려면…
S의 두 부분집합 A, B의 합이 같아야 한다.
그러면 (A에 있는 갈색 원소의 합) - (B에 있는 갈색원소의 합) = (B에 있는 흰색원소의 합) - (A에 있는 흰색원소의 합)

이 성질을 이용하면 문제를 풀 수 있다.

3^(n/2)의 DFS를 앞의 반과 뒤의 반에 대해서 따로 따로해주며 값을 배열에 저장한다.
DFS시 각 레벨에서 선택은 3가지다. a[i]를 빼거나 더하거나 아무것도 하지 않거나.

이후 inch worm algorithm 처럼 정렬된 두 배열에서 두 포인터의 크기를 비교해주면서 진행한다.
문제는 두 포인터가 가르키는 배열이 같을 경우인데 이건 걍 같은걸 for문 돌리면서 다 봐주면 된다.

나도 이게 왜 시간 안에 통과되는지 이해가 잘되지 않는다.
나도 구사과처럼 정보 잘하고 싶다 ㅠㅠ


소스코드 bal




#include <bits/stdc++.h>
#define N 25
using namespace std;
typedef long long ll;
ll c[N],n,ck[(1<<20)+5],li,ri;
vector<pair<ll,ll> > a,b;
void input(){
    scanf("%lld",&n);
    ll i;
    for(i=1;i<=n;i++)
        scanf("%lld",&c[i]);
    li=n/2;
    ri=n-(n/2+1)+1;
}
void set1(ll lev,ll sum,ll pos){
    if(lev>n/2)
        a.push_back(make_pair(sum,pos));
    else
        set1(lev+1,sum,pos*2),set1(lev+1,sum-c[lev],pos*2+1),set1(lev+1,sum+c[lev],pos*2+1);
}
void set2(ll lev,ll sum,ll pos){
    if(lev>n)
        b.push_back(make_pair(sum,pos));
    else
        set2(lev+1,sum,pos*2),set2(lev+1,sum-c[lev],pos*2+1),set2(lev+1,sum+c[lev],pos*2+1);
}
void output(){
    ll i,lef,rig,ans,tlef,trig,j;
    lef=rig=ans=0;
    while(lef<a.size() && rig<b.size()){
        if(a[lef].first<b[rig].first) lef++;
        else if(a[lef].first>b[rig].first) rig++;
        else{
            tlef=lef;trig=rig;
            while(tlef<a.size() && a[tlef].first==a[tlef+1].first)tlef++;
            while(trig<b.size() && b[trig].first==b[trig+1].first)trig++;
            for(i=lef;i<=tlef;i++)
                for(j=rig;j<=trig;j++)
                    ck[a[i].second*(1<<ri)+b[j].second]=1;
            lef=tlef+1;
            rig=trig+1;
        }
    }
    for(i=0;i<(1<<n);i++)
        if(ck[i]==1)
            ans++;
    printf("%lld",ans-1);
}
int main(){
    input();
    set2(n/2+1,0,0);
    set1(1,0,0);
    sort(b.begin(),b.end());sort(a.begin(),a.end());
    output();
}