cdjs의 코딩 공부방

P4 | 2532 - 먹이사슬

풀이 시간: 약 30분

시도 횟수: 4회 + 1회 (992ms로 통과한 뒤에 좌표압축 다시 구현해서 제대로 풀었음)

체감 난이도: P3 하위권

풀이 쓸 의향: 中

풀이

여담: 시즌 292148호 태그랑 딴판으로 문제풀기 성공! 문제 풀다가 "이거 lis 비슷하게 될것 같은데...?" 싶다가 갑자기 세그트리 풀이로 틀어버렸다.

군대에서 후임, 동기와 함께 ICPC Seoul Regional Mirror Contest에 참가했습니다.

원래 팀명을 부대 이름으로 할까 고민했다가, 그냥 별 의미 없는 이름으로 지었습니다.

군대 입대 이후로 살면서 가장 열심히 PS를 하고 있고, 전역하고 나서 24년도 ICPC Regional에 반드시 참가하겠다는 의지로 올해 ICPC Mirror에 참가했습니다.

팀원은 부대에서 PS를 잘하는 사람을 모아온 것이 아니라, 그냥 저랑 친한 친구 두 명(@terabyte, @asdarwin03)을 불렀습니다.

팀 대회는 고등학교 시절 2인으로 치뤘던 에리카 대회를 제외하고는 한 번도 치뤄본 적이 없었기 때문에, 높은 등수가 목표라기보단 단순히 팀 대회를 해보고 싶어서 친한 친구들끼리 진행했습니다. 그래서 팀 노트도 없이 그냥 대회를 진행했습니다.

당연히 세 명 모두 부대 안에 있었기 때문에, 사지방에서 대회를 진행했습니다.

다른 사람들도 사용하는 공공장소이기에 컴퓨터 하나를 잡고 세 명이 모여서 앉기도 힘들었고, 서로 이야기하기는 더더욱 힘들었기에 대회 전에 대안을 생각해 두었습니다.

우선 대회 로그인은 제가 해 두고, discord를 통해 대회 시작과 동시에 문제를 전송했습니다. 세 명이 서로 컴퓨터를 잡고 고민하다가, 풀이가 생각나면 "이제 코딩 시작한다" 라는 멘션을 보낸 뒤 코드를 짰고, 그 동안 다른 사람들은 코드를 짜지 않기로 했습니다.

서로 말도 못하므로 거의 대부분의 대화는 discord 메시지를 통해 진행됐습니다. 점심 시간에나 같이 밥을 먹으며 대화를 나누고자 했으나, 밥을 먹을 타이밍쯤에는 안타깝게도 별로 논의할 내용이 없었어서...

또, 스코어보드도 제가 가끔씩 보면서 캡쳐로 보내주는 방식으로 봤었습니다. 제가 스코어보드를 보면서 풀만한 문제들을 색출하고 친구들에게 던져주는 역할을 했습니다.

이번 대회 목표는 크게 두 가지였습니다.

1. 세 명 모두 적어도 한 문제씩은 풀자 : 제가 부른 친구 둘은 사실 저만큼 PS를 열심히 하는 친구들은 아니었고, 사실상 제가 미러 대회 쳐보고 싶어서 강제 차출 수준으로 불렀습니다. 그 상태에서 제가 쉬운 문제라고 전부 다 풀어버리면 당연히 두 명은 재미가 없을 것이므로, 세 명이 한 문제씩은 풀 수 있도록 노력하기로 했습니다. 제가 스코어보드를 보니, 쉬워보이는 문제들을 친구들에게 넘기고 저는 어느 정도 난이도 있는 문제를 풀기로 했습니다.
2. 플레티넘 중상위 문제를 적어도 한 문제는 풀어내자 : 최근 USACO를 중심으로 플래티넘 중상위 랜덤 디펜스를 열심히 하고 있었는데, 풀면서도 "내가 대회 중에 이 정도 난이도를 풀어낼 수 있을까" 하는 걱정이 컸습니다. 플랜디 중에는 난이도가 보이지만, 대회장에서는 문제 난이도가 안보이니 풀어내기 더 어려울 것 같았습니다. 그리고 제가 최근 열심히 문제를 풀었던 결과물을 (미러긴 하지만) 대회에서 실제로 보고 싶었습니다.

