2024 한국정보올림피아드 고등부 2차 대회

2024년 7월 14일에 진행한 한국정보올림피아드 고등부 2차대회 일지입니다. 작년에 “잘 본 것 같기는 한데 뭔가 아쉬운 느낌은 항상 드는 것 같습니다” 라고 썼는데, 올해는 그냥 못 본 것 같습니다. 마음이 아프네요.

대회 결과는 1, 2, 3번에서 100점, 4점에서 4점을 받아 304점입니다.

대회 시작 전

• 솔브드 디코에서 이런저런 이야기를 나누었습니다. 경곽 응시자가 66명이라는 이야기를 했습니다.
• 40기 디코에서 이런저런 이야기를 나누었습니다. 1번 난이도를 예상했고 저는 골드 2를 찍었습니다.
• 고등부 1고사실이었고 1번째로 신분증 검사를 받았습니다. (끝나고 1등으로 퇴실하겠다는 것을 직감했습니다.)

0:00~0:17 - 0점>100점

• 고1번 가로등 문제를 잡았습니다.
• 바로 imos 기반의 만점 풀이가 떠올랐습니다. 구현했고 두어 번 틀린 뒤 맞았습니다. (0:17:32)

0:17~0:30 - 100점

• 고2번 XOR 최대 문제를 잡았습니다.
• 발상: 두 문자열 중 하나는 전체 문자열입니다. 이 문자열에서 처음으로 0이 되는 비트가 있을 텐데, 그 비트가 1이 되도록 수를 잘 골라주면 됩니다.

0:30~0:31 - 100점

• 고3번 트리 뽑아내기 문제를 읽었습니다.
• 고2번이 너무 풀릴 것 같아서 다시 잡았습니다.

0:31~1:10 - 100점

• 고2번 XOR 최대 문제로 돌아왔습니다.
• 0:45. Claim: 전체 문자열에서 처음 나오는 1 뒤의 문자열을 복사해서, 0은 1로, 1은 0으로 만듭니다. 이 문자열이 ‘목표 문자열’입니다. 이 문자열과 최대한 길게 같은 문자열을 뽑고자 합니다.
• 0:50. 발상: 이때, 목표 문자열만큼 1이 상위 비트에 있는 문자열은 초반의 문자열밖에 없습니다. 따라서 전체 문자열을 오른쪽으로 몇 번 shift해서 원래 문자열과 XOR하면 됩니다.
• 구현했고 틀렸습니다. (1:10:44)

1:10~1:43 - 100점

• 여기에 KMP와 비슷한 무언가를 추가했습니다. 원리는 지금의 저도 정확하게 알지 못합니다만, 60% 정도의 확신을 가지고 구현했습니다.
• 1:15) 관찰: 생각해보니 두 문자열의 가장 오른쪽 비트가 일치한 상태로 xor해야 합니다. 앞에서부터 매칭하는 방식을 사용할 수 없습니다. 즉 뒤에서부터 매칭합니다.
• 구현했고 틀렸습니다.
• 생각해보니, 뒤에서부터 매칭하면 상위 비트를 우선적으로 비교할 수 없습니다. 무언가 잘못되었습니다.
• 1:34) 처음 발상으로 돌아가서, 결국 최초로 나오는 1을 찾고 그 다음 최초로 0이 나올 때까지 shift해서 둘을 xor하면 되는 것 같습니다.
• 3번 혹은 4번 테케에서 틀렸습니다.

1:43~2:15 - 100점>106점>200점

• 고3번 트리 뽑아내기 문제로 돌아왔습니다.
• 1:50) 관찰: 루트는 다음에 빼는 것이 결정되어 있으므로, 루트의 자식을 뭔가 pq 같은 것으로 관리한다고 칩시다. 그중 가장 작은 것을 고르면, 그 정점이 새로운 루트가 되는 동시에 그 자식이 모두 pq에 들어옵니다. 즉 자식의 집합을 merge하는 것과 같습니다. small to large를 매우 정석적으로 사용할 수 있을 것으로 보입니다.
• 16분간 구현했고 틀렸습니다.
• 8분 간 고쳤고 6점을 받았습니다. (2:14:45)
• 배열의 크기를 키웠고 100점을 받았습니다. (2:15:11)

2:15~2:50 - 200점>300점

