IOI 멘토교육 20190615

JOI 2016

 

오렌지 출하

$D_i =$ (1~i번째 오렌지까지 어떻게 상자에 넣을지 배정했을 때 최솟값)이라고 정의하면, $O(NM)$ DP로 해결할 수 있다.

 

스탬프 수집

일단 JOI를 모을 수 있는 경우의 수를 구하는 방법을 생각해 보자. $J_i =$ (1~i번째 가게 중 J 스탬프를 주는 가게 수)로 정의하고, $I_i =$ (i~N번째 가게 중 I 스탬프를 주는 가게 수)로 정의하자. 그러면 경우의 수는 $S_i =$ 'O'를 만족하는 i들에 대해 $J_i*I_i$를 모두 더한 것이 된다.

가게를 추가할 때 스탬프 J를 주는 가게를 추가한다면, 입구에 설치하는 게 이득이고, 스탬프 I를 주는 가게를 추가한다면 출구에 설치하는 게 이득이다. 스탬프 O를 주는 가게를 추가한다면 $J_i*I_i$를 최대로 하는 i에 설치하는 게 이득이다.

이 세 가지 경우 중 최댓값을 출력하면 된다.

 

철도 요금

어떤 간선의 비용이 1에서 2가 되면, 사실상 그 간선은 없어지는 거라고 생각하면 된다. 그 간선을 계속 이용하기로 한다면, 경로의 길이가 늘어날 것이기 때문이다. 또한 도시 1과의 거리가 같은 두 도시를 연결하는 간선은 끊어버려도 상관없다. 이 간선을 이용한 순간, 도시 1로 가는 최단경로가 아니게 되기 때문이다.

$L_i =$ (도시 i와 도시 1을 잇는 최단경로의 길이)로 정의하고, $D_i =$ (도시 i에 사는 주민들이 처음으로 불만을 가지게 되는 시점)으로 정의하자. 또 어떤 간선이 없어지지 않는다면 그 간선이 없어지는 시점을 INF로 정의하자. ($u \in adj_i$ && $L_u = L_i - 1$)을 만족하는 모든 $u$ 중 $Min(D_u, ($u와 i를 잇는 간선이 없어지는 시점$))$의 최댓값이 $D_i$가 된다. DP값을 BFS를 하면서 채워나가면 $O(N+M)$에 문제를 해결할 수 있다.

 

영역 (15점)

조이가 이동하는 걸 시뮬레이션하면서 좌표를 std::set에 넣고, std::set의 원소마다 그 교차로를 왼쪽 아래 점으로 가지는 블록이 조이의 영역인지를 체크해주면 $O(NK log NK)$에 풀 수 있다.

 

영역 (38점)

하룻동안 점 집합이 생기고, 날이 반복될수록 이 집합이 여러 개 겹쳐지면서 영역의 수도 늘어날 것이다. 직관적으로 생각해보면, 충분히 많은 날이 흐르면 다음 날에 새로 생기는 영역의 수 B가 어떤 상수로 고정될 것이다. '충분히 많은 날의 수'를 X라고 하자. $X \leq K$라면 그냥 15점 풀이로 풀면 된다. $X > K$이면 X번째 날까지의 영역의 수 A를 구하고, 다음 날에 새로 생기는 영역의 수 B도 마찬가지로 구해 주자. 그러면 답은 $A + (K-X)*B$이다. $X = O(N)$이므로 시간복잡도는 $O(N^2 log N^2)$이다.

 

나는 38점 풀이에서 발전시켜서 A와 B를 빠르게 구하는 100점 풀이를 계속 떠올리려고 해 봤다. 그 결과 대회가 끝나기 1시간 전에 구현과 풀이가 모두 복잡한 어떤 방법이 떠올랐다. 어떤 점에 영역이 처음으로 생기는 시점을 mod 연산을 통해 열심히 잘 구해주고, 그걸로 A와 B를 구하는 풀이였다. 코딩을 시작했지만, 생각했던 것보다도 더 복잡해서 중간에 구현을 멈추고 약 30분 동안 아무것도 못했던 것 같다. 대회가 끝나고 정해 코드 길이를 보니 7천 바이트를 넘더라. ㅋㅋ

이런 문제를 대회 시간 안에 풀려면 생각이 아주 잘 정리되어 있어야 할 것 같았다.

 

단층 (18점)

문제에 주어진 연산이 뭘 의미하는지는 머릿속으로는 알겠는데, 직관적으로는 와닿지를 않았다. 그래서 일단 단층 이동을 그냥 이차원 배열로 시뮬레이션하면 되는 18점을 풀었다.

 

이후에도 풀이를 발전시켜서 단층 경계를 std::set 같은 자료구조로 관리하는 34점 풀이를 떠올려봤으나, 역시 구현에 어려움을 겪고 4번을 다시 고민하러 갔다.

 

356점을 받고, 2시간 동안 단 1점의 점수도 내지 못했다. 4번 100점과 5번 34점 모두 구현이 쉽지는 않아 보이는 문제였다. (사실 5번 34점은 더 쉽게 푸는 방법이 있는 것 같다...) 풀이를 정리하는 연습과 구현을 어떻게 할지 정리하는 연습이 필요한 것 같다.