CEOI 2006

1. Antenna

http://amugelab.tistory.com/entry/problem-solving-20160130 에 있는 phone cell 문제 + binary search.

https://github.com/koosaga/olympiad/blob/master/CEOI/ceoi06_antenna.cpp

2. Queue

N이 작은 케이스에서 시작하자. 이 때는 linked list의 요령으로 문제를 풀 수 있다. prev(i) = i번의 왼쪽 원소, next(i) = i번의 오른쪽 원소라고 했을때, 초기값은 i-1, i+1로 가득 차 있고, 질의가 들어왔다면, 일단 A를 삭제하고, B의 앞에 A를 박으면 된다. 방법은 생략. 이러한 식으로 처리한 후, 후에 배열의 값을 모두 저장해놓고, 그냥 질의를 응답하면 된다.

N이 커도 풀이는 같다. prev(i)와 next(i)를 std::map에 저장해놓고, 원소가 없으면 i-1, i+1이라고 가정해 버리면 된다. 배열로 저장하는 부분은, 원소를 O(Q)개의 구간으로 생각한 다음에 질의를 약간 더 현명하게 응답하면 된다.

https://github.com/koosaga/olympiad/blob/master/CEOI/ceoi06_queue.cpp

3. Walk

그럴 듯한 그리디 알고리즘이 있다. 나도 풀이에서 본거라 왜 되는지는 모르겠는데, 증명할 수 있는 사실이라고 한다.

* 주어진 두 점을 잇는 최적 경로 중 하나는, 끝 점에서 서쪽으로 "무작정" 움직이고, 만약 장애물이 발견되면 북 / 남쪽 경계를 타고 넘어간다.

중요한 위치는 직사각형의 네 꼭지점 + 시작 끝 점 정도니, 이 점에서 서쪽으로 무작정 쐈을 때 어느 직사각형에 도달하는지 정도만 계산해놓으면, O(N) 크기의 weighted graph가 생기고, 여기서 dijkstra를 돌려서 문제를 해결할 수 있다. (DAG로 모델링할 수도 있는데, 조금 귀찮아서 나는 다익스트라 썼다)

서쪽으로 무작정 쐈을 때 어디 도달하는 지가 문제인데, 그냥 계산하면 O(N^2)이지만, plane sweeping 과 적절한 자료구조를 동반하면 가능하다. 나의 경우에는 구간 값 대입 + 원소 반환을 하는 자료구조가 필요했으며 여기에 가장 좋은 것은 segment tree. 좌표 크기가 작아서 쉽게 구현할 수 있었다. 

https://github.com/koosaga/olympiad/blob/master/CEOI/ceoi06_walk.cpp

4. Connect

직접 연결한다고 생각하면 정말 답없이 막막해질 수 있다. 이 문제를 푸는 매우 중요한 아이디어는, 직소 퍼즐처럼 패턴을 끼워 맞춰서, 답을 유도하는 방법이다.

X자가 있는 셀에서는, X자를 양쪽 4개 방향 중 하나로 이어버리면 된다. 예를 들어:

+.+

.Xo

+.+

그렇지 않은 셀에서는, 4개 방향 중 2개를 골라 그 둘을 잇거나, 아무것도 잇지 않는다. 예를 들어:

+o+

.oo

+.+

코스트를 최소화하면서 저러한 타일로 채우는 방법은, 잘 알려진 bitmask dp이다. 적당한 순서로 채워나가면서, 연결을 필요로 하는 셀이 무엇인지를 비트마스크로 관리하면, O(nm2^m) 정도에 아주 빠르게 돌아간다.

갓문제.

패턴이 11개이기 때문에 실수없이 코딩해야 한다. 사실, tricky한건 하나도 없기 때문에 그냥 키보드만 두들기면 되는, 코딩도 쉬운 문제이다. 갓문제.

https://github.com/koosaga/olympiad/blob/master/CEOI/ceoi06_connect.cpp

5. Link

일단 저 그래프는 사이클에 트리가 주렁주렁 달려있는 형태의 그래프이다. https://en.wikipedia.org/wiki/Pseudoforest#Graphs_of_functions

