2020 숭고한 Marathon 참가 후기

Intro

원래는 Advanced Division에 참가하려고 했었는데, 팀노트를 만들기 귀찮았고 무엇보다 자신이 작성해둔 코드라도 인터넷 검색에 걸리면 표절이라는 룰이 있었기 때문에 굳이 참가할 이유를 못 찾았습니다. ALPS는 Contest나 Marathon에서 한 문제 이상 해결하면 회비를 면제해주기도 했고, thak00는 이기고 싶었기 때문에 정확히 thak00보다 한문제 더 풀려고 노력했습니다. 여담으로 이번에 domjudge를 처음 써 봤는데 CMS에 비해 매우 별로였습니다. CMS가 최고다!

마지막 두 문제 빼고는 전부 해결했습니다. M은 디버깅 코드를 안 빼고 제출한 관계로 대회 중에는 WA로 기록되어 있습니다. 각 문제를 해결하면서 느낀 점과 셋 구성, 디스크립션에 대해 잡설을 풀어보려고 합니다. 보기에 조금 공격적일 수 있는 표현이 있어도, 글의 재미를 위한 과장이 섞여 있으니 너무 상처받지 않으셨으면 좋겠습니다 (...) 돔저지에서 제출한 소스를 어떻게 보는지 모르는 관계로 제 답안은 없습니다. 제가 느끼기에 정말 좋았다고 생각되는 문제들은 별표 쳐 놓았습니다. ~~자랑스러워하셔도 좋습니다~~

A. 이메일 포렌식

단순 구현 문제였습니다. B보다는 어려운 것 같습니다.

B. 알약을 찾아라!

문제 자체는 매우 잘 알려졌는데, n-1의 가장 먼저 나오는 비트의 번호를 찍으면 됩니다. 개인적으로 검수 과정에서 디스크립션이 충분히 고쳐지지 않은 문제라고 생각합니다. 문제가 쉬워서 망정이었지, 그렇지 않았다면 논란이 생길 수도 있었을 것 같습니다. 확인할 약이 없는데 특효약인지 여부를 검증해야 하는 상황도 있었고, 약이 한 종류면 실험을 안 해도 검증을 할 수 있다고 출력해야 하는 상황도 있었습니다. 이는 명백히 문제 오류고 검수 과정에서 걸러졌어야 하는 상황입니다. 저는 쉬운 문제에서 디스크립션이 더 명확해야 한다는 견해를 가지고 있습니다. 어려운 문제의 경우에는 PS에 익숙한 사람들이 접근하니 디스크립션이 조금 대충 작성되어 있어도 어느 정도는 예측할 수 있는데, 쉬운 문제의 경우에는 그렇지 못해서 초보자들이 당황하기 좋다고 생각합니다.

대회가 끝났으니 말하는 거지만, 대회 중에 디스크립션 문제 관련 질의를 여러 번 날렸습니다. 원래 잘못된 문제를 고치거나 해결하는 건 대회가 끝난 뒤에 해도 된다고 생각하는 입장이여서 대회 중에는 가능한 출제자의 의도를 존중하려고 합니다. 그럼에도 불구하고 이렇게 질의/건의를 여러 번 날린 것은, 문제를 수정하겠다는 답변이나 제 오개념을 바로잡아주는 답변 대신 모순이 넘치는 답변이 돌아왔기 때문입니다. 그러한 답변이 단수가 아니여서 일일히 다 나열하지는 않겠지만, 그 중 가장 재밌었던 것은 치료제가 존재하지 않아도 문제에는 이상이 없다는 답변이었습니다(그렇다면 N=1일때 답은 당연히 0이 아니라 1입니다). 최종적으로 제가 의도한 대로 디스크립션 정정 공지가 뜨기는 했지만, 좋은 과정은 아니었던 것 같습니다. 문제가 많은 것은 이해합니다만 앞으로는 검수가 조금 더 활발하게 진행됐으면 하는 바람이 있습니다.

C. 귀차니즘 성서

그냥 무난한 DP 문제입니다. 여담으로 계산 중 발생할 수 있는 값이 int 범위를 정말 아주 살짝 넘겨서($$) long long을 써야 하는데, 솔직히 의도를 잘 모르겠습니다. 사람 놀리는 것도 아니고, 푸는 사람 입장에서 바로 못 알아채면 꽤나 불쾌할 것 같습니다. 코드포스에 나왔다면 다운보트를 1천개쯤 먹고 가라앉았을 것 같은데(핵이 넘쳐나거나), 일부러 int형의 최대 범위와 매우 가까운 제한을 준 것으로 봐서 그냥 낚으려고 이렇게 문제를 낸 것 같다는 생각이 듭니다. 일단 저는 썩 유쾌하지 않았습니다.

D. 오해받는 숭고한 캠프

디스크립션은 숭고한 동아리 4개로 되어 있는데 막상 문제는 입력으로 주어지는 동아리 이름에 대해 해결해야 합니다. 뭐 그건 굉장히 사소하니 그렇다 치고 문제 자체는 재밌었습니다. 구현에서 굉장히 애를 먹어서 시간을 꽤 날렸던 것 같습니다. 뒤에 나오는 E와 F보다 개인 체감 난이도는 어려웠습니다. 난이도 배치에서 발생하는 문제를 배제하고 문제 내용만을 본다면, 앞쪽 문제 포지션에서 가장 괜찮은 문제라고 생각합니다.

E. 점 매칭

