Problem Solving Diary #8

BOJ 4008. 특공대

$$S_i = \sum_{1 \le j \le i} A_j $$

$$DP[i] = \max_{0 \le j < i} \left( a(S_i - S_j)^2 + b(S_i - S_j) + c + DP[j] \right)$$

 

이제 위 점화식을 빠르게 계산해 봅시다.

 

$$ \begin{align} DP[i] &= \max_{0 \le j < i} \left( aS_i^2 - 2aS_i S_j + aS_j^2 + bS_i - bS_j + c + DP[j] \right) \\ &= aS_i^2 + bS_i + c + \max_{0 \le j < i} \left( -2aS_i S_j + aS_j^2 - bS_j + DP[j] \right) \end{align}$$

 

위 식은 CHT의 전형적인 형태를 만족하므로, CHT를 이용해 해결할 수 있습니다. $S_i$가 점차 증가하므로 직선의 기울기는 점차 감소하고, 쿼리의 위치는 점점 증가하는 CHT의 가장 쉬운 형태로 $O(N)$에 풀 수 있습니다.

 

BOJ 13261. 탈옥

$DP[i][j]$: $i$번 칸까지 $j$명의 간수를 배치했을 때의 최소 위험도라고 정의합니다. 또한 $S$를 $C$의 누적 합으로 정의합니다. 그러면,

 

$$ \begin{align} DP[i][j] &= \min_{0 \le k < i} \left( DP[k][j-1] + (i - k) (S_i - S_k) \right) \end{align} $$

 

그런데 위 식에서의 비용 함수 $Cost[i][j] = (j-i)(S_j - S_i)$는 Monge Array임을 보일 수 있습니다. 따라서 Divide & Conquer Optimization을 사용하면 문제를 $O(NG \log N)$에 해결할 수 있습니다.

 

BOJ 17705. Memory 2

문제를 요약하면 아래와 같습니다.

• $A$는 0 이상 $N$ 미만의 정수로 이루어진 길이 $2N$의 수열이며, 각 수는 정확히 두 번씩 등장한다.
• 수 사이에는 우리가 알지 못하는 방식으로 대소 관계가 정의되어 있다.
• 두 개의 카드를 고르면, 두 카드에 적혀 있는 수 중 대소 관계상 크지 않은 것을 알 수 있다.
• 모든 카드에 적힌 수를 알아내야 한다.

Subtask 1 (10점)

이 서브태스크에서는 대소 관계를 미리 알고 있고, 쿼리도 매우 많이 쓸 수 있습니다. $i$번 칸에 적힌 카드를 알아내는 방법은 다음과 같습니다. 단순히 $i$번 카드를 다른 모든 카드와 한 번씩 묶어서 쿼리를 날려 봅시다. 이때 돌아오는 대답 중 가장 큰 것이 $i$번 카드에 적힌 수가 됩니다. 이렇게 하면 $O(N^2)$번의 쿼리로 문제를 풀 수 있습니다.

 

Subtask 2 (60점)

배점이 확 늘어난 것으로 보아 난이도가 많이 올라갔음을 짐작할 수 있습니다. 여전히 대소 관계를 알고 있지만, 사용할 수 있는 쿼리 수가 크게 줄어들었습니다. 거의 선형에 해결해야 할 것으로 짐작됩니다. 

 

아무 카드 세 개나 잡은 뒤, 세 카드 사이에 쿼리를 날려 봅시다. 이때 세 수 중 두 수는 무조건 같습니다. 따라서 가능한 결과는 1 1 1 또는 1 1 2와 같은 형태가 됩니다. 1 1 1의 결과를 얻을 경우 세 카드 중 두 개가 1이라는 사실을 알 수 있고, 1 1 2의 결과를 얻을 경우 1 하나의 위치를 확정지을 수 있습니다.

 

문제는 세 카드 중 두 개가 1이라는 사실을 알았을 때, 어느 두 개가 1인지까지 알아낼 수는 없다는 것입니다. 앞에서는 간단하게 1과 2라고 했지만, 작은 것을 $X$, 큰 것을 $Y$라고 해 봅시다. 첫 세 후보 $A_1, A_2, A_3$을 $A_4$와 쿼리를 날려 봅니다. 이때 $A_4$의 범위에 따라 아래와 같은 세 가지 케이스가 생깁니다.

• $A_4 < X$인 경우 세 값 모두 $A_4$가 나오며, 이때 $A_4$의 값이 확정됩니다.
• $X < A_4 < Y$인 경우 $X$ 두 개와 $A_4$ 한 개가 나오며, $X$의 위치 두 곳을 알아낼 수 있습니다.
• $Y \le A_4$인 경우 $X$ 두 개와 $Y$가 나오며, 이때 역시도 $X$의 위치 두 곳을 알아낼 수 있습니다.

