Google Kick Start 2019 Round B

오늘 오전에는 Kick Start Round B가 있었다. 난이도는 Round A처럼 역시 어려웠다(ㅠㅠ). 다만 각 문제가 다이나믹 프로그래밍, 그리디, 그리고 라인 스위핑 등 기본적인 알고리즘의 의미를 충실하게 고민하면 풀 수 있는 구성으로, PS를 다시 연습하기에 훌륭한 대회였다.

Building Palindromes
Energy Stones
1. Test Set 1
2. Test Set 2
Diverse Subarray

Building Palindromes

알파벳 대문자로 이루어진 문자열 S(1≤|S|≤100,000)와 Q개의 독립적인 쿼리 [L, R]이 주어졌을 때, 각 쿼리에 대해 문자열 조각 S[L:R+1]을 재배열하여 팰린드롬을 만들 수 있는지 확인하는 문제이다.

이는 간단하게 구간 안에 존재하는 각 알파벳의 개수를 세어 확인할 수 있다. 홀수 개 존재하는 알파벳이 1개인 경우에는 해당 알파벳을 가운데에 놓음으로써 팰린드롬을 만들 수 있지만, 이러한 알파벳이 여럿 존재하면 팰린드롬을 만들 수 없으므로 간단히 해결 가능하다.

#include<cstdio>
#include<cstring>
const int MAXN = 1e5 + 10;

char s[MAXN]{};
int d[26][MAXN]{}, n, q;
int main()
{
    for (int T, C = scanf("%d", &T); C <= T; ++C) {
        printf("Case #%d: ", C);
        scanf("%d%d%s", &n, &q, s + 1);
        memset(d, 0, sizeof d);
        for (int k = 0; k < 26; k++) {
            for (int i = 1; i <= n; i++)
                d[k][i] = d[k][i-1] + (s[i] - 'A' == k);
        }
        int ans = 0;
        while (q--) {
            int l, r;
            scanf("%d%d", &l, &r);
            int odd = 0;
            for (int k = 0; k < 26; k++)
                odd += (d[k][r] - d[k][l-1]) % 2;
            ans += odd < 2;
        }
        printf("%d\n", ans);
    }
    return 0;
}

돌 몬스터가 점심으로 N(1≤N≤100)개의 에너지 스톤을 먹으려 한다. 각 에너지 스톤은 S, E, L의 값을 갖는데, 돌을 소화시키는 데에 S(1≤S≤100)만큼의 시간이 걸리고, 돌을 시간 0에 먹을 경우 E만큼의 에너지를 얻을 수 있다. 그리고 시간이 1만큼 지날 때 마다 L만큼 돌의 에너지가 줄어들어 결과적으로 시간 T에 돌을 먹을 경우 max(0, E - L * T)만큼의 에너지를 얻고, 먹는 데에는 시간이 걸리지 않지만, 소화시키는 데에 S만큼 걸려 T = T + S가 된다.

Test Set 1

이 데이터 셋에서는 모든 돌의 S가 같으므로 각 돌을 먹는 데에 걸리는 시간을 1이라고 간단히 생각할 수 있다. 따라서 먹을 돌의 집합이 “이미 결정된 상태” 에서는 L이 큰 것부터 순서대로 먹느 것이 최적인데, 그럼 먹을 돌의 집합은 어떻게 구해야 할까?

순서를 고정한 상태에서 최적의 부분집합을 선택하는 것은 0-1 냅색을 이용해서 쉽게 해결할 수 있다. 즉, 주어진 돌을 미리 L이 감소하는 기준으로 정렬해 두고 냅색을 이용하면 최적의 순서로 선택했을 때 부분 집합이 갖는 에너지의 합을 구할 수 있다.

Test Set 2

S가 다를 수 있으므로 아까보다 복잡해진 기분이 든다. 하지만, 결국 단위 시간당 줄어드는 에너지의 양, 즉 L' = L / S를 생각해 보면 아까와 별로 다를 것이 없음을 알 수 있다.

#include<cstdio>
#include<cstring>
#include<tuple>
#include<vector>
#include<algorithm>
#define pb emplace_back
#define ALL(X) (X).begin(),(X).end()
using namespace std;

