1월 25일 연습 (JOIOC 2022)

선발고사가 얼마 안 남아서, 부분 문제 긁는 연습을 위해 셋을 하나 돌았다.

https://contests.ioi-jp.org/open-2022/

JOI Open Contest 2022

 

이 글은 대회 연습 후기 글로, 간단한 풀이 외의 풀이 글은 업솔빙 이후 따로 작성할 예정이다. 아마 작성되면 이 글 상단에 링크로 달 예정이다.

 

oj.uz에 세 번째 문제가 안 올라와 있어서 백준에서 그룹 만들고 했다. 2시 40분부터 시작해서 7시 40분까지 5시간 시간을 재고 했다. 실제로는 더 빨리 나왔다.

 

점수

Seesaw 100/100

Giraffes 59/100

School Road 45/100

총합 204/300

 

약간 졸리고 집중도 잘 안된 것 같은데, 의외로 점수가 잘 나왔다. 이 점수는 오픈 컨테스트 기준 16/136등에 해당하는 점수이다. (점수 분포를 보면 5시간동안 제대로 응시하지 않은 사람도 꽤 있는 것 같다)

 

solved.ac 티어 기준 세 문제는 D4, R5, D4이다. 3번은 더 높을 줄 알았는데, 생각보다 낮았다.

 

연습 기록

추후 복기를 위해 작성

 

0:00 ~ 0:20 (0 / 0 / 0)

문제를 읽었다. 노트에 적으면서 읽느라 약간 오래 걸린 것 같다.

 

0:21 ~ 0:25 (0 / 0 / 7)

마지막으로 읽은 문제인 3번 문제의 부분 문제 1 코드를 짰다. $M \le 40$이기도 하고, 배점도 제일 작아서 정확한 계산 없이도 백트래킹이 시간 내에 동작함을 유추할 수 있었다. 한 번에 맞았다.

 

0:26 ~ 0:47 (0 / 0 / 22)

3번 문제의 부분 문제 2 코드를 짰다. $N \le 18$인데, $O(2^N \times NM)$정도 시간 복잡도로 짰다. 간략하게 설명하자면, 이때까지 간 정점 집합을 $0~2^{18}-1$까지의 자연수 집합으로 관리하면 된다. 0-based와 1-based를 햇갈려서 약간 구현이 지체된 것 같다.

 

0:48 ~ 1:16 (0 / 32 / 2)

3번 문제를 이것저것 더 시도해 보다가, 쉽게 풀리는 섭테가 안 보여서 50분쯤 2번으로 넘어왔다. 조건 만족하는 배열이 $1, N$이 양끝 중 하나에 배치되는 것으로 재귀적으로 정의된다는 관찰을 하고, 길이 13이하의 조건 만족하는 배열의 수가 생각보다 많지 않음을 관찰하고 배열을 전부 계산해서 저장하는 코드를 짰다. 로컬에서 10초 넘게 걸렸는데, 신기하게 백준에서는 1초정도에 돌았다.

 

1:17 ~ 2:52 (100 / 32 / 22)

2, 3번에서 20분 안에 풀리는 섭테는 전부 구현했다고 생각하고, 1번으로 넘어왔다. $l$, $r$로 가능한 값의 갯수가 $O(N^2)$임을 이용해 세제곱로그 풀이를 찾았고, 이것저것 관찰을 해서 풀테까지 발전시키는데 성공했다. 뭔가 더 빨리 할 수 있었던 것 같은데, 잘못된 관찰을 해서 약간 시간이 지체되고, 구현에서도 약간 말렸던 것 같다. 제곱 풀이를 찾은게 2:10쯤이었던 것 같다.

 

2:53 ~ 3:20 (100 / 59 / 22)

2번 문제의 세제곱 풀이가 dp로 된다는 사실을 알아채고, 네제곱 풀이를 생각해냈다. 여기서 변수 하나를 줄여 세제곱으로 만들었고, 짜서 맞았다.

 

3:21 ~ 4:30 (100 / 59 / 45)

3:21 시점 남은 부분 문제는 2번의 풀테, 3번의 부분 문제 3, 4, 5가 있었다. 2번의 풀테의 경우, 입력이 랜덤으로 주어지고, 데이터가 10개인 등 지금까지 단 한번도 보지 못한 특이한 조건이 주어졌는데, 그래서 어려울 것으로 생각하고 3번으로 넘어가기로 했다. 3번의 3번 섭테는 트리 형태에 간선이 최대 14개 추가될 수 있는 그래프였다. 그런데 나는 계속 $O(2^{14})$가 시복에 들어가는 비트디피에 초점을 맞춰 생각했었고, 많은 시간을 낭비했다. 결국 차수 1 정점을 연쇄적으로 없에고, 40여개의 간선을 제외한 나머지 간선들은 합쳐도 된다는 관찰을 했고, 늦게나마 45점을 받았다. 이 뒤로는 더 긁을 섭테도 없어 보이고 피곤해서 그만했다.