3초간의 마라톤 회의 끝에, terabyte는 ABCD, 저는 EFGH, asdarwin03은 IJKL을 보기로 했습니다.

다음은 대회 타임라인입니다.

대회 시작 타이밍에 Contest Delayed가 뜨길래 잠시 기다리다가, 00:02에 접속이 되는것을 확인하고 즉시 ICPC 홈페이지에서 본선 문제를 다운로드받아 전송했습니다.

E번 문제를 봤는데, 처음에는 상당히 어려워 보였습니다. $m \leq 10n$이라는 조건을 못봐서 이 문제는 답이 없다 생각하고 빠르게 F번으로 넘어갔습니다.

F번 문제를 읽어봤는데 간단한 문제같아 보였습니다. 풀이를 생각해보진 않았지만 단순히 path에 있는 거리 계산을 구현하기만 해도 풀릴 것 같았습니다, 바로 팀원들에게 문제 다 보고 풀거 없으면 F번 보라고 일러두고 다음 문제를 읽었습니다.

G번은 보자마자 제가 풀 문제가 아니라 생각하고 던졌고, H번은 제가 아직 제대로 공부도 하지 않은 문자열 문제이길래 바로 던졌습니다. 이렇게 10분만에 제가 봐야할 문제를 다 보고 다른 문제들을 살펴보다, asdarwin03이 I번 문제가 LCS nlogn으로 풀릴 것 같지만 알고리즘 구현 기억이 안난다면서 저에게 I번을 던졌습니다.

안타깝게도 저도 LCS nlogn 풀이를 외우고 다녔던 것은 아니라 문제를 찬찬히 읽고 있었는데, $k=0, 1, 2, 3$이라는 조건으로는 투 포인터 및 백트래킹으로 풀릴 것 같아 보였습니다.

그렇게 바로 I번 구현에 들어갔고, AC를 받았습니다.

00:20 I AC

풀자마자 terabyte가 B번 문제가 구현 문제인것 같다며 구현을 시작했고, asdarwin03은 J번이 단순 그래프 BFS 구현 문제인것 같다고 합니다. terabyte가 아직 C, D번 문제를 안봤다길래 C, D번 문제를 읽어봤습니다.

근데 C번은 보자마자 빡센 기하학 문제같아 보여서 바로 걸렀고, D번 문제를 읽었습니다.

D번 문제는 그래도 할만해 보여서 해당 문제를 이리저리 생각해 보고 있었습니다. 그리디로 풀리나 싶어서 고민하던 중, 문제 상황 추상화 중에 terabyte가 5분만에 코드를 짰다고 코드를 줬지만, 스코어보드에는 아무도 B를 풀지 못한데다 예제에서도 틀리는 코드였기에 바로 B번을 버리고 F번을 보라고 말해줬습니다. 그 즉시 asdarwin03이 J번 구현을 시작했고, 2분만에 코드를 짜서 제출했지만 틀렸습니다. 코너 케이스를 처리하지 않은 것 같다며 코드를 다시 짜다가 10분쯤 뒤에 도움을 요청했는데, 코너 케이스 문제가 아니라 답이 long long 범위인데 int를 써서 틀렸던 것이었습니다. int를 long long으로 바꿔서 다시 제출했고, AC를 받아냈습니다.

00:32 J WA

00:47 J AC

J AC 코드를 작성 중에 terabyte가 F번이 단순 구현이라며 손코딩을 시작했고, J AC를 받은 뒤 구현에 시작하여 약 10분 뒤 F도 AC를 받아냈습니다.

00:59 F AC

이 시점에서, 이미 목표 1.은 달성했습니다. 이때쯤 스코어보드를 한번 캡쳐해서 보내줬습니다. 남은 문제들 중에서 K, D, E 순서로 많이 풀렸었는데, D는 원래 terabyte의 문제였으므로 가서 문제에 대해 알아낸 내용을 설명해줬고, K, E 중 어떤걸 asdarwin03에게 줄까 고민하다가 그래도 K가 더 많이 풀리기도 했고, 제가 원래 E번을 보는 거였으니 제가 E번을 보고 asdarwin03이 K를 보기로 했고, 문제만 대충 읽은 뒤 밥을 먹으러 갔습니다.

