JOI Open Contest 2017

* 모바일 환경에서 레이텍이 깨지는 현상이 있는 것 같다. 구글 크롬의 경우, 우측 상단의 점 세 개를 눌러 메뉴를 열고 "데스크톱 보기"를 활성화하는 것으로 해결할 수 있다.

 

2017년에 진행된 JOI Open Contest 2017의 풀이이다.

대회는 총 3개의 문제를 5시간 동안 해결해야 하며, 각 문제는 부분 문제가 있다. 각 문제별 배점은 100점으로, 총 300점 만점이다.

 

1. Amusement Park

https://oj.uz/problem/view/JOI17_amusement_park

문제 보기 - Amusement Park (JOI17_amusement_park) :: oj.uz

JOI와 IOI에게 같은 그래프가 주어지고(주어지는 간선 리스트가 완전히 일치한다), JOI는 IOI에게 $X \le 2^{60} - 1$라는 정수 하나를 전달해야 한다. 각 정점에 0 또는 1의 숫자를 쓸 수 있다. IOI는 그래프 한 정점 위에 서 있고, 최대 120번 이하(부분 문제마다 차이가 있다)로 간선을 따라 움직일 수 있다. 한 간선이나 정점을 여러 번 방문하는 것은 허용된다. 이때, IOI는 방문한 정점에 쓰여 있는 숫자를 읽을 수 있다. 이 숫자를 바탕으로, JOI가 숨긴 숫자 $X$를 복원해야 한다.

 

그래프의 정점 갯수 $N$, 간선 갯수 $M$

주어지는 그래프는 연결그래프이다.

주어지는 그래프에는 셀프 루프와 이중 간선이 없다.

$60 \le N \le 10000$, $1 \le M \le 20000$

 

100점 풀이

100점 풀이에서 요구하는 이동 횟수 120회는 $60 \times 2$임을 관찰하자. 정점 60개로 이루어진 그래프에서 한 정점에서 시작하여 dfs를 하고 돌아올 때, 총 이동 횟수로 가능한 최댓값이 120회보다 작다는 사실을 사용할 것이다. 그래프가 주어졌을 때 dfs를 해 스패닝 트리 하나를 만들 수 있으므로, 우선 그래프가 트리일 때 이 문제를 해결하자.

 

그래프에 $X$라는 수를 숨겨야 하는데, 0 또는 1의 수밖에 적을 수 없다. 따라서 $X$를 숨기는 방식은 길이 60의 이진 문자열을 저장하는 방식이 될 것이다. $X$를 이진법 표현으로 $a_0 a_1 a_2 \cdots a_{59}$라 하자.

 

만약 트리의 정점 수가 정확히 60이라면, 각 정점에 $a_0$부터 $a_{59}$의 수를 하나씩 숨기면 될 것이다. 이를 응용하여, 트리에서 번호가 아직 적히지 않은 연결된 60개의 정점을 잡고, 그 정점에 $a_0$부터 $a_{59}$의 수를 적는 시행을 더 이상 할 수 없을 때까지 계속 반복하자. 그렇다면 IOI가 이미 번호가 적힌 정점에서 시작할 경우 반드시 $X$를 원래대로 복원할 수 있음이 자명하다. 

 

 트리에서 번호가 적히지 않은 정점들은 크기가 60 미만인 컴포넌트를 형성할 것이다. 또한, 이 컴포넌트들은 각각 번호가 적힌 어떤 정점과 반드시 인접한다. 따라서, 번호가 적히지 않은 컴포넌트들에 대해 인접한 번호가 적힌 60개 정점들 중 제일 멀리 있는 정점들만 적는다면, 번호가 적히지 않은 컴포넌트들을 시작점으로 갖더라도 숫자를 복원할 수 있을 것이다.

 

구현이 약간 까다롭게 느껴질 수도 있는데, dfs를 돌면서 60개 정점을 모으고, 모아진 정점을 제외했을 때 남는 컴포넌트들의 루트 정점을 큐에 넣는 방식을 사용하면 약간 편한 것 같다.

https://oj.uz/submission/684036

답안 #684036 :: oj.uz

 

2. Bulldozer

https://oj.uz/problem/view/JOI17_bulldozer

문제 보기 - Bulldozer (JOI17_bulldozer) :: oj.uz

2차원 평면에 $N$개의 점들이 있고, 점마다 가중치가 있다. 이때 평행한 직선 두 개를 그어서 두 직선 사이에 위치하는 점들의 가중치 합을 최대화해야 한다.

 