const int MAXN = 111;
int n, s[MAXN], l[MAXN], e[MAXN];

int solve() {
    vector<tuple<int, int, int>> v;
    for (int i = 0; i < n; i++) {
        v.pb(min(l[i], e[i]), s[i], e[i]);
    }

    sort(ALL(v), [](const auto& p, const auto& q) {
        return get<0>(p) * get<1>(q) > get<0>(q) * get<1>(p);
    });

    for (int i = 0; i < n; i++) {
        tie(l[i], s[i], e[i]) = v[i];
    }

    int d[MAXN * MAXN]{}, maxt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = maxt; j >= 0; j--) {
            int val = max(0LL, e[i] - j *1LL* l[i]);
            d[j + s[i]] = max(d[j + s[i]], d[j] + val);
        }
        maxt += s[i];
    }

    return *max_element(d, d + ++maxt);
}

int main()
{
    for (int T, C = scanf("%d", &T); C <= T; ++C) {
        printf("Case #%d: ", C);
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d%d%d", s + i, e + i, l + i);
        }
        printf("%d\n", solve());
    }
    return 0;
}

Diverse Subarray

길이 N(1≤N≤100,000)의 정수 배열이 주어진다. 배열의 각 원소 A[i]가 장식품의 종류를 나타낼 때, 이 배열에서 가장 많은 원소가 포함된 연속한 부분 배열을 선택하는 문제이다. 여기까진 간단해 보이지만, 조금 특이한 제한 조건이 있다: 각 종류별 장식품을 S개 보다 많이 선택할 경우, 해당 종류는 모두 압수당해서 0개가 되어버린다는 것이다.

테스트 셋 1은 N의 제한 조건이 1≤N≤1,000 이므로 모든 부분 배열을 순회하여 해결할 수 있다. 한편, 테스트 셋 2의 경우에는 그렇게 간단히는 해결할 수 없다. 즉, 모든 부분 배열을 확인하지 않고 최적의 부분 배열을 찾아야 한다.

우선 테스트 셋 1번을 해결하는 알고리즘을 ‘조금 복잡하게’ 만들어 보자.

1	1	4	1	4	4
+1	+1	+1	-2	+1	-2

위쪽 행은 예제 수열, 그리고 아래는 S = 2인 경우 각각의 원소까지 선택했을 때 부분 배열 안에 남게 되는 장식품의 수의 변화값을 나타낸다. 즉, 맨 앞의 1만 선택하면 (0) + 1 = 1개가 남고, 네 번째 원소까지 고를 경우 (0) + 1 + 1 + 1 - 2 = 1개가 남는다. 이렇게 시작점이 맨 앞으로 고정돼 있는 경우의 최적 부분 배열은 3번째 원소까지 고른 것(=3)임을 알 수 있다.

1	1	4	1	4	4
±0	+1	+1	+1	+1	-2

이번엔 부분 배열의 시작 위치를 한 칸 옮긴 상태를 생각해 보자. 이 경우의 최적 부분 배열은 다섯 번째 원소까지(=4)가 된다.

여기서 눈여겨 봐야 할 것은 시작 점을 바꿀 때 바뀐 부분(파란 색) 이다. 시작 점이 바뀌더라도 실제로 갱신해야 할 값은 이전 시작 점과 같은 값을 갖는 S번째, 그리고 S + 1번째 값 뿐임을 알 수 있다.

이를 바탕으로 다시 코드를 작성해 보면 다음과 같다.

#include<cstdio>
#include<map>
#include<deque>
#include<vector>
#include<algorithm>
#define sz size()
#define pb emplace_back
using namespace std;
const int MAXN = 1e5 + 10;

int n, s;
int a[MAXN];

