scpc 2024 Final Round 후기

scpc는 2021년부터 출전했고, 2022,2023년도에 Final까지 올라갔었습니다.
2022년은 탈 실력이 아니었고, 2023년은 막차탈 실력은 됐었다고 생각하고,
실제로 탈 수 있었는데 놓쳐서 너무 아쉬웠습니다.
 
scpc가 ps하는 잉여 인간들에게는 매우 중요한 대회입니다.
대기업인 삼성에서 매우 큰 혜택이 포함된 삼성SW멤버십에 가입시켜주기 때문입니다.
 
제 팀원이자 서강대 소멤 goat셨던 검굿님이 많이 알려주셨습니다...
 
이번 대회때 점수가 괜찮아 기대하고 있는 심정입니다.
제발 상 타게 해줘~~
 
대회는 13시에 시작했습니다.
 
[13:09] 1. 시간여행 AC
 
파이널 올 실력이라면 다 풀수 있는 문제입니다. 전 min세그를 박아서 풀었는데, 매우 빠르게 풀었다고 생각했는데 이미 10명 넘게 풀려있어서 다시 한 번 고인대회라는 것을 느꼈습니다.
 
그리고 2번을 열어봤는데.... 
회의를 잘 배정하는 문제입니다.
사실 회의실배정의 greedy한 전략은 잘 알려져 있고, 전 이문제의 풀이를 꽤나 빠르게 냈습니다.
문제 세팅상 풀이가 어느정도 정해진다고 생각합니다.
고정된 회의가 있고, 쿼리마다 새 회의가 들어오는데, 고정된 회의의 개수가 많기 때문에
이를 미리 빠르게 처리해줘야할 필요가 있습니다. 이는 sparse table을 이용하면 할 수 있습니다.
 
이후 한 시간 정도 구현했습니다.
 

[14:20] 2.공장 1WA
? 왜틀렸노
 
뭔가를 고치고 또 냅니다.
[14:22] 2.공장 2WA
 
그리고 고라니짓을 15시정도까지 합니다.
[15:03] 2.공장 6WA
 
그리고 반례를 발견하지는 않았는데, 풀이의 오점을 떠올려냅니다. 다행히도 풀이가 달라지는 부분은 없었고, 디테일에서 실수가 있었습니다.
이 문제는 sparse table을 매우 잘 정의해야 했습니다.
(정의할때 단순히 par[i][x]->par[par[i][x-1]][x-1]이 아니라 lower bound를 어케 어케 잘 섞어야 했습니다.)
그래서 이를 구현하러 갑니다.
 
[15:22] 2.공장 7WA
이제 진짜 틀린게 없는데 틀립니다... 하...
이때 진짜 죽고 싶었습니다.
그때 설마 input이 0 base인지 보러 가는데 0 base였습니다. (진짜 레전드 구현 실력)
 
[15:29] 2.공장 8WA
?진짜 왜 틀리지 이제는
이제는 반례도 다 잘나옵니다.
이때 만들어 놓은 테케만 10개는 될겁니다.
사실 여기서 멘탈이 나간게 이미 매몰비용이 너무컸습니다. (사실상 2시간 반을 쓴셈)
 
그래서 사실상 바뀐게 없는데 2번 더 냅니다. 
 
[15:29] 2.공장  10WA
이때 진짜 슬펐는데 매몰비용이 너무 커서 테케나 만들러 갑니다.
 
?기적같이 반례를 하나 발견했습니다.

이런 부분이 있었는데

아래처럼 바꾸면 맞습니다.
이건 제 구현이 너무 더러워서 했던 실수 같습니다.
 
[15:41] 2.공장 AC 
맞았습니다. 이때 2번 만점자수가 32명? 31명? 정도에 3번 만점자수가 6명? 정도였던 것 같습니다.
 
그 뒤로는 사실 별 게 없는게
안 까불고 4번 20점짜리 실버 테케랑
3번 39점짜리 골드 애드혹 테케 긁었습니다.
 
이때가 16:11분 정도인 것 같습니다.
 
그리고 나머지 시간에 저는  3번 N<=300짜리 고민하다가 시간을 다 썼습니다.
 
결국 359점으로 마무리 했는데... 상타게 해주십쇼...
나머지 지인들도 다 탔으면 좋겠습니다.



수정:
5등상 수상했네요~~ 😄