2주차 멘토교육 - Ceoi 24 day1

결과 : 100 / 27.x / 100 → 227.x

0:20

문제 3개를 다 읽었다.

• 1번 문제 Naval Battle이 APIO의 쿠나이의 하위 호환 문제라는 것을 알았다.
• 2번 문제는 일단 확률이 있고, 휴리스틱 느낌이 나는 인터렉티브 문제였다. 문제가 간단해서 소개하자면 :

N명의 사람이 있고, 각각의 사람이 감염되었을 확률은 P이다. 몇 명의 사람을 골라서 그 중 하나라도 감염된 사람이 있는지 판별하는 쿼리를 시행할 수 있을때, 모든 사람의 감염 여부를 알기 위해서 시행해야 하는 쿼리 횟수의 기댓값은? (P에 따라 만점 쿼리 횟수가 제시되고 300번 시행해서 쿼리 횟수의 평균을 냄)

으.. 일단 마지막에 풀어야겠다고 생각했다.

• 3번 문제는 뭐가 많아서 처음 볼 때는 어려워 보였다.

쿠나이 문제는 풀어본 적이 없지만, 대략적인 풀이 흐름은 알고 있었기 때문에 1번을 잡았다.

1번 문제는 풀이 찾기는 별로 어렵지 않았다. 반면 구현이 상당히 빡세기 때문에 최대한 이쁜 구현을 하려고 구현 구상에 시간을 많이 쏟았고, 덕분에 100줄 이내의 비교적 깔끔한 구현으로 문제를 해결할 수 있었다.

1:15 - 1번 솔브

이후 3번 문제인 Text Editor 문제를 잡았다. 좌표압축과 그래프 모델링을 통해 N^2 log N 풀이를 생각해낼 수 있었고 이를 구현하였다.

2:00 - 2번 56점

2번의 풀 테스크를 제외한 모든 점수인 56점을 받았다. 또한 스택을 이용해 필요없는 정점은 없앨 수 있다는 관찰을 통해 100점 풀이를 찾을 수 있었다. 이를 20~30분 정도 소요해서 짤 수 있었다.

2:30 부근 - 2번 56점 (풀테 TLE)

반면, N log N 풀이를 짰음에도 불구하고 상수가 커서 100점을 맞지 못하는 불상사가 발생했다. 내가 너무 복잡하게 구현한 감도 없지 않아 있다만 상수 차이로 TLE가 난다는 사실이 화가 났다. 그냥 10만으로 해도 N^2 풀이는 막을 수 있는데 왜 100만으로 줘서 시간제한을 빡빡하게 하는지.. 출제자 욕을 하면서 1시간 가량 상수를 줄이려고 시도하다가, 계속 안 되서 2번 문제인 Covid를 잡았다.

3:30 부근 - Covid 16.84

10점은 매우 자명하게 얻을 수 있었다. 반면 이후 풀이는 어떤 방식을 써야 할지 감이 안 잡힌다.. 기 보단 할 수 있는 짓이 너무 많아서 이 중 무엇을 택해야할지가 관건이였다. 일단 가장 간단하게 구현할 수 있는 버킷으로 나누기를 짜니 6.84점을 더 얻을 수 있었다. 이후 DP로 기댓값을 계산하는 풀이를 생각했지만, 구현하진 않았다.

Covid 득점이 상당히 어려워서 3번 상수컷팅을 더욱 열심히 해보았다. 3번 구현을 좀 이상하게 해서 중간에 RMQ도 썼는데, RMQ를 O(1)로 바꾸니까 3번이 돌았다.

3:45 - 3번 솔브

이제 마음놓고 2번 문제를 풀 수 있었다. DP로 기댓값을 계산해서 최적 전략을 찾는 방안을 생각했다. 이를 구현해보았다.

4:15 부근 - Covid 22점

DP에서 계산한 기댓값에 따른 결과보다 훨씬 낮은 점수가 나왔다. 이후 DP에서 큰 실수를 하였다는 것을 깨달았다. 최소한 1명이 양성이라는 것이 보장되면, 확률 분포가 달라질 텐데 이를 간과했다는 것이다.

이렇게 DP 풀이에 확신이 없었기 때문에 그냥 DNC 기반 풀이를 다시 생각해 간단하게 구현해보았다. 시간이 없어서 초조해서 그런지 구현 미스를 많이 했다.

4:50 - Covid 27.x점

나중에 보니 Covid 문제의 정해는 DP 풀이를 잘 하는 것이라고 한다. DNC 풀이를 잘 해도 고득점을 얻을 수 있다고 한다.

후기

실제 CEOI 2024 스코어보드를 본 결과 day 1기준 8등정도의 성적이였다. Text Editor 문제가 백준에서는 플5던데, 실제로는 많이 안 풀렸고 나도 어려운 문제라고 생각했다. 그리고 내 풀이를 백준에 제출한 결과 안 돌았다..

• 1번 문제가 구현이 어려웠지만 침착하게 구현을 잘 한 점은 좋았다.
• 반면 3번 문제에서 시간을 너무 많이 쓴 것 같고, 너무 복잡한 풀이를 생각한 것 같다. 정해 에디토리얼은 케이스 워크였다.
• 그리고 2번 문제같이 휴리스틱적인 유형이 IOI에서 꽤나 많이 나오는데, 고득점을 하지 못한 점이 아쉽다. 실제 대회에선 만점이 2명 나오고, 고득점자도 꽤나 많았다. 사실 모든 정보를 기반으로 확률을 정확하게 계산할 수는 없기 때문에, 근사적으로 어떻게 식을 세울지에 대한 감이 중요한 것 같다.
• 이후 백준에서 2번 문제의 DP풀이를 개선한 결과 (최소한 하나가 양성인 state를 따로 정의함) 56점 정도를 맞을 수 있었다. 이것을 대회중에 했으면 더 좋았을 것 같다.