GCJ R1B는 새벽 1시에 열려서 잠을 포기하고 참가! 했지만.. 컨디션 조절 실패로 (변명) 이번에도 Round 2 진출에 실패하고 말았다. 전체적인 난이도는 A가 너무 쉽고, B가 생각보다 어려웠으며, C는 구현이 상당히 복잡한 문제였다.

  1. Manhattan Crepe Cart
  2. Draupnir
  3. Fair Fight

Manhattan Crepe Cart

Q×Q(1≤Q≤100,000)그리드 상에 있는 P(1≤P≤500)명의 사람의 현재 위치와 이동 방향이 주어졌을 때, 가장 많은 사람의 진행 방향과 겹치는 점의 위치를 찾는 문제이다. 편의상 각 사람은 하나의 반평면이라고 생각하면 된다: 예를 들어 북쪽을 향하고 있을 경우 $y > y_0$ 인 모든 점이 해당 사람의 진행 방향에 있다고 할 수 있고, 동쪽을 향하고 있을 경우 $x > x_0$ 인 모든 점이 해당 사람의 진행 방향에 있다고 할 수 있다.

풀이는 가로 반평면과 세로 반평면을 따로 고려함으로써 각각 $y$와 $x$좌표를 알아낼 수 있다는 것을 떠올리면 간단하다. 우선 가로 반평면을 해결하는 방법을 살펴보자. 이는 간단한 스윕 라인1을 통해 해결할 수 있다.

북쪽을 바라보는 사람을 이벤트 $(y_0 + 1, +1)$으로 나타낼 수 있고, 같은 방법을 이용해서 남쪽을 바라보는 사람 역시 $(y_0, -1)$으로 나타낼 수 있다. 이제 각 이벤트를 처리하면서 가장 많은 사람의 진행 방향과 겹치는 점을 선택하면 끝!

#include<cstdio>
#include<algorithm>
#include<vector>
#define x first
#define y second
#define pb emplace_back
#define ALL(X) (X).begin(),(X).end()
using namespace std;
using ii = pair<int, int>;

int n, m;
vector<ii> p[2];

int sweep(vector<ii>& events, int base) {
    int acnt = base, ret = 0, cnt = base;
    sort(ALL(events));

    for (auto& evt: events) {
        cnt += evt.y;
        if (cnt > acnt) {
            acnt = cnt;
            ret = evt.x;
        }
    }

    return ret;
}

int main()
{
    for (int T, C = scanf("%d", &T); C <= T; ++C) {
        printf("Case #%d: ", C);
        scanf("%d%d", &n, &m);
        p[0].clear();
        p[1].clear();

        int xb = 0, yb = 0;
        for (int i = 0; i < n; i++) {
            int x, y; char d[16];
            scanf("%d%d%s", &x, &y, d);
            if (*d == 'N') {
                p[0].pb(y+1, 1);
            } else if (*d == 'S') {
                ++yb;
                p[0].pb(y, -1);
            } else if (*d == 'E') {
                p[1].pb(x+1, 1);
            } else if (*d == 'W') {
                ++xb;
                p[1].pb(x, -1);
            }
        }

        printf("%d %d\n", sweep(p[1], xb), sweep(p[0], yb));
    }
    return 0;
}

Draupnir

오딘이 $0$번째 날에 6개의 링을 각각 $r_1, r_2, …, r_6$개 가지고 있다고 하자($r_i≤100$). $i$번째 날이 될 때마다, $i|j$, 즉 $i$의 약수인 $j$번째 링이 두 배로 늘어난다. 따라서 $i$번째 날의 각 링의 개수는 각각 $r_1 \cdot 2^{\lfloor{i/1}\rfloor}, r_2 \cdot 2^{\lfloor{i/2}\rfloor}, …$개가 된다. 문제는 $r_1, …, r_6$을 모르는 상태에서 $i$번째 날에 오딘이 가지고 있는 모든 링 개수의 합($\mathrm{mod~} 2^{63}$)을 묻는 질문을 통해 $r_1, …, r_6$을 알아내는 것이다.

풀이의 아이디어는 각 $r_i$가 100보다 작음을 이용, 128진법과 비슷한 아이디어를 통해 합으로부터 각 링의 개수를 분리하는 것이다. 예를 들어 210일 째에 오딘이 가지고 있는 링의 개수를 풀어 쓰면 다음과 같이 표현할 수 있다:

