BOJ 10847, APIO 2015 2 - Jakarta Skyscraper

출처 : 2015 Asia-Pacific Informatics Olympiad Problem 2

백준 번역명 "자카르타의 마천루"

난이도 : Diamond 3

 

1. 문제 설명

0번부터 $m-1$ 번까지의 번호를 가진 "도게" 가 있고, 이 도게들은 1 시간 만에 $+p$ 또는 $-p$ 만큼씩 점프할 수 있다. 도게끼리 만나면 소식을 전달할 수 있고, 소식을 이미 전달받은 도게만 움직일 수 있다.

1번 도게가 소식을 전달받는 최단 시간을 찾는 문제.

 

2. 풀이 설명

[36점, 57점 풀이 : Dijkstra]

최단 시간 (가중치가 주어질 때, 최단 경로)를 찾는 문제이고, 음수 간선이 없으며, $n \leq 30,000$개의 빌딩을 오가야 한다는 점에서 다익스트라 알고리즘을 이용해 보자는 생각을 할 수 있다. 즉, $b$ 번 건물에서 시작한 도게는 $b+p$ 번에 1 시간 만에 갈 수 있고, $b+2p$ 번 건물에 2 시간만에, $b-3p$ 에는 3시간 만에 갈 수 있다. 이를 모두 가중치를 가지는 간선으로 생각할 수 있고, 도게가 도착한 점에서는 일단 (어차피 손해보는게 없으므로) 그 자리에 서있는 모든 도게를 깨워서 보내는 식으로 생각해 보자. 

이렇게 하면, 간선을 모두 만들어서 Graph Construction 하는 작업을 BFS나 DFS를 이용해서 진행할 수 있다. 한 도게마다 간선은 최대 $n / p_i$ 개 만큼 만들어야 하고, 도게가 총 $m$명이므로 이 알고리즘은 총 $n$ 개 의 정점과 $mn$ 개의 간선에서 다익스트라를 돌리는 셈이 된다. 

다익스트라 알고리즘은 구현에 따라 약간의 차이가 있으나 $O(E \log V)$를 쓰는데 이 문제에서는 $O(nm \log nm)$ 이므로 어느쪽을 쓰든 36점까지는 받을 수 있다.

21점짜리 부분문제 4를 보면, 건물 숫자에 비해 도게가 엄청 많다. 굳이 한 지점에 2마리의 도게가 같은 $p$를 가진 채로 앉아있을 이유가 없다. (어차피 한마리만 움직여도 되니까) 이런 부분들을 쳐내면 최대 에지가 $n^2$ 개 이하로 줄어들게 된다. 어차피 100점을 받을 수는 없지만, 57점을 받기 위해서는 $m$ 에 대한 항을 줄여야 한다. 

이렇게 하면 $O(n^2 \log n^2)$ 까지 복잡도를 줄일 수 있고, 이는 57점을 받기에 충분하다.

 

[100점 풀이 : Dijkstra with Cutting]

기본적인 아이디어는 그대로 가져가되, 커팅을 통해 문제를 해결해 보자. 

만약, 2번 정점에서 시작한 도게 $D$가 한번에 3씩 뛰어 가는데, 8번에서 $p = 3$ 인 다른 도게 $D'$ 를 만난다고 생각해 보자. 이때, $D$가 더이상 오른쪽으로 가는 것은 의미가 없다. 왜냐면, 어차피 $D'$도 오른쪽으로 가야 하므로, 도게가 이미 출발한 후에는 $p$ 가 같은 도게는 한명만 움직여도 되고, 

- 도게 $D$ 가 어떤 시간 $t$만큼 걸려서 오른쪽으로 간 다음, $t'$ 만큼 더 오른쪽으로 가는 것

- 도게 $D$ 가 어떤 시간 $t$만큼 걸려서 오른쪽으로 간 다음 멈추고, 그자리에서 $D'$ 가 $t'$ 만큼 가는 것

이 두 상황을 구분할 수 없기 때문이다. 

DFS를 이용해서 간선을 만들다가, 이런 상황을 만나게 되면 커팅해 주는 방식을 생각해 볼 수 있다. 이렇게 커팅을 쓰기로 생각했다면 57점 풀이와 크게 다르지 않다. 

 

이 풀이는 $O(nm \log nm)$ 에 약간 최적화를 해서 돌리는 것처럼 생각할 수 있지만, 사실은 시간 복잡도가 이 커팅을 통해 실제로 줄어든다는 사실을 증명할 수 있다. 

 

Proof of Time Complexity

