190720 팀 연습: BAPC 2018

태어나서 두 번째로 팀 연습을 돌았다. 셋은 BAPC 2018(코드포스 #, BOJ #), 11문제 중 11문제 모두를... 4시간 40분동안 찝찝하지만 올 솔브하긴 했다. 빛rkm 버스 승차감이 너무 편안했다.

 

이 셋으로 연습하고자 하는 팀이 있다면 문제를 출력할 때 조심하자. 문제지에서 문제당 페이지 개수를 짝수 개로 보정(This page is intentionally left blank)해주지 않아 그냥 인쇄를 누르면 문제가 종이 두 개에 나눠서 찍히게 된다.

 

우리 팀이 푼 순서로 모든 문제를 업솔빙해 본다.

 

A - A Prize No One Can Win / junie, 00:03

 

가장 쉬운 문제다. 내가 앞 네 문제를 잡고 읽었는데, A가 가장 쉬운 문제이고 B, C도 쉬운 문제였다는 사실은 내게 D도 풀만할 것이라는 생각을 하게 했다. A, B, C까지는 난이도순 맞는 것 같은데~

 

수열을 정렬한 다음 $a[i-1] + a[i] \le X$를 만족하는 최소의 $i$ (가 없으면 $N$을 출력)을 출력하는 쉬운 문제이다.

 

J - Janitor Troubles / rkm0959, 00:06

 

jwj가 이런 문제 있다고 말하자마자 rkm이 아 이거 개쉬움 ㅋ 하고 낚아채서 바로 풀어버렸다. 사각형의 네 변의 길이가 주어졌을 때 그 넓이는 사각형이 원에 내접할 때 최대이고, 그 때의 넓이는 $\sqrt{(s-a) (s-b) (s-c) (s-d) } $ ( $s = \frac{a+b+c+d}{2}$)이다. 헤론의 공식을 잘 변형한 공식으로 뭐 브라마굽타 뭐 브레치나이더 하는 할일없는 멋진 수학자들이 잘 증명해놓은 듯하다. #

 

F - Financial Planning / rkm0959, 00:10

 

파라매트릭 서치를 배울 때 예제로 풀 만한 문제이다. 내가 업솔빙할 때는 $l$, $r$ 범위가 int 넘을 수 있는 것 생각 안 해서 한 번 틀렸고, 20억 일 동안 투자하면 총 수익이 long long 범위를 넘을 수 있다는 것(걍 수익이 $m$ 넘으면 잘라주면 된다) 생각 안 해서 한 번 틀렸다. 오늘 왜 이렇게 멍청하지?

 

C - Cardboard Container / rkm0959, 00:16

 

처음에 내가 잘못 생각해서 야매 풀이로 짜고 (심지어 3번 예제도 안 나옴), 바로 비켜서 rkm에게 문제 설명했더니 그냥 전탐색해서 풀었다. $ijk = V$인 $i \le j \le k$를 전탐색하자. $i$와 $j$가 있으면 $k$가 바로 나오므로 $i$와 $j$만 iterate하면 된다. $i \le \sqrt[3]{n}$, $j \le \sqrt{n}$이므로 도합 $O( n^{\frac{5}{6}} )$의 시간복잡도로 해결할 수 있다. (하지만 $n$의 범위가 100만이라 그렇게 tight하게 bound를 만들 필요는 없다)

 

G - Game Night / cjwj5505, 00:42

 

처음 보고 3초간 FFT 써야하나? 라는 생각이 들었다. 그냥 풀면 된다. 이런 문제가 내가 코딩하기 제일 머리아파하는 유형이라서, 다른 문제 업솔빙보다 코드 깔끔하게 만드는 데 힘썼다.

 

E - Entirely Unsorted Sequences / rkm0959, 00:53

 

이 문제를 이렇게 빨리 풀었다는 게 믿기지 않는다. 연습 당시에는 읽지도 못했고, 끝나고 나서 끙끙대며 풀었다. 다이나믹 프로그래밍으로 푼다. $a$를 정렬한 결과 나온 배열을 $b$라고 하자. 그리고 $b_{i..j}$를 순서를 가지고 나열하는 모든 경우의 수를 $w_{i, j}$라 하자. (단순히 $\left( j-i+1 \right) !$이 아니다! 중복 원소가 있을 수 있기 때문) 물론 전체 수열을 배열하는 모든 경우의 수는 $w_{1, N}$이다.

 

$dp[i]$ := $b_{1..i}$에 대해서 문제의 답, 즉 모든 원소가 "정렬되지 않은" 상태인 경우의 수.

 

으로 정의하자. 이제 그럼 뭐가 잘.. 잘 겹쳐서 저번 걸 이용해서 잘 계산할 수 있게 된다. $dp[k]$를 계산하기 위해, 여집합인 $b_{1..k}$에서 하나 이상의 원소가 "정렬된" 상태인 경우의 수를 생각해 보자. 이 경우들을 첫번째로 "정렬된" 원소의 위치를 기준으로 분리해 보자. $i$번째 원소가 그런 원소라고 하면, $1$번째부터 $i-1$번째까지의 원소는 모두 "정렬되지 않은" 상태이다. $i+1$번째부터 $k-1$번째의 원소는 어떻게 배열돼 있든 우리 알 바가 아니다. 즉 $i$번째 원소가 첫번째로 "정렬된" 원소이도록 $k$개의 수를 배열하는 가짓수는 $dp[i-1] \times w_{i+1, k}$이다. 따라서

 

$$dp[k] = w_{1, N} \sum _{i=1..k} dp[i-1] \times w_{i+1, k}$$

 

(단, $i>j$이면 $w_{i, j} = 1$이라고 하자.)

 

B - Birthday Boy / junie, 01:26

 

내가 트롤링한 문제 1. 정말 별 것도 아닌 에러 가지고 30분을 삽질했다. 진짜 집에서 다시 짜니 5분컷 나는데 뭐하는 짓이었나 싶다. 문제 자체는 아무것도 없는 구현 문제이다. 생략

 

I - In Case of an Invasion, Please... / rkm0959, 01:44

 

답에 대한 parametric search를 해 보자. 시간 $t$ 안에 모든 시민을 대피시켜야 한다는 조건이 붙으면 각 점은 시간 $t$ 안에 이동할 수 있는지 여부로 $s$개의 대피소에 대해 총 $2^s$개로 분류할 수 있다.

 

대회 때 풀이: 그러면 이제 디닉을 돌리자. s→시민→대피소→t 와 같이 그래프를 만든 뒤 디닉으로 시민의 수만큼 플로우가 흘렀는지 확인한다. 뭐.. 정점 1000개 간선 10000개 scale의 그래프 디닉 50번정도 돌리는 건 시간 안에 잘 돌아갈 거다. 오히려 짜 보면 간단한 다른 풀이와 비슷한 시간에 작동한다.

 

다른 풀이: 모든 시민을 대피시킬 수 있다는 홀의 결혼 정리에 의해 다음과 동치이다. "어떤 대피소의 subset에 대해서도, 이 subset 안에 있는 대피소만을 이용할 수 있는 시민들의 수가 대피소 subset의 용량의 합 이하이면, 모든 시민을 대피시킬 수 있다." 직관적이지는 않지만 자명하다. 따라서, 이를 직접 계산해주면 된다.

 

K - Kingpin Escape / rkm0959 & cjwj5505, 02:58

 

***

 

D - Driver Disagreement / rkm0959, 03:24

 

신기하고 천재적인 풀이가 있었다.

 

***

 

H - Harry the Hamster / junie & cjwj5505, 04:49

 

내가 트롤링한 문제 2. 머리 박아야 한다. (1) 내가 처음에 간선을 m개 받아야 하는데 n개만 받아서 틀림, (2) 원준이가 반례를 찾아내서 그 반례를 고치려고 생쇼함. 그와중에 나는 "이 풀이가 아닌 거 같아. 뭔가 느낌이 우리는 아니야." 이러고 있음, (3) 입력을 잘못 받은 걸 깨닫고 고치지만 그 반례는 고쳐지지 않음. 수 하나가 나와야 하는데 Infinity가 나옴 (4) 알고보니 원준이가 들고 온 반례는 반례가 아니었고, 당연히 Infinity를 출력해야 하는 게 맞았음. (5) 이제 제출했는데 51번 테케에서 틀림. 전부 다 멘탈 나가서 51번 테케 열어봄. (6) 정점이 두 개고 간선이 없는 그래프 처리 안했던 거임. ㅎ;

 

***