230715 팀 연습 (2018 KAIST 8th ACM-ICPC Mock Competition)

사실 1학기나 방학 기간에도 팀 연습을 꾸준히 하긴 했는데, 그닥 열심히 하지 않았을 뿐더러 바빠서 정리를 하지 않았다. 이번 주말부터 연습을 조금씩 하기 시작했는데, 까먹기 전에 정리해두려 한다.
 
셋 : https://www.acmicpc.net/category/detail/1923

스코어보드에 나타나는 각 팀의 구성 인원은 아래와 같다.
team_000102 : qjatn0120baek, menborong, tony9402
leo020630 : leo020630
slahpasa : slah007, pasa3232

slahpasa 팀이 군인이어서 3시간, N컴으로 연습을 진행하였다.
 
~0:02
문제가 많아서 다 펼쳐놓고 가장 짧은 문제를 읽었다. 다행히도 가장 짧은 문제인 I가 가장 쉬운 문제여서 풀었다.
 
~0:38
F가 풀려서 읽었다. 식을 정리해보니 대충 누적합+Harmonic Lemma로 될 것 같아서 짰다. 구현을 이상하게 해 3번이나 틀렸다.
 
~0:48
이리저리 방황하다 L번의 시간 제한이 10초라는 사실을 확인하고 읽었다. 어려워 보이지만 \(NQ \leq 5 \times 10^8\)이라 그냥 나이브를 짜주면 됐다. 바로 짜서 AC를 받았다.
 
~1:12
스코어보드에서 풀린 G, J를 같이 봤다. G는 대충 그런디 DP였고, J는 읽으니 식 정리를 조금만 하면 쉬워서 바로 풀 수 있었다.
 
~1:30
생각을 열심히 했더니 G도 크게 어렵진 않았다. 나름 전형적인 문제였기에 쉽게 짰다. 여기까지 풀었더니 team_000102가 B, C, D를 다 풀어놓아서 조금 어지러웠다. slahpasa도 B에 제출이 있길래 B를 보러 갔다.
 
~2:04
B는 각 정점이 진짜 있을 수 있는 범위만 구한다면 그 뒤는 그리디하게 처리할 수 있을 것 같았지만, 그 방법이 쉽게 보이지 않았다. 적절한 DP식에 대해 생각하다가, 괜찮은 방법이 떠올라 대충 믿음을 가지고 돌린 후 냈더니 맞았다. 기뻐하면서 D로 넘어갔다.
 
~2:59
D는 쉬워 보였지만 뭔가 적절한 방법이 바로 떠오르지 않았다. 고민을 여러 번 하다, 두 크기의 트리를 한 번에 관리하면 된다는 사실을 깨달았다. 끝이 10분 정도 남았었는데, 후다닥 짜고 버그를 하나 고쳐서 59분 39초에 맞을 수 있었다. 이 정도로 아슬아슬하게 AC를 받은 것은 실제 대회에서도 없었어서 상당히 짜릿했다.
 

문제별 요약

A (D3, Not solved) : 문제를 읽지 않았다.
B (P1, solved by leo020630) : 우선 사이클이 있으면 불가능함은 자명하다. 따라서 그래프를 DAG로 생각할 수 있다. 이제 잘 생각해보면, 문제에서 주어진 \([L_i,R_i]\)에서 실제로 가능한 구간을 구하면 그 뒤는 그리디하게 처리할 수 있다. 각 번호에 대해 사용할 수 있으면서 끝이 가장 빠른 구간을 사용하면 된다. 그러면 이 "실제로 가능한 구간"을 구하는 것이 문제인데, 이는 \(u\)에서 \(v\)로 향하는 노드가 있다고 할 때, \(L_u = max(L_u, L_v + 1)\), \(R_v = min(R_v, R_u - 1)\)과 같은 DP를 수행해 불가능한 부분을 줄이면 된다. 이 과정만 수행하면 됨을 보이는 것이 핵심이면서도 어려운데, exchange argument를 이용한다. \(v \Leftarrow u\)에 대해, \(L_v < L_u, R_v < R_u\)이기 때문에 \(v\)가 항상 \(u\)보다 먼저 사용된다. 따라서 위상 정렬 순서를 자연스럽게 만족하게 된다. 굉장히 좋은 문제인 것 같다.
C (D5, Not solved) : 문제를 읽지 않았다.
D (P5, solved by leo020630) : 쉬워 보이는데 어려운 문제이다. 대충 \(2\log{N}\) 수준의 해답이 필요한데, 재귀 호출을 하는 과정에서 \(x\)가 홀수일 때 \( \lfloor \frac{x}{2} \rfloor \)와 \( \lceil \frac{x}{2} \rceil \)를 모두 호출하면 로그 스케일이 아니라는 점이 문제가 된다. 이를 해결하는 방법이 굉장히 창의적인데, 재귀 호출을 하는 과정에서 \(x\)와 \(x+1\)에 대한 답을 같이 저장하면 자식 노드에서 가져와야 하는 값도 길이 2의 연속된 구간임을 계속 만족해서 로그 스케일에 답을 구할 수 있다. 좋은 문제라고 생각한다.
E (D5, Not solved) : 문제를 읽지 않았다.
F (G4, solved by leo020630) : 식을 정리해주면 \(x,y \leq 999, (x,y)=1\)인 개수를 부분합으로 구하고 Harmonic Lemma로 계산해줄 수 있는 형태가 나온다. 정해는 이렇게까지 하지 않고 머리를 조금 더 쓰면 Harmonic Lemma도 필요가 없어진다. 머리가 나쁘면 몸이 고생한다.
G (P3, solved by leo020630) : 선을 하나 그으면 어차피 해당 두 점은 쓰지 못한다. 따라서 크기 \(N\)인 게임을 \(x, N-2-x\)로 나눌 수 있다. 나머지는 그냥 그런디 DP를 구현하면 된다.
H (P1, Not solved) : 문제를 읽지 않았다.
I (B1, solved by leo020630) : 비교 과정을 잘 생각해보면 평범한 팰린드롬과 매칭되는 방식이 똑같아서 그냥 주어진 문자열이 회문인지만 판별해주면 된다.
J (G3, solved by leo020630) : 선분에 대한 식 정리만 잘 해주면 나이브하게 해결할 수 있다. 각 봉우리와 사람을 지나는 선분을 모두 구한 뒤, y절편의 최댓값을 구하면 된다.
K (D3, Not solved) : 문제를 읽지 않았다.
L (S1, solved by leo020630) : 무서워 보이지만 TL이 10초라 그냥 브루트포스를 짜면 된다. 아마 낚시성으로 넣어진 문제인 것 같다.
 

느낀 점

믿고 보는 카이스트답게 문제가 좋았다. 원래 5시간짜리 셋인 만큼 시간이 더 있었으면 좋았을 것 같기도 하다. 혼자 하니까 스코어보드를 따라가는데 급급해서 읽지 못한 문제가 많았다.