벌써 ICPC 예선 전 주이자 예선 전 마지막 팀연습날이네요! UCPC 예선/본선도 엊그제같은데 벌써 ICPC라니.. 시간 참 빠르구나 싶습니다.
여러 차례에 걸친 팀연습과 프린터 덕에 1PC 적응은 충분히 됐다 싶어서, 이번 팀연습은 플래티넘 이하가 많은 셋보다는, 한국 리저널과 난이도가 비슷하거나, 좀 더 높은 셋을 뛰어보기로 했습니다. boj를 뒤져보던 중, 2018 일본 요코하마 리저널이 적당히 어려워 보여서 이번 팀연습 셋으로 결정되었습니다.
오늘 원래 12시에 모여서 1시부터 6시까지 정확히 5시간동안 뛰려고 했으나, 날짜를 착각한 jame0313님이 살짝 늦어버렸습니다. 그래서 12시부터 하려고 했던 카메라/좌석 세팅등은 저와 kyaryunha가 진행했고, jame0313님은 나중에 와서 노트북 관련 세팅만 했습니다. 세팅 끝내니 12시 58분쯤이라 여유롭게 1시 10분에 시작하기로 했고, 스터디룸 예약이 6시까지도 그전에 세팅한 걸 정리해야 하니 5시 4~50분정도에 자체종료하기로 했습니다.
시작하기 직전, 이번에도 ‘A번을 누가 볼 것인가’에 대해 열심히 논의했습니다. A번이 항상 쉬운 문제인건 아니지만, 쉬운 경우가 많은 만큼, ‘A번은 코딩 빠른 사람에게 넘겨주자!’는 이유로 jame0313님에게 넘겨주곤 했었는데, 어쩌다보니 이번엔 폭탄(?)이 제게 넘어왔습니다. B, C번은 각각 kyaryunha와 jame0313님이 잡은 것으로 보입니다.
A번은 단순 문자열 파싱 및 비교 문제였습니다. 구현이 귀찮지 별다른 아이디어가 있는 문제는 아니라서, 바로 코딩을 들어갔습니다. 그런데 코딩을 끝내고 보니 예제조차도 안나와서 코드를 인쇄하고 B번 풀이를 떠올린 kyaryunha에게 풀이를 넘겨줬습니다.
그런데 코드를 인쇄하고 보니 제 멍청한 실수가 바로 보여서 손코딩 조금 하다가 컴퓨터를 도로 뺏었습니다. 예제가 잘 나오는 것을 확인하고, 제출해서 바로 AC를 받았습니다.
A solved (by artichoke42, 19min, 제출 1회)
한편, kyaryunha가 풀던 B번은 그리 순조롭게 흘러가지 않았습니다. dp+std::map을 쓰는 풀이였는데, 공간복잡도가 \( O(N^2) \)인데 long long을 쓰는 바람에 MLE 한 번, int로 바꾸고도 MLE, 그리고 메모리 문제를 해결하니 TLE가 뜨자 팀원들이 단체로 뇌절하기 시작했습니다. 결국 저도 B번을 읽어봤지만 어디서 본 것 같은 문제면서도 정작 풀이는 떠오르지 않아서, 쌓여만 가는 다른 팀의 B 솔브 소식을 뒤로 한 채 C번과 D번으로 넘어갔습니다.
그런데 C와 D도 만만치 않아 보였습니다. C는 그리디일 것 같다는 느낌은 있었지만 구체화될 기미는 안보였고, D는 dp일 것 처럼 생겼는데 식이 감이 안잡혔습니다. 둘 중 뭘 먼저 잡을지 고민하다가 또 dp문제면 저라도 풀어야 할 것 같아 D번을 잡았습니다.
이후 약 30분간 kyaryunha와 jame0313님은 B번, 저는 D번으로 뇌절하고 있었습니다. B 구현을 jame0313님 스타일대로 다시 짰지만 WA 두 번과 MLE 한 번을 더 쌓아버렸고, 저는 D번 dp풀이를 떠올리지 못하고 있었습니다. 그러던 중, 관점을 bfs로 바꿔보니 풀이가 보여서 컴퓨터를 뺏고 구현에 들어갔습니다. 구현 실수를 좀 많이해서 시간이 끌리긴 했지만 어찌저찌 예제는 잘 나오는 코드를 만들었고, 제출해서 79분경에 AC를 받았습니다.
D solved (by artichoke42, 79min, 제출 1회)
이쯤에서 스코어보드를 보니, B와 C번을 (전체 280팀 중) 각각 180팀, 100팀정도 푼 상태였습니다. 사실상 비슷한 실력대 팀들은 다 풀었다는 의미기 때문에 이제는 진짜 B와 C를 풀어야만 했습니다. 다행히도 C는 jame0313님과 제가 논의하는 과정에서 \( O(R^2C) \) 풀이가 나왔고, 구현은 jame0313님이 좀 더 생각해 보겠다고 했습니다. B는 다시 보니 dp에 투 포인터를 섞어서 \( O(N^2) \)에 푸는 풀이가 보였고, 구현도 간단해 보여서 바로 구현에 들어갔습니다.
jame0313님의 C 구현을 먼저 하다가 예제가 안 나오자 컴퓨터를 넘겨받아서 B를 구현했고, B 구현은 순조롭게 돼서 108분경에 AC를 받았습니다. 세 문제 풀 때까지 한 번도 안 틀리다니.. 컨디션이 좋은게 느껴졌습니다. C도 jame0313님이 곧 코드를 고치고 111분에 AC를 받은 것으로 보입니다. 이로써 일단 ‘진작 풀었어야 했던 문제’들은 다 풀었네요.
B solved (by artichoke42, 108min, 제출 7회)
C solved (by jame0313, 111min, 제출 1회)
남은 문제들 중 가장 많이 풀린 문제는 G, 그다음은 K였는데, 일단 그중 솔브수가 더 많은 G를 먼저 잡기로 했습니다. G는 인접한 원소끼리 최소 횟수로 swap해서 \( a_1 \le a_2 \le \ldots \le a_k \ge a_{k+1} \ge \ldots \ge a_{n-1} \ge a_n, 1 \le k \le n \)을 만족하도록 하는 문제였습니다. 다들 풀이 자체는 금방 생각했는데, 문제는 구현.
처음에 제가 코드를 lower_bound로 떡칠하면 어떻게든 되지 않을까?하고 제안했지만 다들 탐탁지 않아 했습니다. 그렇다고 제가 직접 구현할 자신도 없었기 때문에 이 구현방식은 폐기. 그러던 중 jame0313님과 kyaryunha가 거의 동시에 펜윅 트리를 쓰는 풀이를 생각해 냈고, kyaryunha가 구현에 들어갔지만 틀렸습니다. 코드를 본 jame0313님이 답이 long long 범위를 넘어가는데 int를 쓰고 있다는 사실을 발견했고, 고쳐서 AC를 받았습니다.
G solved (by kyaryunha & jame0313, 154min, 제출 2회)
쉬운 문제는 다 풀었다는 느낌이 들었기 때문에, 남은 시간동안 한 문제라도 더 푸는 걸 목표로 kyaryunha는 E, 저와 jame0313님은 K를 잡기로 했습니다. K는 ‘최대 승수’를 구하는 것은 그리디로 쉽게 구할 수 있지만, 최대 승수를 달성할 수 있는 조합이 여러 개면 사전순으로 가장 나중인 조합을 출력해야 한다는 점이 골때렸습니다.
우선 jame0313님이 첫 카드로 무엇을 낼지 이분 탐색으로 결정할 수 있고, 이걸 n개의 카드에 대해서 반복하는 방법을 제안했습니다. 이분 탐색을 쓰면 시간복잡도가 \( O(N^2 \log^2 N)\)까지 줄어드는 것을 확인했는데, \( N \)이 5000씩이나 하기 때문에, 이것만으로는 부족했습니다. 그래서 저는 P배열과 F배열의 남은 카드들을 정렬된 상태로 들고 있으면 로그 하나가 떼지지 않냐고 제안했고, jame0313님도 이 풀이가 맞는 것 같다고 해서 결과적으로 \( O(N^2 \log N)\) 풀이가 완성되었습니다.
구현 과정도 만만치 않았는데, jame0313님이 약 1시간 반정도에 걸쳐 구현해서 결국 AC를 받았습니다. 역시 믿고 맡기는 jame0313님..
K solved (by jame0313, 271min, 제출 1회)
이로써 최종적으로 6솔브를 달성했고, 전체 팀중 84등, official 팀만 따졌을때는 15등에 안착하면서 팀연습을 마무리하게 되었습니다. B번같은 dp문제에서 또 한번 약점을 보이는 등, 아쉬운 점도 조금 있었긴 하지만, 마지막 팀연습을 만족스러운 결과로 마무리해서 좋네요! 다음 주에 있을 ICPC 예선도 오늘처럼만 했으면 좋겠습니다.