UCPC 이후 4차례 팀연습을 거치고, 드디어 ICPC 예선날이 밝았습니다. 팀명은 이전 팀연습 스코어보드를 보면 알 수 있듯 SushidoQueue 였고, 인원 구성은 UCPC와 동일하게 artichoke42, jame0313, kyaryunha입니다. 드디어 팀명이 정치와 무관하다는 해명을 할 필요가 없게 되었습니다.
대회날 아침부터 유난히 꼬였는데, 만나기 전부터 사건이 좀 많았습니다. 대회가 2시부터라 넉넉잡아 12시에 모이기로 했고, jame0313님과 제가 약속시간보다 30분~1시간쯤 일찍와서 점심을 같이먹으려다 커뮤니케이션이 꼬여서 따로 먹게 되거나, kyaryunha가 자느라 늦는 등.. 그나마 시간을 넉넉히 잡은 덕에 여유롭게 대회준비를 끝내고, 대회 시작하면 어떻게 할지, 목표를 어느 정도로 잡을지 등에 대한 토론을 할 수 있었습니다.
인터넷 예선 문제는 여타 리저널 문제와 다르게 한글 문제가 몇 개 있기 때문에, 그것부터 찾아서 kyaryunha가 적당히 배분하기로 했고, 목표는 단연 학교(한양대) 1등으로 잡기로 하긴 했는데.. 사실 한양대에는 오렌지가 2명이나 있는 std::accept(solarmagic, dtc03012, Lemonade255)팀이 있기 때문에 쉽지 않은 목표이긴 했습니다. 그래도 목표는 높게 잡아야죠 ㅎㅎ
약속한대로 대회 시작하자마자 한글 문제부터 찾았습니다. 우선 B와 C가 한글 문제인 것을 확인했고, 이후 K까지 출력했는데 한글문제가 없어서 1차 당황. 문제 목록을 보니 한글문제인 I번 출력을 누락시켰더군요.. 게다가 한글 문제가 5개나 있었던 작년과 달리 3개밖에 없다는 소식에 저를 비롯한 팀원들이 약간 동요했던 것 같습니다. 그리고 먼저 확인한 B번과 C번문제 둘 다 마냥 쉬운 문제는 아니었기에 더더욱 그랬네요. 아무래도 작년 예선때 참가자들의 실력 인플레를 감지하고 난이도를 올린게 아닌가 싶습니다.
아무튼 이러한 사유로 I를 조금 늦게 봤는데, 무지성 priority queue문제인 걸 발견하고 바로 코딩에 들어갔습니다. 구현도 간단해서 금방 짜서 AC를 받았습니다. 다만 안그래도 코딩 느린데 문제를 늦게 읽기까지 해서 다른 팀보다 늦게 푼 감이 있긴 하네요.
I solved (by artichoke42, 8min, 제출 1회)
1솔 이후 다른 한글문제인 B, C번을 번갈아 보다가, J 퍼솔이 나왔다는 소식을 듣고 다같이 J번을 봤습니다. J번 문제는 몇달 전에 잠시 유행했던 사과 게임을 연상시키는 문제였는데, jame0313님이 보자마자 대충 누적합 쓰면 \( O(N^3) \)에 될거같은데? 하며 자기가 잡겠다고 선언했습니다. 저는 이때쯤 적당히 dp쓰면 C번을 풀 수 있지 않을까? 하는 생각에 C번을 잡기 시작했고, kyaryunha는 H 퍼솔 소식을 듣고 H번을 읽기 시작했습니다.
이후 몇십 분간 솔브 소식이 하나도 들려오지 않았습니다. 특히 솔브 소식이 가장 많이 들려오고 있었던 J번을 짠 jame0313님의 코드는 예제조차도 안 나오고 있었던 듯 했습니다. 어지간히 안나오다보니 급기야 J를 잠시 내려놓고 E를 읽기도 하시더군요.. kyaryunha가 보던 H도 펜윅 트리를 쓰는 풀이까지는 나왔지만 마찬가지로 예제조차 안나오고 있었습니다. 약간 지난 일본 리저널 팀연습 초반부가 생각나는 상황. 그나마 그때는 제가 D를 풀기라도 했지만, 이번에는 C 풀이를 찾았고, 짠 코드가 예제는 잘 나오길래 제출했지만 WA가 나왔습니다. 이런 상태가 한시간이 넘도록 지속되자 ‘이러다 리저널도 못가는거 아닌가..?’하는 걱정이 앞섰습니다.
다행히도, jame0313님과 kyaryunha가 거의 동시에 자기 코드의 문제점을 발견했고, 각각 75분, 77분에 AC를 받았습니다. 한편 저는 C번에서 ‘B’또는 ‘R’ 태그가 붙은 1층짜리 원반을 ‘G’ 태그로 바꿔야 한다는 반례를 찾았지만, 또 한번 WA를 받았습니다. (WA를 이쯤에서 한번 더 받았던 걸로 기억하는데, 무엇 때문인지는 기억이 나지 않습니다.)
J solved (by jame0313, 75min, 제출 1회)
H solved (by kyaryunha, 77min, 제출 1회)
제가 C번을 너무 오래 잡고있었던 것 같아, kyaryunha와 함께 스코어보드에서 (그나마) 많이 풀리고 있었던 K번과 퍼솔이 나온 L번을 보고 있었습니다. 그러던 중 kyaryunha가 K번에 대한 사풀을 찾았고, 그 풀이를 들은 jame0313님도 그럴듯해 보인다고 해서 제출했지만 WA. jame0313님도 비슷한 시기에 E번을 제출했지만 WA를 받았습니다. 그런데 오류를 금방 찾으셨는지 105분경에 AC를 받아오셨습니다. E번은 아예 읽지도 않은 문제라 상황이 어땠는지는 잘 모르겠네요.
E solved (by jame0313, 105min, 제출 2회)
jame0313님이 E를 푼 직후, K번이 LIS와 비슷한 느낌으로 y역순, x역순으로 정렬한 후, 세그먼트 트리를 돌리면 될 것 같아서 바로 짜서 115분경에 AC를 띄웠습니다. 이쯤에서 현재 교내 순위 2등에 3등과 격차가 커진 것을 보고 안도했습니다. 목표였던 교내 1등 달성은 생각할 겨를도 없었네요 ㅋㅋ…
K solved (by artichoke42, 115min, 제출 2회)
5솔 이후 jame0313님은 B번을, 저와 kyaryunha는 A번, C번, L번을 번갈아 보기 시작했습니다. 얼마 후 jame0313님이 B번에 포함-배제 원리를 쓰는 풀이를 발견한 거 같다고 주장하며 제게 풀이를 설명하셨는데, 이때 반례를 찾아드려야 했습니다. 저와 jame0313님과의 커뮤니케이션이 또 꼬여서 jame0313님의 풀이의 오류를 찾지 못했습니다.
jame0313님의 틀린 풀이를 제가 알아서 맞는 풀이로 바꿔 이해하는 바람에 jame0313님의 풀이에 별다른 태클을 걸지 않았고, 그 결과 jame0313님은 B번 코딩을 풀이가 틀린 채로 진행하게 되었습니다.
B 풀이 확인 이후 읽은 A번은 이 문제과 거의 판박이인 문제였습니다. 포스팅까지 한 문제기 때문에, 풀이를 확실히 기억하고 있었지만, 저 문제와 다르게 A번은 \( O(QC) \)풀이가 먹히지 않는다는 게 문제였습니다. \( O(Q \sqrt C) \)에 푸는 풀이는 그 당시에도 끝까지 못 찾았었기 때문에 이 문제는 Mo’s를 쓰는 문제라는 걸 알면서도 버릴 수밖에 없었습니다.
L번도 나만 모르는 웰노운 느낌이 나서 던지고, 다시 C에 집중하기로 했습니다. 이때 kyaryunha도 같이 C를 잡았는데, 최상단에 있는 ‘B’ 태그가 붙은 원반을 2번 옮길때는 \( 2n-1 \)번만 옮겨도 된다는 반례를 찾아줬습니다. 그런데 이 경우가 \( m=1 \)일 때만 발생한다고 잘못 이해하고 고쳐서 또 WA. B도 당연하게도 예제조차 나오지 않아서 사실상 자체종료하는 분위기였습니다. 다만 스코어보드상으로 뭔가 있어보이게 하기 위해 B랑 C에 각각 한번씩 제출하긴 했네요.
대회 결과 프리징 기준 22등, 교내 2등을 달성하게 되었습니다. 저희팀은 프리징 이후 푼 게 없기 때문에 프리징이 풀리면 30등정도까지 내려갈 것 같고, 교내에서는 프리징된 문제들을 다 맞았다고 쳐도 5솔 이상으로 올라갈 팀이 없기 때문에, 사실상 2등 확정으로 보입니다.
예년 결과를 봤을 때, 한양대에 7솔브 팀이 있고, 교내 2등팀이기 대문에 리저널 진출은 거의 확보된 것 같긴 합니다. 하지만 대회 과정을 보나, 결과를 보나 썩 만족스럽진 않네요.. 팀원들은 1인분을 했지만 제가 못했기 때문에 더 그런 것 같습니다. 팀원들은 J와 H에서 말리긴 했지만 결국 풀어낸 반면 제가 2시간 가까이 잡은 C는 팀원이 반례를 찾아줬음에도 결국 못풀었으니…
우선 B와 C를 못 푼건 순전히 제 탓입니다. B는 jame0313님의 틀린 풀이를 뻔히 들었고, 풀이를 제대로 이해했다면 틀린 풀이임을 바로 알 수 있었음에도 지적할 생각조차 하지 못했습니다. C도 kyaryunha가 반례를 던져줬음에도 반례를 잘못 이해해서 또 틀리고 말았습니다. 의사소통을 대충 해서 발생한 문제인 것 같고, 팀원의 풀이를 들었을 때, 그 풀이를 제대로 이해한 게 맞는지 확인하는 과정도 거쳐야 한다는 점을 배우게 되었습니다. 그리고 K번은 사실 보자마자 풀었어야 했던 문제같은데 30분씩이나 걸린 것, A번도 봤던 문젠데 업솔빙을 똑바로 안했던 것 등등도 아쉬웠습니다.
그리고 교내 1등의 벽이 생각한 것보다도 높다는 것을 깨닫게 되었습니다. std::accept 팀의 7솔브에 I, L퍼솔은 경이로울 따름.. L번은 해당 팀이 팀연습중에 푼 문제라 빠르게 풀었다지만 그걸 감안해도 솔브수, 페널티 둘다 압도적으로 밀리기 때문에 목표를 달성하려면 연습을 더 빡세게 해야한다는 결론을 얻을 수 있었습니다. 예선 직전에 여러 일이 겹쳐서 한 주간 PS를 거의 손을 못댔는데 이제 다시 열심히 하겠습니다!
추신) B랑 C 둘다 놓친 부분 고치니 귀신같이 AC뜨네요. 억울해라..
추신2) 반면 E번은 대회때 맞은 코드를 boj에 제출하니 WA가 뜨네요. 대회때 E 푼 다른 팀은 boj에서 TLE가 났다는 제보가 있는 거 보면 대회 데이터가 약했던 것 같습니다.
추신3) 예선 최종 스코어보드가 공개되었습니다!
저희팀은 프리징 이후로 아무것도 못 했어서 최종 스코어보드상 순위가 많이 밀려 30위권정도에 안착할 것으로 예상했는데, 이정도면 많이 선방한 것 같습니다. 학교 2등이라 리저널 갈수 있을지는 모르겠네요. 5솔이라 될거같긴 한데…