위 과정을 요약하면 최악의 경우에도 세 번의 쿼리로 값 하나가 확정됩니다. 여기에서 문제가 끝난다면 좋겠지만... 생각하기도 싫은 코너 케이스가 남아 있습니다. 바로 모르는 값의 개수가 세 개 이하로 줄어들면 위 알고리즘을 더 이상 적용하지 못하는데... 엄청난 케이스 워크로 해결해야 합니다.

 

모르는 값이 한 개인 경우는 카운팅으로 쿼리 없이 구할 수 있습니다. 모르는 값이 두 개인 경우 두 값이 같으면 문제없고, 다르면 쿼리 한 번으로 해결됩니다.

 

모르는 값이 세 개인 경우가 문제인데, $A < B < C$라는 가정 하에 서술합니다.

• A B C가 남았을 경우: 이미 찾은 값들 중에 A, B, C가 하나씩 존재합니다. 이들과 쿼리를 날립니다.
• A A B가 남았을 경우: 이미 찾은 값들 중에 B가 하나 존재합니다. 이것과 쿼리를 날립니다.
• A B B가 남았을 경우: 세 수끼리 서로 쿼리를 날리면 됩니다.

 

Subtask 3 (100점)

서브태스크 2의 풀이에서 사실 수들의 대소 관계는 크게 중요하지 않습니다. 조금만 메커니즘을 바꿔 주면 $6N$번 정도의 쿼리로 모든 수를 찾을 수 있습니다.

 

BOJ 17712. Telegraph

먼저 최종 상태가 어떻게 되어야 가능할지를 생각해 봅시다. $i$번 섬의 수신기가 $j$번 섬을 향하고 있다면 $i \rightarrow j$의 방향 간선이 있다고 생각합시다. 그래프는 항상 방향 간선의 수와 정점의 수가 같은 형태로, 사이클 하나 주변에 여러 트리들이 붙어 있는 "묶음"이 여러 개 존재하는 형태입니다. 하지만 이런 그래프에서 모든 정점 사이를 오고갈 수 있으려면 최종 상태는 하나의 큰 사이클이어야 합니다. 

 

각 섬에는 수신기의 방향을 바꾸는 데 드는 비용 $C_i$가 있는데, 이 비용 $C_i$가 섬에 있다고 생각하지 말고 간선에 있다고 생각합시다. 이때 현재 $N$개의 간선 중 최소 비용을 들여 일부를 지운 뒤, 큰 하나의 사이클을 구축할 수 있게 만드는 방법을 찾으면 됩니다. 일부 간선을 지운 뒤 간선을 추가해 사이클을 구축할 수 있으려면, (특수한 예외 케이스를 제외하고) 간선을 모두 지우고 나서 그래프에

• 사이클이 없어야 하고,
• 모든 정점의 indegree와 outdegree는 1 이하여야 합니다. 사실 outdegree는 1을 넘을 수가 없기 때문에, indegree만 고려해도 됩니다.

 

최소 비용으로 간선을 제거하는 것 대신, 최대 가중치를 가진 간선 집합을 찾는다고 생각해 봅시다. 일단 기본적으로는 한 정점으로 들어오는 간선 중 가장 가중치가 큰 것들만 골라 주는 작업을 반복하면 되는데, 이때 사이클이 생기지 않도록 주의해야 합니다. 사이클이 만들어지는 방법은 사이클 상의 간선을 전부 고르는 것밖에 없으므로, 이런 경우가 되지 않도록 해야 합니다.

 

어차피 각 연결 성분에 대해서는 따로 생각해도 상관없기 때문에, 연결성분이 하나라고 고정해 보겠습니다. 이제 사이클 상의 모든 간선에 대해, 해당 간선을 무조건 선택하지 않는다고 할 때의 최대 가중치 합을 구합니다. 이들 중 가장 작은 것을 고르면 해당 연결 성분에 대한 답이 되고, 각 연결 성분에 대한 답을 모두 합치면 전체 답이 됩니다.

 

BOJ 17713. Dangerous Skating