$N \le 2000$

점들의 x, y 좌표와 가중치의 절댓값은 $10^9$보다 작거나 같다.

임의의 서로 다른 두 점의 위치는 서로 다르다.

 

이 문제는 굉장히 특이한 테크닉을 사용하는데, 이 문제가 등장한 이후 이 문제의 이름을 따 흔히 bulldozer trick이라 불리는 것 같다. 다른 OI에는 많이 출제되지 않는 기하 분야이지만, 한번 배워볼만 한 아이디어인 것 같다.

 

비슷한 트릭을 사용하는 문제는 KOI 고압선 등이 있다.

 

25점 풀이 ($O(N^3 \log_{2}{N})$)

직선의 기울기가 정해져 있을 때, $O(N \log_{2}{N})$ 시간 복잡도에 답을 구할 수 있다. 어떤 기울기 $a$에 대해 $y=ax-10^18$직선과 떨어져 있는 거리 순서대로 점들을 정렬하면 점들의 연속한 부분배열 중 가중치 합이 제일 큰 것이 답이 된다. 따라서 정렬하고 최대부분합 dp를 사용하면 풀 수 있다. 또한, 두 개의 점을 골라서 만들어지는 직선의 기울기 $- \epsilon$ 들만 고려해 주어도 된다. 따라서 전체 시간 복잡도는 $O(N^3 \log_{2}{N})$

 

60점 풀이

알고리즘의 시간 복잡도를 줄여 최적화하는 접근은 여러 가지가 있으나, 보통 중복되는 연산을 줄이는 방식이 사용된다. 이 문제도 그러하다.

25점 풀이에서는 임의의 두 점으로 만들어지는 모든 기울기에 따라 배열을 한 번씩 정렬해야 한다. 그런데 실제로 몇 가지의 예시를 들어 보면, 비슷한 두 기울기에 대해 각각 정렬을 해 보았을 때 정렬된 배열에 큰 차이가 없음을 알 수 있다. 구체적으로, 다음이 성립한다.

 

관찰 1. 두 점 쌍으로 만들어지는 $\binom{N}{2}$개의 기울기를 $a_1 \cdots a_k$라 하자. 이때 $a_i - \epsilon$에 의해 정렬된 점의 배열과 $a_{i+1}-\epsilon$에 의해 정렬된 점의 배열은 정확히 2개의 인접한 원소만 차이나고, 이 원소는 기울기가 $a_{i+1}$인 쌍의 두 점이다.

 

관찰에 의하여, 모든 점의 쌍을 기울기 순서로 정렬하면 기울기를 점차 증가시켜가면서 생기는 정렬된 배열의 변화를 선형 미만의 시간에 관리할 수 있다. 또한 계속해서 인접한 원소가 변하는 배열에서 전체 배열의 최대 구간 합을 선형 미만의 시간에 구해 주어야 하므로, 흔히 금광 세그라고 불리는 세그먼트 트리를 사용하면 된다.

 

만점 풀이 (작성 중)

솔직히 만점 풀이와 60점 풀이를 분리한 이유, 점수 차이를 40점씩이나 둔 이유를 잘 모르겠다. 점 순서쌍의 정렬 기준을 아주 잘 설정하면, 세 점이 한 직선에 놓여 있든, 기울기가 같은 쌍이 있든 완전히 같은 코드로 풀 수 있다.

(추후 작성 예정)

 

3. Golf

https://oj.uz/problem/view/JOI17_golf

문제 보기 - Golf (JOI17_golf) :: oj.uz

2차원 평면에 $N$개의 직사각형 모양의 장애물이 있고, 어떤 점에 골프공이 있다. 이 골프공을 주어지는 도착점으로 옮기는 것이 목표이다. 골프공을 옮길 때는 특정 방향으로 특정 거리만큼 이동시킬 수 있는데, 이동시키는 거리에는 제약이 없다. 그러나 장애물의 내부(경계는 내부가 아니다)로는 통과할 수 없다. 최소 이동 횟수를 구하라.

 

모든 좌표 범위는 1 이상 $10^9$ 이하이다.

$1 \le N \le 100000$

서로 다른 두 장애물끼리 경계에서도, 내부에서도 겹치지 않는다.

시작점과 도착점은 장애물의 경계에서도, 내부에서도 있지 않다.

 

30점 풀이

다음과 같은 관찰이 요구된다.

 