밥을 먹기 전에 E번 문제를 보던 중 문제 제한에 $m \leq 10n$인 것을 발견하고, 그럼 대충 구현해도 맞지 않을까 싶어서 생각해 보니까 충분히 가능해 보였습니다. 플레 하위권 정도의 구현이 필요해 보였고, 제가 풀기로 생각했습니다. 다만 밥을 좀 천천히 먹는 바람에 약 40분 가량을 날렸고, 밥을 먹고나서 바로 구현해서 10분만에 AC를 받았습니다.

02:04 E AC

사실 밥을 조금만 더 빨리 먹으면 좋았겠다 싶긴 했지만, 대충 플레 하위권 그래프 문제를 하나 풀었다는 점에 만족하고 넘어갔습니다. 다만 약간 물플레 수준 아닌가 싶은 난이도였어서, 목표 2.를 성공했다고 보기엔 조금 애매했습니다.

그 타이밍에 본선 스코어보드를 봤었는데 본선 38등 수준의 점수였습니다. 물론 대회장과 환경이 다르므로 곧이곧대로 비교하긴 힘들겠지만 사실상 제가 끌고온 멤버를 데리고 이정도 성적을 냈다는 점에 상당히 만족했습니다.

E번을 풀고 나서 terabyte에게 D번에 대한 조금 더 자세한 내용을 들었는데, 문제를 추상화한 결과 "수열에서 연속한 부분을 적절히 합쳐서 증가 함수를 만들었을 때 함수의 최댓값의 최솟값을 찾아라" 였습니다. 최댓값을 인자로 갖는 Parametric Search가 가능할까 생각해봤으나 증가 함수여야 한다는 조건을 맞추기가 힘들어 보여서 일단은 terabyte에게 넘기고, L번 문제를 살펴봤습니다.

이 과정이 조금 복잡하게 돌아갔는데, discord로 소통을 하다 보니까 이것저것 많이 섞여버렸습니다. 제가 L번 문제를 생각하던 도중 terabyte와 D번에 관한 내용을 논의하고, 그러면서 asdarwin03에게 K번이 DP 문제일것 같다는 이야기를 들었습니다. L번 문제는 크기 3 이상의 동일한 크기의 서로 다른 사이클 두 개를 찾으라는 문제이므로 tree dp를 사용해 풀 수 있을것 같아 dfs로 구현하다가 중간에 구현이 꼬여버리는 바람에 약 30분동안을 날려버렸습니다. 그 와중에 asdarwin03이 K번 문제를 구현해보겠다고 해서 자리를 비켜주고, terabyte가 D번을 포기하고 C번을 보겠다고 선언해버려서 일단 L을 버리고 제가 다시 D번을 보기 시작했습니다. 이때쯤 든 생각은, 우리가 풀 수 있는 최대는 DEFIJKL으로 총 7문제라고 생각했습니다.

그렇게 30분이 지나고, asdarwin03이 구현하다 중간에 막혀서 다시 메모장 모드로 들어갔고, C번을 보던 terabyte는 빠른 포기 후 asdarwin03과 같이 K를 보기 시작했습니다. 저는 D를 보겠다고 했으면서 L번에 미련을 못버리고 L번에 집착하고 있다가, 원래 생각했던 방식이 완전히 틀렸다는 것을 늦게 파악하고 다시 D로 돌아갔습니다. 그러던 중 풀다가 정신이 나가버린 나머지 한 번을 그냥 약간의 최적화를 거친 O(N^2) dp 코드를 신뢰의 도약으로 던졌다가 어림도 없이 TLE를 받고, 약 10분 뒤 정신을 차리고 식 정리를 끝마쳐 D번을 맞았습니다.

04:36 D WA

04:45 D AC

전 이때쯤 K번에서 좋은 소식이 들려올 줄 알았지만, 안타깝게도 두 친구 모두 K번을 푸는 데 실패하고 말았습니다. 저도 마지막 15분동안 K번에 도전해봤지만, 결국 실패하고 예제에서도 틀리는 asdarwin03의 K번 코드 제출을 마지막으로 대회가 끝났습니다.

