IOI 2022 후기

이번 IOI에서 Day1 27등, Day2 18등, 종합 22등의 성적을 거두어 금메달을 받게 되었습니다.

제가 대회를 치르면서 어떤 풀이를 생각했고, 어떤 전략을 사용했는지를 써 보겠습니다.

 

Day 1

시작~1시간 30분

평소에 하던 대로, 1시간 30분까지는 구현을 하지 않고 풀이만 생각한 뒤에, 구현은 그 뒤에 몰아서 하기로 했습니다. A번은 dp식을 잘 세우면 누적합이나 세그먼트 트리로 풀 수 있어 보이는 쉬운 문제라 생각을 했고, B번은 재밌어 보이는 인터렉티브 형식이지만 너무 잡으면 망할 듯한 문제, 3번은 41까지는 쉽고 그 뒤는 어려운 문제라 생각을 했습니다.

1번을 무조건 풀어야 한다고 생각해서 30분~1시간 30분까지는 1번만 생각했습니다. 1번의 최적해는 그물의 길이가 증가하다가 감소하여 0이 된 뒤, 다시 증가하고 감소하는 것을 반복하는 형태라는 관찰을 했고, 이를 바탕으로 케이스 워크를 하는 dp 풀이를 냈습니다.

2번과 3번은 30분 전에 생각한 48.5점과 41점 풀이만 생각하고 있는 상태로 1번 구현에 들어갔습니다.

1시간 30분~2시간 32분

1번을 구현했습니다. 현재 증가하는 상황, 감소하는 상황, 0인 상황에 대해 dp를 세우고, 이들을 부분 최댓값 등의 배열을 사용해 전이하였는데, 구현이 꽤 어렵고 실수할 여지가 많았습니다. 2시간 1분에 구현을 완료하고 제출을 했지만, 예상대로 WA가 나왔습니다. 그 뒤에 30분 동안 디버깅을 하여 AC를 맞았고, 은메달 성적은 나올 것 같다는 생각을 했습니다.

2시간 32분~2시간 55분

2번에서 48.5 풀이를 구현하였습니다. 만약에 현재 칠판에 써있는 숫자가 0이면 A를 본 뒤 A를 3진수로 나타내었을 때 7번째 비트+1을 칠판에 쓰고, 1,2,3이 있으면 B를 봐 비교한 뒤 서로 다르면 결과를 주고, 같으면 4를 써주고, 이를 모든 비트에 대해 반복하는 풀이입니다. 너무 최적화를 많이 시도하다가는 3번 문제의 서브태스크를를 많이 긁지 못할 것 같아서, 최대한 생각이 필요없는 코드를 짜서 맞았습니다.

2시간 55분~3시간 55분

3번의 여러 서브태스크를 풀었습니다.

1번 서브태스크: 가장 왼쪽과 가장 오른쪽 2개만 후보이고, 이 두개를 같이 선택 가능하면 2, 아니면 1입니다.

4번 서브태스크: 왼쪽 원소와 오른쪽 원소가 모두 자신보다 크면 집합에 넣어주면 됩니다.

2,3번 서브태스크: 카르테시안 트리를 만든 뒤, 트리dp를 해 줍니다. dp식은 dp[i]=max(i의 서브트리에서의 최솟값<=부모의 값-D이면 1, 아니면 0,모든 자식의 dp값의 합)입니다.

5번 서브태스크: 2,3번 서브태스크의 dp 값이 변하는 D를 저장해 주면 풀 수 있습니다

그 뒤

3번에서 3진수를 4진수로 바꾸되 마지막 자리는 5진수로 나타내고, 마지막 자리를 볼 때 0이나 4이면 바로 리턴해주는 등의 최적화를 하여 53점을 맞았습니다. 이때는 제가 플래티넘 섭테만 다 풀었다고 생각을 하고 있었습니다

끝나고 난 후