관찰 1. 주어지는 모든 점(사각형의 왼쪽 아래, 오른쪽 위 꼭짓점, 시작점, 도착점)에서 장애물을 만날 때까지 왼쪽, 오른쪽 방향으로 선을 연장해 그리자. 상하 방향으로도 그리자. 이렇게 하여 생긴 $4N+4$개의 직선만 골프공이 지나는 최적해가 존재한다.

 

시작점과 끝점, 직사각형(검은색)과 연장선(주황색)을 표시한 그림이다. 연장선 중 일부는 생략되었다. 또한 연장선이 다른 장애물의 경계를 지나갈 수 있음에 유의해야 한다.

위 예시처럼, 연장선을 전부 그리면 연장선만을 따라가는 최적해(3회 이동)가 존재한다는 사실을 알 수 있다. 이때, 점이 아닌 연장선을 정점으로 생각하고 교점을 간선으로 생각하면, 이 문제는 시작 정점 2개(시작점에서 그려진 연장선 2개)에서 끝 정점 2개(도착점에서 그려진 연장선 2개)로 가는 최단 경로를 찾는 문제로 생각할 수 있다. 가중치 없는 그래프로 생각할 수 있으므로, 다익스트라 없이 bfs만으로도 풀 수 있다.

부분 문제 2의 경우 $N$이 1000보다 작으므로, 약 4000개 정도의 직선이 있다. 각 점마다 모든 사각형을 확인해 보는 방식으로 점 하나 당 $O(N)$ 시간 복잡도로 연장선이 어디 까지 연장되는지 구해 주고, 연장선을 전부 구했으면 $O(N^2)$으로 모든 직선 쌍 사이 교점이 존재하는지 체크해주고, 그래프를 만들어준다. 이후 bfs를 하면 답을 구할 수 있다.

 

구현에 따라 다르지만 답이 1인 예외 케이스가 발생할 수도 있다. 이를 처리해줘야 한다.

 

만점 풀이

사실 30점 풀이와 별 차이 없다. 30점 풀이에서는 각 점마다 연장선을 $O(N)$에 구하고, 각 직선들마다 교점이 있는지 총 $O(N^2)$에 걸쳐 판정을 했지만, 만점 풀이에서는 자료 구조와 셋으로 이 전체 과정을 최적화해 줄 것이다.

우선, 이 문제에서는 점들의 위치의 대소 관계만 중요할 뿐이지 거리가 중요하지는 않다. 따라서 10억정도 되는 모든 좌표를 $1$~$2N$ 범위로 압축해준다.

연장선을 구하는 것은 셋을 이용한 스위핑 네 번(위, 아래, 오른쪽, 왼쪽)으로 해결할 수 있다.

이제 bfs 과정을 최적화 할 것인데, 연장선들의 교점을 미리 구해 놓는 것이 아닌 bfs할때 큐에서 뺄 때마다 큐에서 뺀 연장선과 만나는 연장선을 그때그때 구하는 방식을 사용할 것이다.

 

여러 가지 풀이가 있겠지만, 나는 std::set을 노드로 갖는 머지 소트 세그먼트 트리를 사용했다. bfs를 할 때 인접한 연장선을 구하는데, 수직 연장선에서는 인접한 수평 연장선만 구해도 되고, 수평 연장선에서는 인접한 수직 연장선만 구해도 된다. 수직 연장선과 인접한 수평 연장선을 구하는 방법은 수평 연장선의 $x$좌표 범위에 해당하는 머지 소트 세그먼트 트리의 노드에 연장선을 저장해두고, 각 세그먼트 트리의 노드에는 연장선을 $y$좌표 순으로 관리한다. 그러면 수직 연장선이 주어질 때 그 수직 연장선의 $x$좌표를 포함하는 모든 노드에서 $y$좌표가 수직 연장선의 $y$좌표 범위 안에 드는 모든 직선들을 꺼낼 수 있다. 이때 bfs에서는 한번 간 정점의 재방문은 허용하지 않으므로, 연장선들을 찾았으면 찾은 모든 연장선을 머지 소트 세그먼트 트리 상에서 제거한다.

 

이렇게 하면 시간 복잡도 $O(N \log_{2}^{2}{N})$에 주어진 문제를 풀 수 있다.

 

풀이와 별개로, 내 코드는 6000B, 공식 솔루션은 6700B로 상당히 코드가 긴 것을 알 수 있다. 제곱 풀이의 일련의 과정들을 각기 다른 풀이로 최적화하다 보니 길어진 것 같은데, 생각보다 어렵진 않았던 것 같다.

https://oj.uz/submission/684734

답안 #684734 :: oj.uz