ICPC 예선 끝나자마자 시험기간이 시작되는 바람에 한동안 팀연습을 쉬다가, 3주 뒤인 어제부터 재개하기로 했습니다. 사실 저와 jame0313님은 시험이 아직 안끝나긴 했지만.. 리저널 전 주에 팀연습 한 번만 진행하는 것으로는 좀 불안해서 그 전주에도 팀연습을 하자고 했고, 다행히도 팀원들이 수락해 주었습니다. 팀연습 셋은 지난 팀연습때 진행했던 요코하마 리저널 문제 퀄리티가 괜찮았던 것 같아서, 이번에도 요코하마 리저널을 뛰기로 했습니다.
시작하기 직전에 또 저희팀의 유구한 전통인 A번 폭탄돌리기(?)에 의해 jame0313님이 A, kyaryunha가 B, 제가 C를 먼저 보기로 했는데.. 어라? 설정이 잘못됐는지 문제가 K번부터 역순으로 프린트되기 시작했습니다. 그래서 저는 K, H, E, B번을 보게 됐는데, K번과 H번은 쉬운문제는 아닌거 같아서 읽기만 하고 치워뒀고, E번은 기하같아서 나중에 읽기로 했습니다.
B번은 길이가 n인 배열 A, 길이가 m인 배열 B의 일부가 주어졌을 때, 두 배열을 1부터 n+m 사이의 수를 단 한번씩만 사용하여, 오름차순 배열로 만드는 문제였습니다. 조금 생각해보니 처음으로 등장하는 숫자가 더 작은 쪽부터 채우는 방식의 그리디로 풀릴 것 같아 보여서 제가 짜겠다고 했습니다.
약 10분정도 들여서 구현했는데, 예제 1번조차도 제대로 나오지 않았습니다. 원인은 배열 끝부분이 0일 때에 대한 예외처리를 안해줬기 때문. 원인 자체는 금방 찾았지만, 계속 고쳐봐도 예제 1번 결과가 달라지지 않아서 슬슬 멘탈이 나가기 시작했습니다. 노트북을 계속 잡고 있다가 jame0313님이 A번 풀이를 떠올린 것 같아서 노트북을 넘겨주고, kyaryunha에게 B번을 설명하고 헬프 요청을 했습니다. jame0313님은 A번을 금방 구현해서 AC를 받았던 것으로 기억합니다.
A solved (by jame0313, 32min, 제출 1회)
kyaryunha도 별다른 B번 풀이가 떠오르지 않는 것 같아 jame0313님에게도 헬프를 쳤습니다. 반대로 jame0313님은 제가 B를 짜던 동안 읽고 있었던 J번 헬프를 요청했습니다. B 설명을 들은 jame0313님은 본인이 짜겠다고 했습니다. J번은 트리 버전의 소코반 문제인데, 단순 dfs로 풀릴 것 같은 문제라, jame0313님이 B번을 짤 동안 풀이 구체화에 들어갔습니다.
jame0313님이 구현한 B번은 예제가 잘 나와서 제출해봤지만, WA가 떠서 제게 노트북을 넘겨줬고, 저는 구체화한 J번 풀이 구현을 시작했습니다..만 도중에 jame0313님이 다시 제 노트북을 뺏어서 B번을 고쳐서 제출했고, 이번엔 AC를 받았습니다. J번은 도중에 문제 해석 관련 이슈가 있긴 했지만 그래도 금방 구현했고, 이 문제도 얼마 안지나 AC를 받았습니다.
B solved (by jame0313, 63min, 제출 2회)
J solved (by artichoke42, 72min, 제출 1회)
쉬운 문제는 다 풀었다고 생각해서, 이쯤에서 스코어보드를 한 번 확인했습니다. 4솔 이상 팀이 가장 많이 푼 문제는 제가 B와 J번을 잡을동안 kyaryunha가 잡고있었던 G번이었고, 그 다음으로 많이 푼 문제는 C번, E번 그리고 H번이었습니다. C번은 구현+구성적 문제인 것 같아서 일단 접어두고, 저는 E번, jame0313과 kyaryunha는 G번을 잡기로 했습니다.
E번은 다각형의 각 변이 주어져있을 때, 외접원의 지름의 최솟값을 구하는 문제였습니다. 일단 반지름을 고정해두고, acos 함수를 통해 구한 다각형의 내각의 합을 기준으로 이분 탐색을 하는 풀이까지는 떠올렸는데, 예제 4번 답이 안나오는 문제가 있었습니다. 알고보니 예제 4번은 외접원의 중심이 다각형 밖에 있어, acos 함수를 통해 구한 다각형의 내각이 합이 \( (n-2) \pi \)보다 커지는 것이 문제였습니다. 문제는 찾긴 했는데 어떻게 해결해야할 지 모르겠어서 여기서 2차 멘붕이 왔습니다.
이후 한동안 E번을 잠시 내려놓고 C, G, H, I번을 한 번씩 다 읽어봤는데, 결국 E번을 잡긴 해야할 것 같아 돌고돌아 E번으로 다시 돌아오게 되었습니다. 그리고 얼마 뒤 다각형의 외접원의 중심이 내부에 있는지 여부를 asin 함수의 값의 합이 \( \pi \)인지 확인하는 방법으로 판별할 수 있게 되었습니다. 외접원 중심이 밖에 있는 경우는 acos한 값을 모두 더한 뒤, 가장 긴 변에 대한 acos값을 빼주는 방식으로 했는데, 이렇게 되면 단조성이 깨져서인지 여전히 4번 예제가 잘 나오지 않았습니다.
그래서 중심이 외부에 있는 경우는 각도 계산을 외부에 있는지 여부 판별때처럼 asin으로 바꾸고 나서야 예제가 제대로 나오기 시작했습니다. 예제가 제대로 나오는 것을 확인하고 제출했는데, WA를 받았습니다. 부동소수점 문제임을 확신하고, eps를 1e-14로 변경했더니 이번엔 TLE. 그래서 이번엔 이분탐색 종료조건을 부동소수점 기준이 아니라, 고정된 횟수 기준으로 바꾸었더니 WA를 두 번 더 받았습니다. 4번을 툴리고 나서 코드를 다시 봤더니, 원의 중심이 외부에 있는지 여부를 판단할 때 쓰이는 cmath 헤더의 M_PI 매크로가 long double이 아닌 double 타입임을 알게 되었고, 이 부분의 eps값만 1e-9로 바꾸고 나서야 AC를 받을 수 있었습니다.
E solved (by artichoke42, 207min, 제출 5회)
남은 시간동안은 C, G, H, I중 하나라도 잡기 위해, 다른 문제들을 번갈아 보기 시작했습니다. 그중에서도 저는 G번을 중점으로, jame0313님은 H번과 C번을 중점으로 봤습니다. G번은 정점의 가중치를 기준으로 정점을 두 그룹으로 나눈 뒤, 간선 몇 개를 추가하되, 서로 다른 그룹끼리만 연결하고, 정점 하나당 최대 간선 하나까지만 연결하여 모든 정점이 연결되도록 할 수 있는지를 판별하는 문제였습니다.
그런데 제가 이쯤에서 집중력이 떨어졌는지, 예제만 보고 초기에 연결되어 있는 정점 그룹이 일직선 형태라는 이상한 가정을 해버렸습니다. 유니온 파인드에 두 그룹의 컴포넌트 수 합에 1을 뺀 것이 정점 수가 더 적은 그룹의 정점수보다 작거나 같은지 판별을 하면 되는 문제였는데, 문제를 이상하게 해석했으니 제대로 구현할 리가 없었습니다. 예제가 잘 나와서 제출했지만 당연히 WA. 종료 20분쯤 전에 문제점을 알아챘지만, 시간 안에 문제를 짜기 힘들어 보였고, 당시 jame0313님이 짜던 H번을 디버깅하는게 더 AC받을 확률이 커 보여서 G번은 사실상 포기했습니다.
한편 jame0313님은 map과 multiset으로 덕지덕지 발라놓은(?) H번 코드를 완성해서 제출했는데, TLE가 났습니다. 이후 #pragma GCC optimize(“Ofast”)를 추가한다거나, 인자를 reference로 받도록 고치거나, multiset을 vector로 고치는 등 최적화를 위한 별별 시도를 했으나, TLE만 4번 더 받고 팀연습을 마치게 되었습니다.
이로써 저희팀은 4솔브에 페널티 474분, 당시 대회 스코어보드 기준 30등을 기록했습니다. 2018년 요코하마 리저널 기준 15등에 비하면 다소 처참한 퍼포먼스네요. 2018년보다 훨씬 어려웠던 거 같은데 정작 15등권은 7솔인거 보면 저희가 말린건지 일본쪽도 실력 인플레이션이 상당히 이루어진건지 아니면 문제들이 일본식 웰노운인건지 잘 모르겠네요..
그래도 정작 팀연습 상황을 되돌아보면 마지막에 G번 잘못생각해서 못 푼 것과 B번 제 선에서 해결 못하고 헬프요청한 거 제외하면 할 만큼 한 느낌이기는 합니다. 특히 G번 덕에 제 집중력의 유통기한이 약 3시간정도라는걸 깨닫게 되었네요. 이 문제는 다음 팀연습 외에도 따로 5시간짜리 셋같은거 뛰어보는 방식으로 해결해 봐야 할 것 같습니다. 이번 팀연습도 따지고보면 다 제 실책인데 제가 더 열심히 해야겠어요 ㅠㅠ..