int main()
{
    for (int T, C = scanf("%d", &T); C <= T; ++C) {
        printf("Case #%d: ", C);
        scanf("%d%d", &n, &s);
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
        }

        map<int, deque<int>> d;
        vector<int> v(MAXN, 0);
        for (int i = 1; i <= n; i++) {
            auto & q = d[a[i]];
            v[i] = q.sz == s ? -s : q.sz > s ? 0 : 1;
            q.pb(i);
        }

        int ans = 0;
        for (int b = 1; b <= n; b++) {
            int ptr[MAXN]{}, cur = 0;
            for (int e = b; e <= n; e++) { // can be eliminated
                cur += v[d[a[e]][ptr[a[e]]++]];
                ans = max(ans, cur);
            }
            if (d[a[b]].sz > s) v[d[a[b]][s]] = 1;
            if (d[a[b]].sz > s + 1) v[d[a[b]][s+1]] = -s;
            d[a[b]].pop_front();
        }

        printf("%d\n", ans);
    }
    return 0;
}

결과적으로 이렇게 구하더라도 여전히 시간 복잡도는 배열 길이의 제곱에 비례한다. 하지만, 이제 코드에서 시간을 줄일 수 있는 부분이 확실하게 보인다: 바로 합을 구하는 루프!

이는 세그먼트 트리와 같은 자료 구조를 이용하여 원소 수의 로그에 비례하는 시간에 구할 수 있다. 더욱이, 시작점이 바뀔 때 마다 업데이트 하는 연산 역시도 로그 시간에 수행할 수 있다. 따라서 모든 시작점에 대해 최적 부분 배열을 로그 시간에 구할 수 있으므로 총 시간 복잡도는 $O(n\log{n})$이 된다.

#include<cstdio>
#include<map>
#include<deque>
#include<vector>
#include<algorithm>
#define sz size()
#define pb emplace_back
using namespace std;
const int MAXN = 1e5 + 10;

struct PrefixSumNode {
    typedef int ReturnType;
    ReturnType sum, prefix;
    inline PrefixSumNode(ReturnType x=0): sum(x), prefix(x) {}
    inline ReturnType query() const { return prefix; }
    inline void update(const ReturnType& x) { sum = prefix = x; }
    inline PrefixSumNode combine(const PrefixSumNode& le, const PrefixSumNode& ri) {
        sum = le.sum + ri.sum;
        prefix = max(le.prefix, le.sum + ri.prefix);
        return *this;
    }
};

template<class Node>
struct SegmentTree {
    typedef typename Node::ReturnType T;
    Node *nodes;
    int size;

    inline SegmentTree(int n): size(1) {
        while (size <= n || size < 8) size <<= 1;
        nodes = new Node[size<<1];
    }

    inline void update(int p, const T& v) {
        nodes[size+p].update(v);
        for (p += size; p > 1; p >>= 1) {
            int parent = p >> 1, le = p, ri = p;
            if (p&1) le = p ^ 1;
            else ri = p ^ 1;
            nodes[parent].combine(nodes[le], nodes[ri]);
        }
    }

    inline T query(int l, int r) const {
        Node le, ri, tmp;
        for (l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) le = tmp.combine(le, nodes[l++]);
            if (r & 1) ri = tmp.combine(nodes[--r], ri);
        }
        return tmp.combine(le, ri).query();
    }

    inline ~SegmentTree() { delete[] nodes; }
};

int n, s;
int a[MAXN];

int main()
{
    for (int T, C = scanf("%d", &T); C <= T; ++C) {
        printf("Case #%d: ", C);
        scanf("%d%d", &n, &s);
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
        }

        map<int, deque<int>> d;
        SegmentTree<PrefixSumNode> tree(n);
        for (int i = 1; i <= n; i++) {
            auto & q = d[a[i]];
            tree.update(i, q.sz == s ? -s : q.sz > s ? 0 : 1);
            q.pb(i);
        }

        int ans = 0;
        for (int b = 1; b <= n; b++) {
            ans = max(ans, tree.query(b, n));
            if (d[a[b]].sz > s) tree.update(d[a[b]][s], 1);
            if (d[a[b]].sz > s + 1) tree.update(d[a[b]][s+1], -s);
            d[a[b]].pop_front();
        }

        printf("%d\n", ans);
    }
    return 0;
}

Building Palindromes

Energy Stones

Test Set 1

Test Set 2

Diverse Subarray