백준 8313번 Sweets

문제 링크

중국의 의문의 블로그에서 풀이를 보고 풀었다. 여기서 찾았다.

Anton, Dmytro, Borys이 각각 받을 사탕의 개수를 $A,B,C$라고 하자. $A\ge B\ge C$를 만족해야 한다. $A-C$를 최소화해야 한다.

$front:=a[1:N/2]$

$back:=a[N/2:N]$

이라고 하자.

$front,back$에서 $A,B,C$에 나누는 $3^{N/2}$개의 경우의 수를 모두 찾아 튜플로 나타내 $(x_i,y_i,z_i)$라고 표현하자. $a_i=x_i-y_i,b_i=y_i-z_i$로 정의하자.

$front$에서 나온 어떤 경우를 $(a_i,b_i)$, $back$에서 나온 어떤 경우를 $(a_j,b_j)$라고 하면 $A-C=(A-B)+(B-C)=a_i+a_j+b_i+b_j$이다. $A\ge B\ge C$조건을 만족하려면 $a_i+a_j\ge 0,b_i+b_j\ge 0$을 만족해야 한다.

$b_i,b_j$값을 좌표압축한 후 $(a_i,b_i)$를 $a_i$가 증가하게 정렬하고 $(a_j,b_j)$를 $a_j$가 감소하게 정렬한 뒤 세그먼트 트리를 사용하여 해결 할 수 있다.

차를 이용해 변수 3개를 2개로 줄이는 아이디어가 인상깊었다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int MAXC = 600000;

ll N, tree[4*MAXC];

void update(int x, ll v, int s = 0, int e = MAXC, int idx = 1)
{
    if(e < x || x < s) return;
    if(s == e) {
        tree[idx] = min(tree[idx], v);
        return;
    }
    int m = (s + e) / 2;
    update(x, v, s, m, 2*idx);
    update(x, v, m+1, e, 2*idx+1);
    tree[idx] = min(tree[2*idx], tree[2*idx+1]);
}

ll query(int l, int r, int s = 0, int e = MAXC, int idx = 1)
{
    if(e < l || r < s) return 1e18;
    if(l <= s && e <= r) return tree[idx];
    int m = (s + e) / 2;
    return min(query(l, r, s, m, 2*idx), query(l, r, m+1, e, 2*idx+1));
}

void dfs(int idx, ll a, ll b, ll c, vector<ll>& A, vector<pair<ll, ll>>& out)
{
    if(idx == A.size()) {
        out.emplace_back(c - b, b - a);
        return;
    }

    dfs(idx + 1, a + A[idx], b, c, A, out);
    dfs(idx + 1, a, b + A[idx], c, A, out);
    dfs(idx + 1, a, b, c + A[idx], A, out);
}

int main()
{
    cin >> N;
    vector<ll> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];
    int m = N / 2;
    vector<ll> front(A.begin(), A.begin() + m), back(A.begin() + m, A.end());
    vector<pair<ll, ll>> front_out, back_out;
    dfs(0, 0, 0, 0, front, front_out);
    dfs(0, 0, 0, 0, back, back_out);
    sort(front_out.begin(), front_out.end());
    sort(back_out.begin(), back_out.end());

    vector<ll> v;
    v.reserve(back_out.size());
    for(auto [a, b] : back_out) v.push_back(b);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    fill(tree, tree + 4*MAXC, 1e18);

    ll ans = 1e18;
    int j = back_out.size() - 1;
    for(int i = 0; i < front_out.size(); i++) {
        while(j >= 0 && front_out[i].first + back_out[j].first >= 0) {
            int idx = lower_bound(v.begin(), v.end(), back_out[j].second) - v.begin();
            update(idx, back_out[j].first + back_out[j].second);
            j--;
        }
        int idx = lower_bound(v.begin(), v.end(), -front_out[i].second) - v.begin();
        ans = min(ans, front_out[i].first + front_out[i].second + query(idx, MAXC));
    }
    cout << ans;
}