• 1:34 발상의 반례를 찾고자 했습니다.
• 2:20) 관찰: 생각해보니, 최초로 나오는 1 뒤로 1이 많이 연속해 있다면 반례가 됩니다. 예를 들어, ‘111101010’은 ‘111111111’으로 만들 수 있습니다.
• 2:25) 발상: 지금이야말로 1:15 관찰의 방법을 가져다 쓰면 돨 것 같습니다.
• 예제에서 막혔습니다.
• 2:30) 발상: 그냥, 최초로 나오는 1 뒤로 연속한 1의 개수와 그 다음에 나오는 0부터 시작해 연속한 0의 개수를 세고 둘 중 더 작은 것만큼 겹차도록 shift해주는 것이 맞는 것 같습니다.
• 틀렸습니다. (2:39:25)
• 생각해보니 한 번 쓰기 시작했으면 끝까지 다 써야 합니다. (그렇지 않아도 된다는 생각은 1:15 관찰에서 나왔습니다. 왜 그런 생각을 했을까요?)
• 11분간 수정했고 100점을 받았습니다. (2:50:03)

2:50~3:00 - 300점

• 고4번 점수 경주 문제를 잡았습니다.
• 아마 풀테를 잡을 수 없을 것이라 생각했고, 10분만 생각해본 뒤에 섭테를 긁기로 했습니다.
• 섭테를 긁기로 했습니다.

3:00~3:38 - 300점>301점>302점

• 섭테는 1, 2, 4번이 풀만하다고 판단했고, 여기에 시간이 된다면 3번을 생각해볼 수 있겠다고 보았습니다.
• 1번 섭테를 잡았고 약 15분간 구현했고, 2점을 맞아야 할 솔루션이 1점을 맞았습니다. (3:23:50)
• 디버깅에 15분을 썼고(별 것 아닌 이유였는데 오래 걸렸습니다), 2점을 맞았습니다. (3:38:53)

3:38~4:20 - 302점>304점

• 섭테 4로 넘어갔고, 24분 정도 걸려 구현했습니다.
• 4점을 받아야 할 솔루션이 틀렸습니다. (4:02:28)
• 디버깅에 18분을 썼고(역시나 카운팅을 제대로 안 해서 틀렸던 것 같습니다), 4점을 받아야 할 솔루션이 2점을 받았습니다. (4:20:41)

4:20~4:29 - 304점

• 디버깅에 10분을 썼지만 고칠 수 없었습니다.

4:29~4:30 - 304점

• 정리했습니다.

후기

• 솔직히 312까지는 긁었어야 하는데(그리고 312점을 받은 사람이 적어도 5명으로 보이는데), 많이 아쉽습니다. 마지막 90분을 너무 못 쓴 것 같습니다.
• 패착의 요인이라면 디버깅에 너무 많은 시간을 썼다는 것 같습니다. 코드포스나 백준을 하면서 breakpoint형 디버깅에 너무 익숙해져 있었던 것 같습니다.
  • 4번의 섭테를 얼마나 잘 긁는가가 금-은상, 은-동상의 커트를 모두 결정하게 될 것 같습니다. (2, 3번이 쉽긴 했지만 그래도 3번까지 풀었으면 4번을 안 긁었어도 은상을 받아갈 수 있었으면 하는데요.)
• 의외로 3번까지 딱히 알고리즘이나 자료구조가 필요 없었습니다. 저는 3번에서 작큰을 쓰긴 했지만 이것도 작큰 스킬 없이 우선순위 큐 하나로 해결 가능합니다. 2번도 애드혹이고 1번도 쉬웠습니다.
• 그래서 그런 건지, 나코더 40기에 에 300을 받지 못한 친구들이 많아서 슬픕니다. 계속 ps를 해왔던 친구들에 비해 그냥 머리 좋은 애들이 높은 점수를 받아간 것 같아 약간 안타깝습니다.
• 저만 보자면, 머리도 애매하고(즉 애구그를 애매하게 잘 풀고) 자구/알고도 애매하게 알아서(즉 센트나 cht를 현장에서 n분만에 구현할 자신이 없는 정도) 점수도 애매하게 304점만 나온 것 같네요.
• 이상으로 정올 라스트댄스를 마치게 되었습니다. 짧다면 짧고 길다면 길 3년 ps 인생의 기점에 다다랐는데, 그런 것치고는 3번 섭테가 너무 많은 것을 결정 + 근데 나는 3번 섭테에서 말림 이슈로 아쉽습니다. 그냥너무아쉬워요322만받았어도좋은데응애;;;
• 앞으로도 ps러 인생을 살게 되지 않을까 싶습니다. 일단 방학 중에 코포 2200 정도를 복구하고 앳코더 옐로우를 찍고 싶고, NYPC 본선에서 노트북도 받고 싶습니다. 졸업 전에는 레드를 가는 것이 목표입니다.