2020년도 대한민국 국제정보올림피아드 선발고사 풀이 (Day 2)

대회 당시에 본인의 실시간 등수. 끝나기 직전에 4 -> 5 -> 6이 인상적이다...

 

Day 1: https://dsstar.tistory.com/48

 

이어서 작성한다.

 

 

Day 2

 

 

1. 마법의 다이얼(BOJ 25012)

 

Solution

 

각 행에 대해, 해당 행에서 i에 다이얼이 오도록 맞추는 비용을 생각해보면, 함수의 개형은 지그재그 꼴이 된다.

다이얼이 처음 상태에서 위치한 곳의 함수값은 0, 거기서부터 시작해서 좌우로 함수의 기울기가 왼쪽으로 -1, 오른쪽으로 1인 그래프가 되고, 다른 직선과 만나게 된다면 끊기게 된다.

더 정확히 설명하자면, $s$, $e$ 사이의 그래프는 s에서 기울기가 1 증가, $\lfloor (s+e)/2 \rfloor$에서 기울기가 1 감소, $\lceil (s+e)/2 \rceil$에서 기울기가 1 감소, e에서 기울기가 1 증가한다.

기울기가 변하는 점을 전부 배열에 저장해서 정렬하고, 기울기가 변하는 점에서의 함수값만 확인해도 무방하다.

0을 포함하는 구간에 유의하여 구현하자.

 

시간복잡도는 O(NlogN).

 

Code : http://boj.kr/00f79823a7734a89b8157dcb8640e6f2

 

 

2. 하나 둘 셋(BOJ 25013)

 

Subtask #2(43점)

 

우선, 2를 빼놓고 1과 3만 생각해보자. 1과 3을 매칭시킬때 앞에 나오는 걸 '시작하는' 1(또는 3), 뒤에 나오는 걸 '끝나는' 3(또는 1)이라고 하겠다.

• 3, 1, 1, 3 순서대로 있다고 가정하면, 첫번째 3과 첫번째 1을 매칭시킬 이유가 없다. 따라서, 모든 시작하는 1은 모든 끝나는 1 이전에 위치한다. 3에 대해서도 마찬가지.
• 1, 1, 3, 3 순서대로 있다고 가정하면, 첫번째 1과 두번째 3을 매칭시킬 이유가 없다. 따라서, 시작하는 1과 끝나는 3은 순서대로 매칭시키는게 이득이다. 끝나는 3과 시작하는 1에 대해서도 마찬가지.
• 1, 3, 3 순서대로 있다고 가정하면, 1과 첫번쨰 3을 매칭시킬 이유가 없다. 따라서, 시작하는 1(이나 3)들은 앞에서부터 순서대로, 끝나는 3(이나 1)들은 뒤에서부터 순서대로 뽑는게 이득이다. 

 

이제 123의 개수랑 321의 개수를 정하면, 각 트리플에 대해 1과 3의 위치는 결정이 된다. 1-3 쌍이나 3-1 쌍에 대해서 종류를 상관하지 않고 나열하면, 이 쌍들에 대해서 2를 매칭시키는 회의실 배정 문제가 된다.

 

회의실 배정 문제는 $O(NlogN)$에 풀 수 있고, 이를 $O(N^2)$ 회 풀어야 한다.

따라서 시간복잡도는 $O(N^3logN)$.

 

Subtask #3(96점)

 

123의 개수가 증가할수록, 가능한 321의 개수는 단조감소한다는 사실을 관찰할 수 있다.

따라서, 투포인터 등을 통해서 각각의 개수를 관리하면, 회의실 배정 문제를 푸는 횟수를 $O(N)$회로 줄일 수 있다.

 

시간복잡도는 $O(N^2logN)$.

 

Full Solution(150점)

 

회의실 배정 문제를 최적화시켜보자.

1-3 쌍과 3-1 쌍은 각각 시작점과 끝점이 단조증가한다.

그렇다면, 회의실 배정 문제에서 '끝점이 빠른 일정을 먼저 고른다'라는 그리디를, 1-3 쌍과 3-1 쌍들에 대해서는 무시할 수 있다.

따라서, 1-3 쌍들에 대한 queue와 3-1 쌍들에 대한 queue를 따로 관리하면서 두 queue의 front 중 먼저 끝나는 쪽을 먼저 2와 매칭시키면, 회의실 배정 문제를 $O(N)$에 풀 수 있다.

 

시간복잡도는 $O(N^2)$.

 

Further Approach(??점)

 

tlwpdus님의 코드(46890039번 제출)에 따르면, 이 문제를 $O(N)$, 또는 $O(NlogN)$에 풀 수 있다고 한다.(????)

 

123에 대하여, 가능한 123의 개수의 최댓값은 모든 $(i, j)$($0 \leq i \leq j < N$)에 대하여 ($[0, i]$ 구간의 1의 개수) + ($(i, j]$ 구간의 2의 개수) + ($(j, N-1]$ 구간의 3의 개수)의 최솟값이다. Hall's Theorem을 이용하면 증명할 수 있다.

