2023 ICPC Seoul Regional First Round (인터넷 예선)

(23.10.30 - 스코어보드를 추가하였습니다.)

http://static.icpckorea.net/2023/first_round/scoreboard/

설.카.숭.

'2솔 이하라면 아무도 본선에 못 갈 것 같다'는 말을 썼긴 했지만, 진짜로 그렇게 될 줄은 몰랐습니다.. 다행히 경희대 팀 중 두 팀(Hwang leftovers, NHBK)이 3솔을 하였고, 규칙에 따라 Hwang leftovers 팀이 본선에 진출할 수 있게 되었습니다. 축하합니다! 

 

(경희대 내 1등 팀인 wa on test 287팀이 본선 선발 명단에 빠져있는 걸 보니 휴학 이슈가 있는 듯 합니다. 개인적으로 기대했던 팀이었는데, 아쉽게 됐네요.)

 

 

 

 

 

(23.10.22 - 스코어보드 프리즈 전 상황만 기술하였습니다.)

 

군대 이슈로 이번 ICPC는 참가하지 못하였습니다. 휴학생 팀이라도 꾸려서 외박으로 예선만 보는 것도 생각해봤는데, 이래저래 피곤할 것 같아 올해는 좀만 참기로 했습니다. 아마 본선은 미러로 참여해볼 것 같습니다.

 

이번 ICPC부터 몇 가지가 달라진다고 들었습니다. 우선 Seoul Regional 한정으로, 올해부터 파이썬(!)을 사용할 수 있게 되었다는 점. World Finals에서도 파이썬을 사용할 수 있는데, 그 하위 리저널에서 사용하지 못한다는 점이 의아했었는데, 올해부터 사용할 수 있게 된 것은 반가운 소식인 것 같습니다. 또 한 가지는 Regional 성적만으로는 World Finals 진출을 확정지을 수 없다는 점. 원래는 Regional에서 대학 3등 이내에 들면 World Finals 진출이 거진 확정이었는데, 슈퍼 리저널인가 뭔가가 더 생겨 진출 방식이 조금 복잡해진 것 같습니다. 2023-2024부터 새로 생긴 규칙이라 어떻게 진행될지는 좀 더 지켜봐야겠습니다.

 

이번 Regional 예선에서 경희대 팀은 예년보다 적은 참가 수를 보여주었습니다. 보통 30팀 조금 안 되는 팀 수로 참가해왔는데, 이번에는 19팀이 참가하였습니다. (ㅠㅠ) 작년부터 좋은 성적을 보여줬던 팀인 WA oN tEsT 287팀이 올해에도 동일한 팀 이름으로(대소문자가 바뀌긴 했는데 아무튼) 2023 Seoul Regional에 참여했습니다. 큰 무리없이 본선에 진출할 것이라 생각했고, 예상대로 경희대 팀 내 압도적인 차이로 본선에 진출할 것 같습니다. 사실 초반 C번에서 1WA를 적립한 채 시작하기도 했고, G번에서 많은 고생을 해서 불안불안해 보였는데, 결국 모두 이겨내고 I번까지 풀어내서 결과적으로는 좋은 성적을 내게 되었습니다.

작년에는 그래도(?) 경쟁이 좀 됐었던 것 같은데, 이번에는 남들 2솔일 때 홀로 5솔하는, 압도적인 모습을 보여주었습니다. 30분 프리즈 전 4솔이 50위권 안쪽이었던 걸로 기억하는데, 이렇게 되면 대학 1위가 아닌 그냥 솔브 수 차이로 무난하게 올라갈 수 있을 것 같습니다. 

 

대신 나머지 팀들이 올라갈 수 있을지는.. 아주 애매한 상황입니다. 30분 프리즈 전 전체적으로 2솔, 1솔에 머물러 있었기 때문에.. 만약 프리즈 동안에 한 문제라도 풀어서 3솔을 만들었다면 어찌저찌 본선에 갈 수 있을 것 같은데, 그렇지 않고 전부 2솔 이하라면 최악의 경우엔 아무도 본선에 못 갈 수도 있을 것 같습니다. 이건 나중에 생각해보도록 하고..

 