이렇게 총 5 Solve로 대회를 끝마쳤습니다. 실제 대회장에서 이 정도 성적이었으면 45등의 성적이네요.

대회를 치면서 느껴졌던 아쉬웠던 부분들은,

1. 너무 산만했다 : 대회 환경을 말하는 것이 아니라, 너무 여러 문제들을 동시에 봤던 것 같습니다. 실제로 중간에 E번을 풀고 난 이후로 어떤 문제를 잡아야 할지 갈피를 못잡아서 K번을 보다가 L번을 보다가 D번으로 돌아간 뒤에 다시 L번으로 갔다가... 물론 결국 D번을 풀긴 했지만, 한 문제씩 고민을 했더라면 K번까지는 풀 수 있지 않았을까 하는 아쉬움이 남습니다.
2. 서로 소통을 잘 못했다 : 사지방에서 대회를 쳤던 거라 서로 말을 못했던게 좀 아쉬웠습니다. 디스코드로는 소통하는 데 제약이 있었고, 물론 기록하는 용도로는 괜찮았으나 결국 채팅을 치느라 꽤 오랜 시간을 보냈던 것 같습니다. 실제 대회 환경에서는 어떻게 소통하게 될지 감을 아직 잘 못잡겠습니다.
3. K번을 결국에는 못풀었다 : 이건 사실 제가 아쉽다기 보다는 같이 대회를 치뤘던 asdarwin03과 terabyte가 좀 아쉬울 것 같았습니다. 특히 asdarwin03은 본인의 원래 실력보다 더 낮은 성적을 얻은 것 같아 더 아쉽습니다.
4. L번에서 뇌절을 너무 심하게 했다 : 이건 1. 너무 산만했다 의 결정적인 원인이기도 했는데, 제가 좋아하던 그래프 문제에서 그렇게 뇌절을 때려버린 것이 조금 많이 아쉬웠습니다.

전 원래 목표였던 1. 세 명 모두 한 문제씩은 풀자 는 성공했고, 2. 플래티넘 중상위 수준의 문제를 풀어내자 또한 E번과 D번을 풀어내며 성공했습니다. 사실 큰 기대 없이 치뤘던 대회였던 만큼 5솔브라는 꽤나 괜찮은 성적에도 만족하고 있습니다.

다만 앞으로 더 실력을 쌓아야겠다는 생각도 들었습니다. 이번 대회에서 이상적인 성적은 L, K까지 풀어내면서 7솔브를 하는 것이었는데, D, L에 시간을 너무 쏟아 실패했다는게 많이 아쉬웠습니다.

내년에도 저는 군대에 있을 예정이기에 ICPC 본선에 직접 출전은 못하겠지만, 다음 ICPC때까지 ICPC 리저널 본선에 나오는 플래티넘 수준의 문제는 무조건 풀 수 있는 실력까지 끌어올리고 싶습니다.

P4 | 3043 - 장난감 탱크

풀이 시간: 30~40분

시도 횟수: 3회

체감 난이도: P4 하위권

풀이 쓸 의향: 下

풀이

여담: 동일한 칸에 겹치는 탱크를 고려 안해서 -1, push_back(y)자리에 (x) 집어넣어서 -1... 복붙하다 실수했다..

P3 | 1523 - 종점

풀이 시간: 25분

시도 횟수: 1회

체감 난이도: ??

풀이 쓸 의향: 下

풀이

여담: 사실 난이도 플레 랜덤으로 슬쩍 가리고 풀었는데... 풀고 나서 이게 이 난이도가 맞나 싶었던 문제. 경험상 이런 생각이 들던 문제들은 보통 다른 사람이 기여했던게 맞았어서 난이도 기여에서는 손 뗐다.

P4 | 1604 - 도망자 원숭이

풀이 시간: 약 1시간

시도 횟수: 2회

체감 난이도: P4

풀이 쓸 의향: 下

풀이

여담: 플로이드-워셜 알고리즘이 어떻게 동작하는지 다시 찬찬히 이해해본 다음에야 풀 수 있었던 문제. 훌륭한 문제인듯.