새로 장애물이 생기는 조건이 없다면 간단한 BFS로 풀리는 문제입니다. 장애물이 생기긴 하지만, 이 장애물은 사실 주인공에게 도움을 주는 장치에 가깝습니다. 예를 들어 오른쪽으로 한 번 갔다가 왼쪽으로 한 번 가면 무조건 오른쪽으로 정확히 한 칸 이동할 수 있기 때문입니다. 따라서, 비용 1을 들이고 한쪽 방향으로 끝까지 가는 것과, 비용 2를 들이고 한 칸 가는 작업만을 이용해 다익스트라를 돌리면 맞습니다.

 

이 두 가지 방법만으로 항상 최적해를 찾을 수 있다는 증명이 어려운데, 손으로 여러 가지 케이스를 해 보면 빙 돌아가는 것보다는 그냥 비용 2로 한 칸 이동하는 것이 항상 더 낫다는 걸 짐작할 수 있습니다.

 

BOJ 17715. Worst Reporter 2

서브태스크 3 (60점)

최종 상태를 생각해 봅시다. 앞 스코어보드의 학생과 뒤 스코어보드의 학생은 일대일 대응 될 텐데, 여기서 두 학생 모두 국적을 바꿀 필요는 없다는 것을 알 수 있습니다. 국적을 같게만 하면 되기 때문에 $C_i$를 $A_i$로 바꾸기만 하면 배열 $A$는 전혀 건드릴 필요가 없다는 사실을 짐작할 수 있습니다. 따라서 배열 $A$는 고정하고 배열 $C$만 바꾸는 방법을 찾아 봅시다.

 

$(B_i, A_i)$ pair와 $(D_i, C_i)$ pair를 함께 정렬합니다. 이제 앞에서부터 원소를 체크해 줍니다. 뽑은 pair가 $(B_i, A_i)$라면, $A_i$ 값의 개수가 하나 늘어난 것이 됩니다. 뽑은 pair가 $(D_i, C_i)$ pair라면, $C_i$의 개수가 하나 줄어들게 됩니다. 그런데 문제는 $C_i$가 한 개도 없거나, 이미 다 사용해 버린 경우입니다. 이때는 불가피하게 다른 것으로 바꿔야 합니다. 어떤 것으로 바꿔야 할까요?

 

greedy한 전략을 사용합시다. 현재 사용할 수 있는 대안은 남은 사람이 한 명이라도 존재하는 국가들 $V_1, V_2, \cdots, V_k$입니다. 이들 중 $V_i$를 제거했다고 합시다. 아직 살펴보지 않은 기록 중에서 국가가 $V_i$인 선수들에 대한 기록이 존재할 수 있습니다. 앞과 같은 방식으로 $A_i$를 만나면 +1, $C_i$를 만나면 -1을 해 주다가 음수가 되는 시점이 생긴다면 이 $V_i$번 국가 학생을 다시 충원해야 합니다. 모든 국가에 대해, 이러한 상황이 가장 나중에 오는 국가로 바꿔 주면 됩니다. 단 지금 이 국가 학생이 한 명이라도 있어야 합니다. 이걸 $O(N^2)$에 짜면 60점이 나옵니다.

 

서브태스크 4 (100점)

이제 시간 복잡도를 줄여 봅시다. 뭔가 자료구조를 이용해야 시간 복잡도가 줄어들 것 같은데, 아직까진 감이 잘 잡히지 않습니다. 이럴 때는 명확하게 무슨 일을 하는 자료구조가 필요한지를 정리해 보는 것이 좋습니다.

 

위의 +1, -1 작업을 그래프로 나타내면 좌표평면 상에 $N$개의 그래프가 있는 모습을 생각할 수 있습니다. 이 그래프를 모두 관리하는 것은 버겁습니다. 언제 $C_i$를 바꿔서 그래프의 형태가 달라질 지 모르기 때문입니다. 우리가 해야 하는 작업을 정리해 보면,

• $i$번 국가만 나타낸 꺾은선 그래프에서 $y$좌표가 $v$ 이하로 떨어지는 $x$좌표 중, $r$ 이상인 최소의 $x$좌표를 구하기
• 이들을 set 같은 자료구조에 관리하며, 그래프에 간단한 수정이 가해졌을 때 위 쿼리를 빨리 구할 수 있으면 될 것 같다.
• 그래프에 가해지는 업데이트의 종류는 어떤 점을 기준으로 그 오른쪽의 y좌표를 모두 1 늘리거나 줄이는 것이다.

저 업데이트를 처리하는 방법은 간단합니다. 그래프는 그대로 두고, 들어오는 쿼리의 값을 바꿔서 생각하는 겁니다. 예를 들어 그래프를 1 낮추는 업데이트가 주어졌다면, 그래프를 실제로 1만큼 낮추는 대신 쿼리의 y좌표를 모두 1 늘려서 생각하면 됩니다. 이렇게 해도 결과는 같습니다.

 