전체 에지의 개수가 많아야 $O(n \sqrt n)$ 개임을 증명하자. 이러면 전체 시간 복잡도가 $O(n \sqrt n \log (n \sqrt n)$ 이면 점근적으로 $O(n \sqrt{n} \log n)$ 이므로 $n = 30,000$ 에서 통과하는 것이 충분히 납득 가능하다.

 

$k$ 만큼 뛰는, 즉 $p = k$ 인 도게가 $f(k)$ 마리 있다고 생각하자. 이때, 이 $f(k)$ 마리의 도게가 어떻게 잘 위치하든, 실제로 유의미한 도게는 최대 $k$ 마리 이하이다. 만약 $k$ 보다 많은 숫자가 있다면, 항상 모듈러 $k$ 의 값이 겹치게 되어서, 출발 위치를 $k$ 로 모듈러한 값마다 도게가 1마리씩만 있으면 충분하기 때문이다. 

유효한 도게 1마리 (유효한 도게는, 위의 커팅을 통해 합쳐진 이후, 0부터 3만까지의 모든 뛸 수 있는 위치를 다 뛰는 도게를 유효하다고 정의하자) 가 주는 에지의 개수는 자명하게 $n / k$ 개이다. 따라서, 전체 에지의 개수는 

$$\sum_{k = 1}^{n} \frac{n}{k} \min(f(k), k)$$ 만큼 있게 된다.

이 식을 $\sum_{k = 1}^{n} f(k) = n$ 조건을 지키면서 최대화한다고 (즉, 가장 에지가 많은 입력을 만든다고) 생각해 보자. 이때, 최대한 앞부분에 도게 마릿수를 몰아주는게 이득임을 보이자.

 

대략적인 스케치는 exchange argument 같이 생각하면 된다. 

$f(a) < a$ 이고, $a < b$ 인 $b$ 중에 $b > 0$ 이라고 생각해 보자. 그러면, 뒤쪽 $b$의 도게 1마리는 $n / b$ 개의 간선을 주지만, 이 도게를 $f(a)$ 를 늘리는 데 쓰면 $n / a$ 개가 되므로, 항상 이득이다.

 

그런데 이렇게 $f(k) = k$ 가 되게 딱딱 맞춰 채우면서 앞으로 가다 보면, $\sum_k f(k) = n$ 에 막히는 지점이 오게 된다. 구체적으로는 $\frac{k(k+1)}{2}$ 가 $n$ 정도 되면 더이상 채울 도게가 남지 않게 되며, 이 지점은 대략 $k \approx \sqrt{2n}$ 이다. 따라서, 실제 우리가 얻을 수 있는 최대 에지 수는 다음과 같다. 

$$\sum_{k = 1}^{2 \sqrt n} \frac{n}{k} k = 2n \sqrt n$$  

정수 나눗셈이라고 해서 큰 차이가 발생하지 않음은 자명하므로, 에지가 $O(n \sqrt n)$ 개인 다익스트라가 되고, 시간 내에 집어넣기에 충분하다.

 

3. 코드

이것저것 생각하면서 짜다가 굉장히 Redundant 한 코드가 되었다. mark 에 쓰는 bitset 도 조금만 코드를 고치면 없앨 수 있는 것 같고, alldoge 와 dogeinfo도 상당히 redundant 해 보이는데 코딩할 때는 정작 그생각을 못했다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin()),((x).end())
 
using pii = pair <int, int>;
#define INF 0x7f7f7f7f
const int MX = 30202;
 
struct Edge
{
    int dest, w;
    bool operator<(const Edge &p) const
    {
        return w > p.w;
    }
};
 
bool relax(Edge edge, int u, int dist[])
{
    bool flag = 0;
    int v = edge.dest, w = edge.w;
    if (dist[v] > dist[u] + w && (dist[u]!=INF))
    {
        flag = true;
        dist[v] = dist[u]+w;
    }
    return flag;
}
 
void dijkstra(int dist[], int start, vector<Edge> graph[])
{
    fill(dist,dist+MX,INF);
    dist[start] = 0;
    priority_queue<Edge> pq;
    pq.push({start,0});
    while(!pq.empty())
    {
        Edge x = pq.top();
        int v = x.dest, w = x.w;
        pq.pop();
        if (w>dist[v])
            continue;
        for (auto ed : graph[v])
            if (relax(ed, v, dist))
                pq.push({ed.dest,dist[ed.dest]});
    }
}
struct doge
{
    int start, power, index;
};
int n, m;
vector <int> bi(30303, 0), pi(30303, 0);
vector <Edge> G[30303];
bitset <30303> mark[30303];
vector <doge> alldoge[30303];
vector <doge> dogeinfo;
int distances[30303];
bool dogevisit[30303];
void dfs(doge curdoge)
{
    dogevisit[curdoge.index] = true;
    for (auto it:alldoge[curdoge.start])
        if (!dogevisit[it.index])
            dfs(it);
    for (int i = 1; ;i++)
    {
        int u = curdoge.start+i*curdoge.power;
        if (u >= n)
            break;
        bool check = false;
        for (auto it:alldoge[u])
        {
            if (it.power == curdoge.power)
                check = true;
            if (!dogevisit[it.index])
                dfs(it);
        }
        G[curdoge.start].push_back({u,i});
        if (check)
            break;
    }
    for (int i = -1; ;i--)
    {
        int u = curdoge.start+i*curdoge.power;
        if (u < 0)
            break;
        bool check = false;
        for (auto it:alldoge[u])
        {
            if (it.power == curdoge.power)
                check = true;
            if (!dogevisit[it.index])
                dfs(it);
        }
        G[curdoge.start].push_back({u,-i});
        if (check) break;
    }
}
int32_t main()
{
    usecppio
    cin >> n >> m;
    for (int i = 0; i<m; i++)
    {
        cin >> bi[i] >> pi[i];
        if (!mark[bi[i]][pi[i]] && i!=1)
        {
            mark[bi[i]][pi[i]] = true;
            alldoge[bi[i]].push_back({bi[i], pi[i], i});
        }
        dogeinfo.push_back({bi[i], pi[i], i});
    }
    dogevisit[0] = true;
    dfs(dogeinfo[0]);
    dijkstra(distances,bi[0],G);
    if (distances[bi[1]] >= 10000000)
        printf("-1");
    else printf("%d\n",distances[bi[1]]);
}