스코어보드를 봤는데, 1번 100과 3번 58이 모두 다이아였고, 오히려 2번 80이 플레였습니다. 3문제 중에 2문제에서만 금메달 급의 점수를 맞아도 금메달 성적이 나와서 어느 정도 자신감이 생겼습니다.

Day 2

시작~1시간 20분

저번과 똑같이 1시간 20분까지는 긁을 수 있는 섭테를 생각했습니다. 1번은 보고 5분 뒤 답이 리프 i의 값*어떤 수 형식으로 될 것이라는 거를 떠올린 후, i를 1로 하는 가짓수는 i의 자식은 1로 하는 가짓수*(나머지 서브트리들을 정하는 가짓수)임을 알아차렸습니다.

2번은 10분 정도 생각하고 나니 답에 대해서 이분탐색을 해주면서, 답이 X 이상인지는 가장 많이 나오는 종류가 X번 이하로 나오도록 최대한 넣었을 때 모든 종류가 X번 들어갔는지를 판별해주면 됩니다. 쿼리 횟수는 N로그N이지만, 최적화 여지가 많이 보였습니다. 몇 가지 종류가 있는지는 X=1로 해주면 됩니다.

3번은 55점을 받을 수 있을 것으로 보였지만, 케이스가 많아 전부 다 생각하지는 않았습니다.

1시간 20분~1시간 55분

1번을 구현했습니다. 구현은 부분 곱 배열을 사용해서 했고, 오버플로우로 한 번 틀린 뒤 AC를 받았습니다.

1시간 55분~2시간 45분

2번을 구현했습니다. 위 풀이에서는 답이 X였을 때 성공하였으면 들어간 것이 X 이상의 답에 무조건 들어간다는 최적화를 할 수 있습니다. X였을 때 실패하였을 경우의 최적화를 생각하지 못해 50점이 나왔지만, 최악의 케이스인 1 2 2 2 2 .....을 찾을 수 있었고, 배열을 랜덤으로 섞은 뒤 답이 4 이상인지 체크를 하고, 4 미만이면 이분탐색이 빨리 끝나니 91점 정도가 나왔습니다.

2시간 55분~3시간 55분

3번의 여러 서브태스크를 풀었습니다.

1번 서브태스크: 0에서 1로 가는 것이 2개 이상이고, 1에서 0으로 가는 것이 있으면 됩니다. 

2번 서브태스크: 0에서 1, 1에서 2, 2에서 0으로 간 뒤 역방향으로 가고, 이를 한 번 더 해주면 됩니다.

3번 서브태스크: 사이클이 있어야 되는 줄 알고 틀렸는데, 사이클이 없어도 0번 정점의 디그리가 2 이상이거나 0과 연결되어 있고 디그리가 3 이상인 정점이 있으면 됩니다. 0번 정점의 디그리가 2 이상이면 0번에서 한 간선을 왕복했다가 다른 간선을 가는 것을 2번 해주면 되고, 디그리가 3 이상인 정점이 있으면 0에서 그 정점까지 간 뒤 이를 해주면 됩니다.

4번 서브태스크:사이클이 있어야 하고, 사이클이 있을 때는 사이클까지 갔다가 사이클을 돈 뒤 돌아오고, 중복된 간선으로 이를 한번 다시 가주고, 이를 역방향으로 한번 더 해주면 됩니다.

그 이후

3번의 만점 서브태스크 중 35%를 뚫으려다 실패하고, 2번의 랜덤 시드를 바꾸어 내서 93점을 받았습니다.

끝나고 난 후

스코어보드를 보고 나니 1번이 예상보다 3배 이상 안 풀렸고, 쉬울 수도 있었다 생각한 3번은 어려웠습니다. 저번보다 좋은 성적으로 금메달을 받게 되서 다행이였고, 앞으로도 이 전략을 사용하여 좋은 성적을 받을 수 있으면 좋겠습니다.