추가하게 될 링크가 1번 노드를 시작점으로 하는 것이 자명함으로, 링크를 추가한다 -> 임의의 지점에서 K-1 거리까지의 지점을 체크한다 라는 식으로 생각할 수 있다. 이미 1번 노드에서 거리 K 안인 위치는 모두 체크가 되어 있으니, 나머지 지점을 적절히 최소 횟수로 체크하는 것이 문제의 과제이다.

일단 먼저 사이클이 없이, 방향성이 있는 트리라고 생각을 하고 문제를 해결하자. 트리일 때는, dfs로 문제를 해결할 수가 있다. 트리의 루트에서 dfs를 한다. 반환값은 “자신의 x번째 조상까지 색칠 가능하다” 라는 뜻이다.

 * 1. x == 1이면 K를 리턴한다,

 * 2. 자식 중에 반환값이 가장 큰 자식을 고르고, 그 자식을 답으로 체크한다.

 * 3. 만약 그러한 자식이 없거나 그 자식이 자기를 체크하고 수명이 끝난다면 (답이 0이라면) 자신을 체크하고 K-1을 리턴한다.

int dfs(int x){

    int ret = 0;

    if(x == 1) ret = k;

    for(auto &i : graph[x]){

        ret = max(ret, dfs(i));

    }

    ret--;

    if(ret < 0) ret = k-1, cnt++;

    return ret;

}

말로 설명할 자신이 없다. 소스가 간단하니까 이걸 이해하도록.. ㅋㅋ 이렇게 하면 트리일 때는 선형 시간에 해결할 수 있다.

사이클이 있어도 크게 문제는 다르지 않다. 일단 위에 설명한 똑같은 알고리즘으로 사이클에 달려있는 트리를 색칠하자. 이 과정에서 사이클도 어느정도 칠해진다. 이제 최소 횟수를 색칠할 것인데, 문제를 살짝 간략화해보자.

 * N개의 원주상에 0 또는 1이 있다. K개의 연속된 수를 1로 덮는 연산이 가능하다. 최소 횟수는?

원주를 선으로 펴 보면, 아주 당연한 그리디가 존재한다. 원주를 선으로 펴는 경우, 즉 시작점의 경우는 K개가 존재한다. 고로 O(NK) 알고리즘이 유도 가능하다. 한편, 사이클에 대해서 다음과 같은 전처리를 할 수 있다.

 * nxt[i] = i에서 오른쪽으로 최소 k만큼 떨어져 있으면서, 값이 0인, i에서 가장 가까운 원소.

이 값을 구하면, 점프 횟수를 worst O(N/K)로 줄일 수 있다. 전처리 O(N)인 고로 O(N/K) * O(K) = O(N)에 문제가 해결.

https://github.com/koosaga/olympiad/blob/master/CEOI/ceoi06_link.cpp

6. Meandian

N = 4인 케이스에서는 한 원소도 답을 구할 수 없음이 자명하다.

N = 5에서는 딱 1개만 구할 수 있는데, 다음과 같은 방법으로 할 수 있다.

- meandian(b2, b3, b4, b5) = meandian(b1, b3, b4, b5) = (b3 + b4) / 2

- meandian(b1, b2, b4, b5) = (b2 + b4) / 2;

- meandian(b1, b2, b3, b5) = meandian(b1, b2, b3, b4) = (b2 + b3) / 2

위 정보를 통해 b2 + b3 + b4와, b2 + b4를 알 수 있다. 고로, b3인 중간값을 유추해 낼 수 있다.

한편, 원소 중 최솟값 / 두번째 최솟값 / 두번째 최댓값 / 최댓값 역시 답을 구할 수 없다. 최솟값을 못 구하는 것은 자명하고, 두번째 최솟값을 못 구하는 이유는, 구하기 위해서는 meandian(최솟값, 두번째 최솟값, ..) 과 같은 질의를 무조건 날려야 하는데, 이 질의로 나오는 답들은 최솟값과 두번째 최솟값을 구별하는 데 충분한 정보를 주지 못한다. 최댓값도 동일.

고로, 구하지 않은 수의 개수가 N일 때

- N >= 5 일 때, 구하지 않은 5개의 수를 골라서 중간값의 값을 5번만에 유추할 수 있음, N은 항상 1씩 감소.

- N == 4 일 때는 절대 답을 구할 수 없음

5(N-4) 번의 질의로 항상 답을 구할 수 있다.

https://github.com/koosaga/olympiad/blob/master/CEOI/ceoi06_meandian.cpp