그렇다면 업데이트 처리는 크게 어렵지 않아졌고, 문제는 쿼리에 대한 답을 빠르게 구하는 일입니다. 만약 각 그래프를 따로따로 만들 수 있다면, 세그먼트 트리에서 이분 탐색을 하는 과정을 통해 이 쿼리를 처리할 수 있습니다. 하지만 $N$개 그래프의 $N$개 값을 모두 저장하는 것은 너무 많습니다. 다행히 한 $x$좌표에서 값이 변하는 그래프는 $N$개 중 하나이므로, 값이 변하는 횟수는 다 합쳐서 $N$번 미만입니다. 즉 세그먼트 트리를 만들 때 각각의 트리에 좌표 압축을 수행해 주면 $O(N \log N)$의 시간 복잡도로 문제를 해결할 수 있습니다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF = 1e9;

struct segTree{
    int n;
    vector<int> tree;
    vector<int> indices;

    void init(int i, int l, int r, vector<int>& vec){
        if(l==r){
            tree[i] = vec[l];
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, vec), init(i*2+1, m+1, r, vec);
        tree[i] = min(tree[i*2], tree[i*2+1]);
    }

    void init(vector<int>& vec, vector<int>& idx){
        n = (int)vec.size();
        tree.resize(n*4+1);
        indices = idx;
        init(1, 0, n-1, vec);
    }

    int query(int i, int l, int r, int s, int x){ /// s 이상 index에서 처음으로 x 이하로 떨어지는 지점
        if(r<s || tree[i] > x) return INF;
        if(l==r) return l;
        int m = (l+r)>>1;
        int tmp = query(i*2, l, m, s, x);
        return tmp == INF ? query(i*2+1, m+1, r, s, x) : tmp;
    }

    int query(int s, int x){
        int tmp = query(1, 0, (int)indices.size()-1, lower_bound(indices.begin(), indices.end(), s) - indices.begin(), x);
        if(tmp == INF) return INF;
        return indices[tmp];
    }
} tree[200002];

struct dat{
    int x, y; bool d; /// 0: 진입
    dat(){}
    dat(int x, int y, bool d): x(x), y(y), d(d){}
    bool operator<(const dat &r)const{
        if(y != r.y) return y < r.y;
        return d < r.d;
    }
};

int n;
vector<dat> vec;
int cnt[200002];
int ans;
vector<pair<int, int> > graph[200002];
vector<int> indices[200002];
vector<int> values[200002];
set<pair<int, int> > st;

int offset[200002];

void addToSet(int i, int x){
    int tmp = tree[x].query(i, -offset[x]);
    st.insert(make_pair(tmp, x));
//    printf("Added set %d %d\n", tmp, x);
}

void deleteFromSet(int i, int x){
    int pnt = tree[x].query(i, -offset[x]);
    auto it = st.lower_bound(make_pair(pnt, x));
    assert(it->first == pnt && it->second == x);
//    printf("Deleted set %d %d\n", it->first, it->second);
    st.erase(it);
}

void useOne(int i, int x, int org){
    deleteFromSet(i, x);
    cnt[x]--;
    offset[x]--;
    if(cnt[x]) addToSet(i, x);

    offset[org]++;
    assert(!cnt[org]);
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        vec.push_back(dat(x, y, 0));
    }
    for(int i=1; i<=n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        vec.push_back(dat(x, y, 1));
    }
    sort(vec.begin(), vec.end());

    for(int i=1; i<=n; i++) graph[i].push_back(make_pair(-1, 0));
    for(int i=0; i<n+n; i++){
        graph[vec[i].x].push_back(make_pair(i, graph[vec[i].x].back().second + (vec[i].d ? -1 : 1)));
    }
    for(int i=1; i<=n; i++){
        for(auto p: graph[i]) indices[i].push_back(p.first), values[i].push_back(p.second);
        tree[i].init(values[i], indices[i]);
    }

    for(int i=0; i<n+n; i++){
//        printf("i: %d\n", i);
        if(vec[i].d == 0){
            if(cnt[vec[i].x] == 0) addToSet(i, vec[i].x);
            cnt[vec[i].x]++;
            continue;
        }
        if(cnt[vec[i].x]){
            cnt[vec[i].x]--;
            if(cnt[vec[i].x] == 0) deleteFromSet(i, vec[i].x);
            continue;
        }
        ans++;
        assert(!st.empty());
        int key = st.rbegin()->second;
        useOne(i, key, vec[i].x);
    }
    printf("%d", ans);
}