작년 예선셋이 이상한 난이도 분포를 보였다는 것을 의식한 건지, 올해 예선셋은 조금 더 어려운 난이도 분포를 보였습니다. 문제 자체 난이도도 난이돈데, 문제 제한과 시간 제한이 꽤나 빡빡하게 느껴졌습니다. 특히 이번 대회의 뜨거운 감자인 G는 정해를 무엇으로 유도하고 싶었는지를 궁금하게 만들만큼 요상한 제한을 보여주었습니다. 대부분의 팀이 TLE로 많은 고생을 한 것 같습니다. 기발한 풀이를 떠올렸거나, 기가 막힌 커팅에 성공했다면 다행이지만, 그게 아니었다면.. 아무래도 G번에서 본선 진출 당락이 갈릴 것으로 예상됩니다.

 

 

 

 

 

 

검증되지 않은 풀이 몇 개를 간단히 남겨봅니다.

 

C번. Happy Point (행복 점수)

문제에서 하라는 대로 구현하면 될 것 같은 문제. 행복 점수와 우울 점수가 모두 0인 경우엔 50.00을 출력해야 함에 유의해야 한다. 

 

여담으로, 이번 인터넷 예선에서도 문제 기술이 제대로 되어있지 않았다는 게 좀.. (한국어 지문 L9 : "행복 지수 P_G는" -> "행복 지수 H는")

 

 

 

 

D번. Palindrome Numbers (회문수)

N의 범위가 10^10까지이므로, O(N) 브루트포스 풀이말고 다른 풀이를 생각해보아야 한다. 회문수는 왼쪽 반과 오른쪽 반이 서로 대칭적인 형태를 이루고 있으므로, (N의 자릿수/2)까지의 수만 보고 나머지를 뒤집어서 붙인 다음 그 수가 N 안에 들어오는지만 체크해주면 될 듯 싶다. 나머지를 뒤집어서 붙이는 건 다양한 구현 방법이 있겠지만, 나였다면 귀찮아서 to_string과 reverse를 계속 사용했을 것 같다. 

 

 

 

 

K번. Symmetry of Stars

O(N^2)으로 모든 쌍의 별을 조사해주고, 그 쌍의 대칭점을 해시에다 넣으면 간단하게 풀릴 것 같다. 이걸 한국어 문제로 줬어야 하지 않나 싶은 문제.. 스코어보드 아니었으면 문제 비주얼 보고 그냥 버렸을 것 같다.

 

 

 

 

G번. Reafy Sequence (Reafy 수열)

처음에는 가능한 기약분수를 모두 만들고 정렬하는 브루트포스 풀이를 떠올렸는데, 테스트를 해보니 O(N^2lg(N^2))이라 시간 안에 들어오지를 않았다. 문제에 있는 수열들을 한참 들여다보다 다음과 같은 풀이를 떠올렸다.

 

7/12라는 기약분수는 5/12라는 기약분수가 수열에 사용되기까지 절대로 사용될 수 없다. 따라서 초기에 0/1 기약분수와 1/2, 1/3, ... 1/N 기약분수 집합에서 출발한다. 어떤 기약분수 p/q가 사용되면, q를 분모로 하고, 분자가 p이상인 기약분수를 하나 찾고, 이를 기약분수 집합에 넣는다. 그리고 이를 반복한다. set이나 priority_queue를 이용하면 되는데, 나는 priority_queue를 사용했다. 근데 이것도 O(N^2lg(N))이라, 사실 TLE이 난다. 

 

여기서부터는 기가 막힌 커팅에 들어가거나 아예 새로운 방법을 생각해보아야 한다. 스코어보드를 지켜봤을 때, 어떠한 사전지식(이 수열 자체에 '페리 수열'이라는 이름이 붙어 있다고 한다.) 없이는 대부분의 팀이 눈물의 커팅을 시도했던 것으로 보였다. 어떤 팀이 절반 정렬로 뚫었다고 하니, O((N^2)/2 lg((N^2)/2))이 가장 현실적이고 실전적인 풀이가 아니었나.. 싶다.