5월 4일 연습

IOI 멘토교육 2주차로 세 문제로 이루어진 셋을 5시간동안 걸쳐서 풀었다. 오후 3시 30분에 시작해서, 오후 8시 30분에 끝났다.

 

문제는 다음과 같다.

 

1. BOJ 16760 Balance Beam (USACO 2018 December Contest Platinum 1번)

2. BOJ 17019 Exercise Route (USACO 2019 January Contest Platinum 2번)

3. BOJ 17191 Valleys (USACO 2019 Open Contest Platinum 3번)

 

결과

제출 기록

 

연습 기록

0:00 ~ 0:15

세 문제를 전부 읽었다. 내가 영어를 잘 못 하는 것도 있고, 지문이 뭔가 이해하기 어려웠다. 특히 3번은 조건이 많이 복잡해서 정확히 이해하기 힘들었다.

0:16 ~ 0:27

일단 1번부터 봤다. 기댓값을 구하라는 문제였는데, $x$번째 답을 $g(x)$라 한다면 $g(x) = min \{ f(x), \frac{g(x-1) + g(x+1)}{2}\}$로 쓸 수 있음을 알았다. 다음과 같은 관찰을 했다.

1. $x$를 배열의 최댓값이라 할 때, $f(x) = g(x)$

2. $l \le x \le r$에 대하여 $g(x) \ge min \{ g(l), g(r) \}$, 즉 $g$는 unimodal한 함수이다.

0:28 ~ 0:36

1번 문제의 풀이를 찾았다. $g(x) = min \{ f(x), \frac{g(x-1) + g(x+1)}{2}\}$ 조건을 조금 변형하면 $g(x) \ge \frac{g(x-1) + g(x+1)}{2}$이고, 저 식은 결국 $g$함수가 볼록한 함수라는 사실을 말해준다. 따라서 $(i, f(i)$ 점들을 다 찍고($f(0) = f(N+1)=1$이라 하자) 볼록 껍질을 그리면 $g$의 그래프가 된다. 일단 시간이 별로 안 지났으니, 2번을 조금 생각해보고 구현하기로 했다.

0:37 ~ 0:47

2번 문제에서 두 간선을 모두 사용할 경로가 존재할 필요충분조건을 찾았다. 두 간선에 대해, 그 간선들이 연결하는 양 끝 정점을 사이 트리상의 경로를 생각하자. 이 두 경로가 교집합이 없다면, 두 간선을 모두 사용하는 경로는 존재하지 않는다.(단절선을 이용해 증명했다) 또한, 교집합이 있는 경우는 구성적으로 경로가 존재함을 보일 수 있었다.

 

원래는 적당히 생각하다가 1번을 구현하려고 했으나, 뭔가 반쯤 푼 것 같아서 좀 더 생각해 보기로 했다.

0:48 ~ 1:10

결국 구현해야 하는 것은 주어진 $M-N+1$개 경로 중 교집합이 있는 경로 쌍의 갯수인데, 처음에는 HLD 느낌으로 생각해보았는데 잘 안 되었다. 그러다가 "두 경로가 겹친다면 한 경로는 다른 경로의 LCA(경로의 양 끝 정점의 최소 공통 조상)를 포함한다" 라는 사실을 알게 되었고, LCA의 깊이가 같은 경우와 다른 경우로 나눠 갯수를 세면 된다는 사실을 알게 되었다. 세그트리가 필요한줄 알았으나, 안 쓰고 푸는 방법을 금방 찾았다.

1:11 ~ 1:28

위 풀이를 구현했다.

구현을 다 하고 보니 앞서 언급한 교집합을 "간선의 교집합"이 아닌 "정점의 교집합"으로 생각하고, 잘못 구현했음을 확인했다. 

1:29 ~ 2:04

다시 생각해 보았는데, 약간의 디테일만 고치면 되는 정도였다. 다시 코딩했다. 제출하고 한 번에 맞았다.

2:05 ~ 2:14

1번 문제를 구현했다. 구현 자체는 금방 했다. 그런데 제출하니까 WA가 떴다.

2:15 ~ 2:51

반례를 찾으려고 이것저것 다 해보다가 실패했다. 설마 실수오차 때문에 틀리는게 아닐까 하고 실수 계산하는 방식을 바꾸었다. 정확히는, 분모 분자를 다 따로 저장해놓고 계산했다. 그랬더니 맞았다. 이후로는 3번만 계속 생각했다.

2:52 ~ 4:23

풀이를 생각하는데 좀 오래 걸렸다. 이것저것 다 시도를 해 보았는데, 잘 안 되었다. 그러다가 "각 컴포넌트가 포함하고 있는 구멍의 갯수를 관리할 수 있다" 라는 사실을 알게 되었고, 각 $i$에 대해 $[1, i]$의 높이만 고려할 때 complement에는 몇 개의 컴포넌트가 있는지를 전처리하면 $O(N^2)$에 풀 수 있다는 사실을 알게 되었다.

4:24 ~ 4:59

끝나기 1분 전에 겨우 AC를 받았다.