지수를 살펴보면 각각의 차이가 7 이상이기 때문에 합으로부터 $r_4, r_5, r_6$을 얻어낼 수 있다.

마찬가지로 42일 째의 링 개수는 다음과 같이 표현 가능하다. 다행히 이미 $r_4, r_5, r_6$을 알고 있으므로, 아까와 똑같은 방법을 통해 나머지 링의 개수도 구할 수 있다.

def solve3(x, s):
    return [(x >> i) & 127 for i in s]

def solve():
    print(210, flush=True)
    x = solve3(int(input()), [210 // 4, 210 // 5, 210 // 6])

    print(42, flush=True)
    y = int(input()) - sum([x[i] << (42 // (i + 4)) for i in range(3)])

    r = solve3(y, [42 // 1, 42 // 2, 42 // 3]) + x
    print(" ".join([str(x) for x in r]), flush=True)
    if int(input()) == -1: exit(-1)

T, _ = map(int, input().strip().split())
[solve() for C in range(1, T + 1)]

Fair Fight

N(1≤N≤100,000)종류의 검이 각각 여러 자루씩 존재하고, 각 종류별로 찰스와 데릴라가 각각의 검을 선택했을 때의 공격력이 주어진다. 찰스와 데릴라는 각각 자신의 공격력이 최대가 되는 검을 선택한다고 할 때, 선택할 수 있는 검의 종류를 $[L, R]$ 구간으로 제한해서 둘의 공격력 차이가 K이하가 되도록 하는 경우의 수를 구해보자.

보자마자 히스토그램에서 가장 큰 직사각형 찾기가 떠오르는 문제이다. 이를 해결하는 방법에는 여러 가지가 있지만, 여기선 구현은 조금 복잡하지만 아이디어가 간단한 방법인 바이너리 서치를 이용한 풀이를 살펴보자.

구간이 주어졌을 때, 찰스와 데릴라는 각각 가장 큰 공격력($C_i, D_i$)을 갖는 검을 고르게 된다. 이 사실을 이용해서 각각의 검이 찰스(혹은 데릴라)에게 최대의 공격력을 주는 구간을 따로 고려하면 모든 답의 후보를 살펴볼 수 있다.

다음의 테스트 케이스를 살펴보자:

5 4        # K = 4
2 4 4 0 5  # C_i
2 4 4 4 1  # D_i

여기서 각각의 검이 찰스에게 최대의 공격력을 주는 구간은 다음과 같다(각각의 수는 모두 인덱스를 나타낸다).

1 : {1..1..1} # [(1, 1)]
2 : {1..2..4} # [(1, 2), (2, 2), (1, 3), (2, 3), (2, 4)]
3 : {1..3..4} # [(1, 3), (2, 3), (3, 3), (3, 4)]
4 : {4..4..4} # [(4, 4)]
5 : {1..5..5} # [(1, 5), (2, 5), (3, 5), (4, 5), (5, 5)]

왼쪽의 각 구간 별 중괄호 표현은 각 검이 구간 내의 최댓값인 가장 큰 구간을 나타낸다. 이를 구할 때 바로 바이너리 서치를 이용하게 되는데, 검 $i$에 대한 구간을 고려할 때, $[i, j]$ 구간의 최댓값이 $C_i$ 이하라면 $j < k$인 $[i, k]$ 구간의 최댓값 역시 $C_i$ 이하가 되기 때문에 바이너리 서치로 $i$를 중심으로 했을 때 (1)오른쪽 끝과 (2)왼쪽 끝을 따로 구할 수 있다. 이 구간을 $L_i, R_i$라고 하자.

이제 $C_i - K ≤ \mathrm{max}(\{D_j \| L’≤j≤R’\}) ≤ C_i + K$를 만족하는 $L_i ≤ L’ ≤ i ≤ R’ ≤ R_i$ 쌍의 개수를 구하면 검 $i$가 속하는 모든 가능한 구간의 개수를 구할 수 있다.

여기선 부등호의 양 변을 따로 계산하면 편리한데, 우선 $D_j ≤ C_i + K$를 만족하는 $j$의 최대 범위를 아까와 같은 방식으로 찾고, 이를 $L^+, R^+$라고 하자. 그 다음 $D_j ≥ C_i - K$를 만족하는 최대 범위를 찾아 $L^-, R^-$라고 하면 (그런 구간이 존재할 경우) $L_i ≤ L^+ ≤ L^- ≤ i ≤ R^- ≤ R^+ ≤ R_i$가 되고, 이로부터 $L’ = \{L^+, …, L^-\}$, 그리고 $R’ = \{R^-, …, R^+\}$를 찾아 $i$를 중심으로 하는 구간의 개수 $\|L’\| \cdot \|R’\|$를 얻을 수 있다.

여기까진 어렵지 않게 떠올릴 수 있지만, 실제로 구현할 때에는 특정 구간의 최댓값을 빠르게 구하는 구간 최댓값 쿼리2를 이용해야 하고, 같은 공격력을 갖는 검이 여럿 있을 경우 중복되는 구간을 세지 않도록(위의 예제를 보자) 신경써서 구현해야 해서 대회 시간에 해결하기에는 어려운 문제라고 느꼈다.

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
using ll = long long;

struct MaxNode {
    using ReturnType = int;
    int v;
    inline MaxNode(ReturnType v=-1e9): v(v) {}
    inline ReturnType Query() const { return v; }
    inline void Update(const ReturnType& x) { v = x; }
    inline MaxNode Combine(const MaxNode& le, const MaxNode& ri) {
        v = max(le.v, ri.v);
        return *this;
    }
};

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

    inline SegmentTree(int *s, int *e): size(1) {
        int n(e - s);
        while (size <= n || size < 8) size <<= 1;
        nodes = new Node[size<<1];

        for (int i = n; i > 0; i--)
            --e, nodes[i+size].Update(*e);

        for (int i = size - 1; i > 0; i--)
            nodes[i].Combine(nodes[i<<1], nodes[i<<1|1]);
    }

    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; }
};

const int MAXN = 1e5 + 10;
int n, k, a[MAXN], b[MAXN];

template<typename T>
int searchMaxLeft(T & tree, int l, int r, int i, int x) {
    int ret = 1 << 30;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (tree.Query(min(i, mid), max(i, mid)) <= x) {
            ret = min(ret, mid);
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    return ret;
}

template<typename T>
int searchMaxRight(T & tree, int l, int r, int i, int x) {
    int ret = -(1 << 30);
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (tree.Query(min(i, mid), max(i, mid)) <= x) {
            ret = max(ret, mid);
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    return ret;
}

int main()
{
    for (int T, C = scanf("%d", &T); C <= T; ++C) {
        scanf("%d%d", &n, &k);

        for (int i = 1; i <= n; i++) scanf("%d", a + i);
        SegmentTree<MaxNode> tree1(a + 1, a + n + 1);

        for (int i = 1; i <= n; i++) scanf("%d", b + i);
        SegmentTree<MaxNode> tree2(b + 1, b + n + 1);

        ll ans = 0;
        map<int, int> ignore;
        for (int i = 1; i <= n; i++) {
            int j = ignore.count(a[i]) ? ignore[a[i]] + 1 : 1;
            int alb = searchMaxLeft(tree1, j, i, i, a[i]);
            int arb = searchMaxRight(tree1, i, n, i, a[i]);

            int lb = max({alb, searchMaxLeft(tree2, j, i, i, a[i] + k)});
            int rb = min({arb, searchMaxRight(tree2, i, n, i, a[i] + k)});
            if (rb >= lb) ans += (rb - i + 1) *1LL* (i - lb + 1);

            int flb = max({alb, searchMaxLeft(tree2, j, i, i, a[i] - k - 1)});
            int frb = min({arb, searchMaxRight(tree2, i, n, i, a[i] - k - 1)});
            if (frb >= flb) ans -= (frb - i + 1) *1LL* (i - flb + 1);

            ignore[a[i]] = i;
        }
        printf("Case #%d: %lld\n", C, ans);
    }
    return 0;
}

  1. 스윕 라인에 대한 TopCoder 튜토리얼, Baekjoon Online Judge 튜토리얼. ↩

  2. 구간 최댓값 문제를 해결하는 Segment Tree, Sparse Table. ↩