웰노운입니다. 3초 생각하면 됩니다.

F. 바이토닉 트리

그냥 짜면 됩니다. dfs 느낌?

G. 트리 가짓수 세기

중요한 건 이것뿐입니다: BST로 만들 수 있는 트리의 종류는 이진 트리로 만들 수 있는 트리의 종류와 정확히 같습니다. 높이가 제한된 트리의 개수를 세는건 트리 DP로 적절히 구할 수 있고, 이는 NYPC 2018 예선 9번의 하위 호환이며 https://www.acmicpc.net/problem/16468와 같은 문제입니다. 검수진 중에 NYPC 2018 본선 진출자가 있는 것으로 알고 있는데 어떻게 뚫고 출제되었는지는 의문이지만, 그렇다고 못 나올 이유는 없어 보입니다.

H. 제가 수학 문제를 하나 가져왔어요*

생각보다 되게 재밌는 문제였습니다. 주어진 수열은 어차피 초항이 커지면 정확히 그에 비례해서 커지므로, 미리 대충 계산해 두고 나눠지는 수들만 체크해주면 됩니다. 구현에서 말려서 애를 좀 먹었습니다. 저 "미리 대충 계산"을 어떻게 할 지 알기 위해 제 2종 스털링 수에 대한 간단한 구글링이 필요하고, 어떠한 항들을 계산할 필요가 있고 그렇지 않은지를 확인하기 위해 머리를 조금 더 써야 합니다.

I. 이진수 탐색

문제 풀이 자체는 굉장히 쉬운데 저는 코딩을 잘못해서 굉장한 양의 반례를 검토해야 했습니다. 그냥 눈으로 보기에는 도저히 찾을 수 없어서 스캐폴딩을 돌렸고, 그 결과 약 3가지 정도의 코너 케이스를 추가로 처리해줘야 했습니다. 문제 퀄리티는 꽤 좋다고 생각합니다.

J. 3n 투어링*

상하좌우 이동을 최대 4번까지 할 수 있는 상황에서의 open knight's tour을 구하는 문제입니다. 보통 이런 문제는 parity를 나눠서 해결하는 것이 정석이고 출제자도 5에 대한 나머지에 대해 그렇게 해결한 듯 하지만, 사실 N=1,2인 경우만 예외처리를 해 주면 나머지 N에 대해서는 일반적인 해결책이 존재합니다. 구체적으로는 다음과 같은데, (1,1)에서 3번 치트키를 써서 (2,1), (2,2), (3,1) 순서대로 이동한 후 (+1,-2), (-2,+1), (+1,+2)를 반복해주면 됩니다. 이를 (1,N-1)에 도달할 때까지 반복하면 N-2까지의 모든 그리드가 꽉 채워지고 (2,N-1)이 채워진 상태가 되는데, 이때 (3,N)으로 이동하고 마지막 치트키로 (3,N-1)로 이동한 후 (1,N)으로 마지막으로 이동해주면 됩니다. 그러면 항상 치트키 4번 사용으로 모든 칸을 덮을 수 있습니다. (정해일 줄 알았지만 정해가 아니었던)제가 찾은 풀이가 우아해서 1따봉 드립니다.

K. 태양처럼

정말 왜 출제된 건지, 그리고 왜 이 자리에 있는지 출제진한테 여쭤 보고 싶은 문제입니다. 어렵지 않고, 생각할 것도 없는 세그먼트 트리 연습문제입니다. G가 BOJ 기준 플4정도의 난이도를 가질 것으로 추측되는데, K는 BOJ 기준 플5정도의 난이도를 가질 것으로 추측됩니다. 이 대회의 주는 문제 포지션을 담당하고 있는 만큼 앞으로 쭉 땡겨도 된다고 생각합니다. 더해 이러한 단순 자료구조 연습문제성 문제가 대회에 출제될 가치가 있는지는 잘 모르겠습니다.

L. 숭고한 초콜릿*

개인적으로 생각하는 이번 대회 Best Problem입니다. 어렵지 않은 관찰과 알고리즘으로 풀어낼 수 있지만 그 과정은 상당히 우아합니다. 아직 안 풀어보신 분이라면 직접 풀어보시길 강력하게 권하기 때문에 설명은 통째로 생략하겠습니다. Good Luck!

M. 리그 오브 숭고한

그냥 말 그대로 잘 짜면 됩니다. 연세대 RPG Extreme 느낌이 났고 그것보다 약간 더 쉽다고 생각하긴 합니다만, 디버깅 코드를 안 지우고 내는 바람에 (그것도 첫 제출에!) 의문의 -1솔을 당했습니다. 힝

ms와 골드가 좀 헷갈릴 수 있지만, 골드를 1ms당 1mg씩 먹는다고 해도 풀이에는 변화가 없어서 잘 해주면 됩니다. 단 팔 때는 /2000한 다음 *1000 해주어야 소수점 버림을 구현할 수 있습니다.

Outro

좋은 문제들도 있었고 별로 마음에 안 드는 문제들도 있었습니다만, 하여튼 좋은 문제를 몇 개 건진 것 만으로도 돌아볼 가치는 있었던 것 같습니다. N은 높은 확률로 업솔빙 해볼 것 같고 O는 그러고 싶지 않습니다(출제 의도를 모르겠는 문제 중 하나입니다 힝). 이제 숭고한이 마무리 됐으니 UCPC에 집중할 것 같습니다. 회고할 건 이 정도?