JOI 2023 final open contest 후기

어제 JOI 2023 final open contest를 쳤다. JOI 대회들은 항상 퀄리티가 높아서 재미있는 문제도 볼 겸 대회를 쳤다.

 

주의: 아래 후기에는 대회 스포일러가 있다.

 

타임라인

~0:00

오랜만에 cms를 들어가니까 기분이 좋았다. 옛날에 cms로 싸이컴 입부 시험도 치고, 선발고사도 치고 했었는데 대학생이 되니까 cms를 한동안 접할 일이 없었던 것이다. cms는 모든 테스트케이스의 실행시간을 보여줘서 좋고 무엇보다도 초록색으로 100/100을 띄워줘서 기분이 좋다.

 

0:00~0:07

JOI는 항상 문제가 난이도 순으로 배치되어있기 때문에 1번부터 읽었다. 읽으니까 스택으로 슥삭슥삭하면 되는 것처럼 생긴 문제가 있어서 머릿속에 있는 사전지식으로 호다닥 풀었다. 1번에 100을 초록 글씨로 받으니까 기분이 매우 좋았다.

 

0:07~0:16

2번을 읽기 시작했는데 무슨 이상한 식이 있었다. 2차원 좌표평면에 플로팅하니까 적당히 좌표평면을 돌리면 점이 여러 개 주어졌을 때 아래에 있는 점들의 개수를 세주면 되는 문제가 되었다. 역시 머릿속에 있는 사전지식으로 호다닥 풀었다. 2번에서도 1번에 100점을 받았다. 근육으로 문제들을 슥삭 푸는 이 느낌이 매우 좋았다.

 

0:16~1:11

기분 좋게 3번을 읽었는데 무슨 이상한 그래프 문제가 있었다. 내가 만약 이런 문제를 만들었다면 "이게 풀려?" 하면서 쓰레기통으로 넣었을 법한 비주얼이었다. 그리고 숫자 범위가 600만이었다. 600만! 선형이 아니면 잘라버리겠다는 출제자의 강한 의지가 보였다.

하지만 선형 풀이는 보이지가 않았다. 4번 문제나 풀까 생각했는데 4번은 지문이 난해해서 다시 3번으로 돌아왔다. 엉엉 울면서 문제를 어떻게 풀지 생각했다. 그래서 다음 관찰을 했다.

 

1. 한 점에서 큰 사각형을 그려서 이동할거면 그리는 사각형의 가짓수는 8가지면 충분하다.

2. 정사각형 하나는 작은 정사각형 4개로 쪼갤 수 있다.

 

대충 $O(RClogRC)$정도로 86점 먹고 다른 문제 읽을 생각에 코드를 짰다. 구현은 힘든데 풀고 있는게 86점짜리라는 것이 슬펐다. 게다가 숫자 범위가 너무 커서 MLE같은 변수가 생기면 어쩌지 하는 걱정도 구현하는 내내 들었다.

 

제출을 했는데 67점이 나왔다. TLE맞고 사망했다고 생각해서 다음 문제로 넘어가려고 했다. 그런데 TLE는 없고 WA가 있었다. 야호~ 무슨 숫자 하나 잘못 쓴거 디버깅하고 100점 맞고 행복하게 다음 문제로 넘어갔다.

 

1:11~1:39

다시 난해한 지문을 읽을 생각에 정신이 아찔했다. 문제가 좀 지문이 이상해서 질문을 넣었다. 근데 질문 답이 안 왔다. 하긴야 24시간 대회인데 질문에 바로바로 답이 올 리가 없다. 그래서 그냥 이런거겠지~ 하고 찍었다. 예전에 선발고사에서 이렇게 찍었다가 돌돌 말린 경험이 있어서 좀 두려웠다.

문제를 다 읽고 나니까 선형은 너무 쉬웠다. 그냥 세그먼트 트리를 발라주면 된다. 그래서 빠르게 41점 풀이를 짰다.

처음에 41점이 안 나와서 당황했지만 배열 범위 안 고친 것을 깨닫고 다시 제출해서 41점을 받았다. 내가 이해한 문제가 맞았다!

다시  문제를 보니까 100점도 매우 쉬웠다. 그냥 작은 것부터 보면서 스위핑하면 됐다. 호다닥 짜서 100점을 받았다.

 

1:39~2:18

이제 5번 문제밖에 안 남았다! 5번문제를 보는데 상당히 난해했다. 문제가 쿼리 다발을 쿼리로 줘서 정신이 나갈 거 같았다.

모든 JOI 5번이 그렇듯이 관찰 대략 n개 후에 풀리는 문제처럼 생겼다.

침착하게 문제를 해석해보니까 25점이 세그먼트 트리로 긁혔다. 정확히는 "쿼리 다발에서의 쿼리"를 $O(logN)$에 처리하는 방법이 보였다. 구현이 귀찮아서 로그 하나 더 추가해서 25점을 긁었다.

 

2:18~4:00

만점을 위해서는 관찰이 더 필요할텐데, 관찰이 더 안 보였다. 그리고 스코어보드를 보니까 내가 거의 1등이었다. 그 이후로는 마음이 꺾여서 관찰이 뭔지도 모르겠고 그냥 섭태나 훑으면서 조금씩 생각했다. 다들 서브태스크 4를 밀었는데 나는 모르겠다! 멘탈이 조금 바사삭 된 상태로 서브태스크 5를 생각해보니까 항상 판의 왼쪽에는 $R$이 있고 오른쪽에는 $B$가 있다는 것을 알았다. 그래서 판의 상태를 $N+1$개 나타낼 수 있다는 것을 알았다. 그래서 이제 여기에 머지소트 세그먼트 트리를 사용하면 풀리나? 했는데 시간도 그렇고 풀이도 구체화가 안 됐고 마음도 꺾이고 해서 같은 방법으로 서브태스크 4를 밀러 갔다.

 

서브태스크 4는 서브태스크 5의 하위호환이다. $N$이 작아서 머지소트 세그먼트 트리와 같은 자료구조를 쓰지 않아도 된다. 그냥 $(N+1)M$개의 노드를 만들어주고 각 상태에서 버튼을 눌렀을 때 다음 상태로 간선을 이어주면 된다. 그리고 간선을 타주면 된다!

 

약간의 뇌절 후에 sparse table을 사용하면 뚝딱 풀 수 있다는 것을 알았다. 풀이를 짜서 11점을 긁었다. (3:22) 그리고 남은 시간에는 뭐를 할 수 없을 것 같기도 하고 1등이기도 해서 띵가띵가 놀았다.

 

나름 재미있는 대회였던 것 같다. 슼보를 보니까 3번에서 고통받는 사람들이 있는 것 같은데 나는 그냥 원큐에 100점이 떠서 운이 좋았던 것 같다. 4번이 쉬운 것은 상당히 아쉬웠다. 5번은 난해했다는 점에서 마음이 들었다. 나는 관찰 여러 개 하는 문제가 좋은데, 자료구조로 밀어버리는 문제가 나왔으면 실망할 뻔했다. 다음 JOI final round도 재미있으면 좋을 것 같다.

 

에디토리얼 읽은 후 수정: 5번 정해를 보니까 멋진 자구 비빔밥 문제였다. 그래도 관찰이 신선해서 좋은 문제인 것 같다. 섭태 5 풀이는 비슷하게 생각했는데 풀이 구체화 부분에서 좀 말려서 대회에서 못 풀었다. 나중에 업솔빙해야겠다.