321의 개수와 123의 개수 + 321의 개수에 대해서도 마찬가지이다.

따라서, 123과 321의 개수를 각각 정할 수 있다.

 

전처리에 $O(N)$, 회의실 배정 문제를 푸는데 $O(N)$이다.

따라서 시간복잡도는 $O(N)$.

 

Codes

$O(N^2)$ : http://boj.kr/d4fe1b4ffb5f44098f1174b73b8cf2cd

$O(N)$ : http://boj.kr/656b0ebe233d472d890ff8a50a3acc79

 

 

3. 열차의 이동(BOJ 25014)

 

Subtask #3(63점)

 

$P$ 상의 점 중에서 $Q$에 가장 가까운 것을 $p$, $Q$ 상의 점 중에서 $P$에 가장 가까운 것을 $q라고 하자.

$P$와 $Q$ 중 겹치는 간선이 없기 때문에, 열차의 경로는 다음과 같이 나눌 수 있다:

• $P$의 한쪽 끝 점을 $p$로 보내고
• 해당 끝 점을 $q$로 보내고
• 이를 다시 $Q$로 보낸다.

 

두번째와 세번째 단계를 살짝 바꿔보겠다.

• $P$의 한쪽 끝 점을 $p$로 보낸다.
• $len(P) + dist(p, q)$만큼 이동시킨다.
• $Q$의 한쪽 끝 점을 $q$로 보낸다.

세 번째 단계를 역순으로 뒤집고, 이를 빼내서 $p$에 닿게 하는 부분을 두 번째 단계로 보냈다.

따라서, "경로의 한쪽 끝 점을 경로 위의 특정한 점으로 보낸다"라는 행위를 두 번 계산하면 된다.

 

경로 위의 각 점에 대해서, 열차의 한쪽 끝 점이 해당 점에 위치하게 하는 비용을 DP를 통해 구할 수 있다.

전처리에 $O(N)$, DP의 계산에 $O(len(P)^2)$이다.

따라서 시간복잡도는 $O(N + len(P)sum(len(P)))$.

 

Full Solution(150점)

 

DP를 최적화시켜보자.

$P$ 상에서 $p$보다 왼쪽에 있는 $i$에 대하여, $i$가 오른쪽으로 갈수록 왼쪽 끝 점이 $i$ 이하인 상태에서 도달할 수 있는 오른쪽 끝 점의 위치는 점차 왼쪽으로 이동한다.

또한, $p$ 왼쪽의 $i$에 대한 DP값은 $i$가 오른쪽으로 갈수록 증가하며, 오른쪽의 $j$에 대한 DP값은 $j$가 왼쪽으로 갈수록 감소한다.

따라서, 투포인터를 이용하여 DP를 $O(len(P))$에 구할 수 있고, DP의 전처리는 $O(len(P)logN))$에 할 수 있다.

 

시간복잡도는 $O(N + sum(len(P))logN)$이다.

 

Code : http://boj.kr/debd1fe0f7b347a49c6942c9d7215e31

 

여담.

잘못된 관찰을 해서 말릴수도 있고, 관찰 자체도 어렵고, 구현도 어렵다. 어떻게 선발고사때 대회장에서 4솔이 나왔는지 모르겠다.

나는 $sum(len(P)) \leq 1000000$ 조건을 못 봐서 관찰을 다 해놓고 선발고사때 못 풀었다.

어제 KOI 사이트에 공개되어 있는 CMS 스코어보드를 확인해봤는데, 나보다 위에 있던 두 사람이 각각 4시간 52분 18초, 4시간 55분 45초에 AC를 받았었다.

아............................................................

 

 

4. 아이싱(BOJ 25015)

 

Solution

 

Intended solution은 논문에서 나온 굉장히 복잡한 풀이라고 한다.

 

몇 개의 간선을 제외해서 그래프를 이분 그래프로 만들기 위해서는, 해당 간선들이 포함된 홀수 사이클의 합집합이 모든 홀수 사이클의 집합이라는 것이다.

DFS를 돌면서, 백엣지를 통해 홀수 사이클이 만들어진다면 해당 홀수 사이클 상의 모든 간선에 랜덤한 태그를 붙여준다.

태그가 여러개 붙은 간선의 경우, 태그들의 값을 xor해준다.

 

그래프가 처음부터 이분 그래프라면 답은 0이다.

이외의 경우, 모든 태그가 붙어있는 간선이 있다면 답은 1이다.

이외의 경우, 두 간선의 태그를 xor해서 전체 태그의 xor값이 되는 두 간선이 존재한다면 답은 2이다. 셋이나 해시셋을 이용하여 빠르게 계산할 수 있다.

이외의 경우, 답은 3이다.

 

시간복잡도는 $O(N+M)$ 또는 $O(N+MlogM)$이다.

 

Code : http://boj.kr/d028d711a8654a03b57421cb8997c68f