지난번에 이어 이번에도 1PC 연습 겸 풀 수 있는(=플래티넘 이하인) 문제가 많은 셋을 고르기로 했습니다. 그중에서도 문제가 무려 13개이고, 난이도 분포가 적당해’보이는’ 라틴 아메리카 리저널이 눈에 띄었고, 그래서 이 셋이 오늘 팀연습 셋으로 결정되었습니다.
지난 팀연습 도중 다이아 문제(였던 것)을 푼 이후로 자신감이 붙어서 플래티넘 이하 문제를 모두 푸는 것(=9솔)으로 목표로 하기로 했는데, 약간 스포를 하자면, 나중에 스코어보드를 까보니 월파권 팀들이나 겨우겨우 9솔할정도의 난이도더군요.. 난이도 예측을 잘못해도 너무 잘못한 셋이었습니다. 덕분에 대회 난이도를 솔브드 티어만으로 판단하면 안된다는 좋은 교훈을 얻긴 했네요 ㅠ..
뭐 아무튼.. 일단은 ‘9~10솔브’라는 어림도 없는 목표를 가지고 팀연습을 시작했습니다.
시작 직전에 A, B, C를 누가 잡냐에 대헤 열심히 논의했었는데, 문제지를 출력하고 보니 아무 의미가 없었습니다. A, B, C가 하나같이 어려웠거든요. 그래서 일단 퍼솔이 나올때까지 지문이 짧은 문제를 읽으면서 대기했습니다.
얼마 안지나 E와 M의 퍼솔이 나온 것을 확인하고, jame0313님은 M, 저는 E를 잡았습니다. M번은 문제를 읽지도 않았기 때문에 무슨 문제인지 모르지만, jame0313님이 브론즈급 문제라고 판단해서 바로 코딩에 들어갔고, 곧 AC를 받았습니다.
M solved (by jame0313, 9min, 제출 1회)
M번 AC를 받을때쯤, E번 풀이도 나왔습니다. 각 인덱스에 대해 순회하면서, b - (현재 인덱스 - 가장 최근에 나온 ‘E’의 인덱스)를 더해주면 되는 간단한 문제였습니다. 구현도 간단해보여서 바로 코딩에 들어갔는데, 판이 Circular하다는 것을 고려하지 않아서, WA를 받았습니다. 여기까진 괜찮았는데 고치는걸 또 잘못 고쳐서 2번 더 틀렸습니다. 뇌절이 길어질 기미가 보여서, 그새 I 풀이를 찾은 jame0313님에게 다시 컴퓨터를 넘겨줬습니다.
그동안 저는 코드 출력하고 읽고 있었는데, 틀린 부분이 바로 보여서 I번을 코딩하던 jame0313님의 컴퓨터를 뺏었습니다. 틀린 부분을 고쳐서 제출했고 그대로 AC. I번도 구현은 간단했는지 얼마 안지나서 바로 AC를 받았습니다.
E solved (by artichoke42, 21min, 제출 4회)
I solved (by jame0313, 28min, 제출 1회)
3솔한 시점에서, 스코어보드를 다시 봤을 때 사람들이 많이 푼 문제는 G, K, L이었습니다. jame0313님과, 내내 이분 매칭으로 추정되는 A번을 잡고있던 kyaryunha는 문자열 문제인 G번을, 저는 L번을 잡기로 했습니다. L번은 Parametric Search를 써야 할 것 같다는 느낌이 들긴 했는데, naive하게 짜면 \( O(N^2 M^2 \log(NM)) \), Prefix Sum을 써도 \( O(N^2 M \log(NM)) \)으로 TLE가 날 것처럼 보였습니다. 아이디어를 얻기 위해 팀원들에게도 이 내용을 설명해봤지만 딱히 소득이 없자, G번으로 합류했습니다.
한편 G번쪽은 아호-코라식을 쓰면 풀릴 것 같다는 얘기가 나와서, jame0313님이 짜기 시작했으나, 얼마 안 지나 시간복잡도가 \( O(N^2) \)이라 터진다는 결론이 나왔습니다. KMP, Z, 해싱 등 웬만한 문자열 알고리즘이나, 단순 그리디 같은것도 어림없어 보였습니다. 아무리 봐도 남은건 Suffix Array뿐. 그런데 문제는 팀노트가 예전 버전이라 Suffix Array가 없다는 점입니다.. 그래서 저는 G는 사실상 포기하고 K를 읽으러 갔습니다.
K는 좌표 \( 2, 4, \ldots , 2N\)와 다항식 \( f(x) \)에 대해, ‘A’가 적혀있는 좌표의 함수값은 음수, ‘H’가 적혀있는 좌표의 함수값은 양수가 되도록 하는 다항식 \( f(x) \)를 찾는 문제였습니다. 좌표가 정직하게 짝수만 주어져있어서, 좌표 i에 ‘A’(‘H’), i+2에 ‘H’(‘A’)가 적혀있으면 다항식에 (x-(i+1))을 추가하면 되는 문제였는데, 구현을 어떻게 하냐가 문제였습니다. naive하게 하면 \( O(N^3) \)이라 터지고, \( N \)이 \( 10^4 \)이내다보니 \( O(N^2) \)도 살짝 불안해서 FFT로 \( O(N \log N) \)에 풀자는 얘기가 나왔고, 그래서 jame0313님이 팀노트 바탕으로 코딩에 착수했습니다.
jame0313님이 K를 구현하는 동안, 저는 다시 L을 봤습니다. 이분탐색을 쓰는 건 맞다는 확신이 있었기에, 최적화를 어떻게 할까 고민하던 중, Prefix Sum을 쓰는 기존 풀이에 최적화를 약간 더 하면 \( O(NM \log(NM)) \)으로 줄일 수 있다는 것을 발견하고, jame0313님이 K 코딩이 끝나기를 기다렸습니다. 얼마 안지나 K 코딩이 끝나서 제출해봤지만 WA. 계수의 크기가 \( 2^{63} \)이내라는 조건으로 인해 부동소수점 오차를 피할 수 없었던 것으로 보입니다.
결국 FFT를 버려야 한다는 판단이 나왔고, 그래서 컴퓨터를 뺏고 L을 짜기 시작했습니다. 이분탐색 풀이가 나왔을 때 짜놓았던 게 있어서 금방 구현했고, 92분에 AC를 받았습니다. K도 그냥 분할 정복으로 \( O(N^2) \)으로 짜자는 얘기가 나와서 jame0313님이 다시 구현에 들어갔고, 111분에 AC를 받았습니다. 진작 \( O(N^2) \)으로 짤걸 그랬네요 ㅋㅋ…
L solved (by artichoke42, 92min, 제출 1회)
K solved (by artichoke42 & jame0313, 111min, 제출 2회)
남은 문제 중 많이 풀린 문제는 D, F, G정도였습니다. 그중에서도 가장 많이 풀린 G는 Suffix Array를 짤 줄 아는 사람이 없어서 반쯤 포기한 문제였고, F는 제발 안나왔으면 싶었던 DP문제였고, D는 Bulldozer같은 느낌의 기하학+스위핑문제처럼 보였습니다.
D번이 Bulldozer와 같은 방법으로 풀릴 것 같은 느낌이 들면서도, 이게 정해면 이렇게 많이들 풀었을 리가 없을 것 같다는 의심이 들었지만, 그렇다고 다른 문제 풀이가 나온것도 아니라서 D 구현에 들어갔습니다. 그동안 jame0313님은 F, kyaryunha는 A번을 보고 있었습니다.
약 1시간 뒤 D번 구현이 끝났지만, 예제조차도 나오지 않았습니다. Brightness Level이 서로 다른 별을 동시에 보는 경우에도 인정을 해야 하는데, 이 부분에 대한 처리가 안 되는 듯 보였습니다. 현재 풀이에서 해당 문제에 대한 처리를 할 방법이 딱히 보이지 않아 D도 사실상 포기했습니다.
한편 F를 포기하고 H를 본 jame0313님은 이 문제가 지난번 팀연습때 G번이었던 Great Expectations와 비슷하다고 보고 코딩에 들어갔지만 이쪽도 역시나 WA. 결국 더 이상 풀 수 있는 문제가 없다 생각해서 팀연습을 자체마감했습니다.
결과적으로, 5솔브로 801팀중 293등이라는, 썩 좋지 못한 성적을 기록했습니다. 플래티넘 문제 올솔은 커녕 한 문제도 못풀었네요..
한편, 이번 셋을 통해 저희 팀의 약점을 어느 정도 파악하게 된 것 같습니다. 다른 문자열 알고리즘은 어느 정도 알고 있으면서도 Suffix Array만큼은 익숙지 않았는데, 다른 팀원들도 마찬가지였던 모양입니다. 그리고 G번에 대해 논의하던 중, 팀원 중 해싱을 사용하는 문제에 익숙한 사람도 딱히 없다는 것도 알게 되었습니다. 별개로 약간 의문인 건, Suffix Array(심지어 기본문제도 아닌) 문제가 K번보다 솔브수가 많고, L번이랑 솔브수가 비슷할 정도 급인지는 지금도 의문이긴 하네요.
한국 ICPC에서 Suffix Array와 해싱 문제는 거의 안나오니(여태까지는 2018년 예선에서밖에 나온 적이 없습니다) 그렇다 쳐도, ICPC에서 꾸준히 출제되고 있는 기하학 문제와 dp문제를 풀 수 있는 팀원이 없다는 건 치명적인 문제입니다. 특히 다이아급 dp문제는 (월파권 팀 제외) 아무도 못푸니 그렇다 쳐도 플래티넘급 dp문제가 나와버리면 저희 팀만 못푸는 사태가 일어나기 때문에.. 저라도 dp문제를 꾸준히 풀어야 할 것 같습니다.
추가로, solved.ac 티어만으로 셋의 난이도를 판단하면 안된다는 좋은 교훈을 얻게 되었습니다. 플래티넘 문제들이 전부 플래티넘 1~2정도의 고난이도 문제였다는 점은 차치하고서라도, 나중에 스코어보드를 까보니 플래티넘으로 책정된 B번을 푼 팀이 한 팀도 없었습니다. 앞으로 셋 고를때 티어 말고도 스코어보드를 대충이라도 봐야겠습니다.