2020 중앙대학교 프로그래밍 대회 (CPC) 검수후기 / 풀이
카테고리 없음 2020. 11. 22. 03:09www.acmicpc.net/category/detail/2345
처음으로 대회 검수에 들어가 보는 경험이 되었다. 서버 이슈가 약간 아쉽지만 출제하신 분들이 정말 많이 노력해 주셔서, 검수 및 풀이 과정은 재밌었다. 전체적인 난이도도 브실골플 1232로 밸런스 있게 짜여졌다고 생각한다. 풀이 슬라이드가 있는지는 잘 모르겠는데, 아무튼 블로그에 내 후기 / 풀이를 적어보기로 했다.
A. 교수님 그림이 깨지는데요? [Bronze 1]
설명 : 설명하는것보다 문제 읽는게 빠르다. www.acmicpc.net/problem/20205
풀이 : 그대로 구현하면 된다.
B. 푸앙이가 길을 건너간 이유 [Silver 2]
설명 : 직선의 방정식과 직사각형이 주어질 때, 직선이 직사각형과 만나는지 여부를 확인하는 문제.
풀이 : 직선의 기울기와 등등에 따라 경우를 매우 열심히 나누는 풀이가 있지만, 매우 힘들고 귀찮을 것이다. 얼핏 기억에는 대회중 잠시 채점현황을 구경했을 때 시도하는것 같은 팀이 있었는데 그 결과는 모르겠다.
좀더 쉬운 접근법은 점과 직선의 위치관계를 이용하는 것인데, $ax + by = c$ 의 직선과 점 $(p, q)$ 가 있을 때, $ap + bq > c$ 인지, $ap + bq < c$ 인지가 직선의 위와 아래를 구분한다. 따라서 직사각형을 이루는 네 점이 모두 한쪽에 몰려있으면 직선이 직사각형을 지나지 않는다.
여담 : 이 대회는 educational한 성격이 좀 있으므로, double로 풀리지 않게 하거나 int 범위를 넘어서는 좌표를 줬어도 나름의 educational한 의미가 조금 있었...으려나?
C. 달력 [Silver 1]
설명 : 마찬가지로 읽는게 빠르다.
풀이 : 거의 그대로 구현하면 된다. 앞으로 나가면서 0의 위치들을 기억하자. 0이 나올때마다 이전 0이 어디었는지와 비교해서 길이를 확인하면 되고, 그 구간 사이의 max값은 max를 계속 하다가 0이 나올때마다 초기화해주기만 하면 쉽게 구할 수 있다. 나는 개인적으로 B번보다 쉽다고 생각했다.
D. 진우의 민트초코우유 [Gold 5]
설명 : $n \times n$ 그리드 지도에 *민트초코우유* 들이 있다. 민트초코우유를 챙길때마다 체력이 늘어나고, 이동할때마다 한칸당 1씩 체력을 소모한다. 최대한 많은 우유를 먹고 집으로 돌아오는 문제.
풀이 : Traveling Salesman Problem처럼 생각할 수 있다. TSP를 bit DP로 $\mathcal{O}(n * 2^n)} 시간에 풀 때, dp 테이블을 [현재까지의 방문에 대한 비트마스크 정보] 와 [지금 방문할 예정인 정점] 으로 잡는데, 이것처럼 해주자. 여기서 체력 요소가 들어 있으므로, DP를 [현재까지 방문][방문 예정인 정점][남은 체력] 의 3차원으로 잡아서, 이 테이블을 다 채워주면 된다. 채우는 방법은 외판원 순회 문제에서 체력이 추가된 형태로 하면 된다.
이 풀이의 시간 복잡도는 총 채워야하는 DP 테이블의 칸수인데 (한 칸당 $O(1)$에 채울 수 있으므로), 이는 최대 $n * 2^n * H$ (H는 최대체력) 이다. 최대체력이 $10n$ 보다 조금 많은 정도이므로 넉넉하다.
여담 : 이 문제의 경우, 다양한 풀이가 있다. 가장 쉽게 생각할 수 있는 풀이는 먹을 우유의 permutation을 모두 돌면서 $O(n \times n!)$ 에 브루트포스로 돌리는 것인데, 난이도 조정을 위해 검토도중 이 풀이가 허용되었다. 내가 위에 서술한 풀이도 별로 좋지 않고, $n$을 하나 더 뗄 수 있는데, 적당히 생각해보면 많이 어렵지는 않다.
처음 문제를 봤을때 $n$이 20인가 15였던것 같은데, 줄어들다 보니 10이 되었다.
여담 2 : 민트초코우유를 먹을때마다 체력이 늘어난다는 문제의 기본 가정에 동의할 수 없다. 다만 지문에 판타지 세계관을 쓰는 문제는 많으므로 그렇게 납득하고 넘어가기로 했다. :P
E. 스트레이트 스위치 게임 [Gold 3]
설명 : 모든 숫자는 모듈러 5. 여러 개의 숫자들과 연결된 스위치들이 있으며,
$i$번 스위치를 한번 누를때마다 스위치에 연결된 숫자들이 $i$만큼 증가한다. (모듈러 5)
스위치를 최소 횟수로 눌러서, 모든 숫자를 같게 만들고 싶다.
풀이 : 한 스위치를 5번 누르는것은 누르지 않는것과 같다는 사실을 관찰하자. 스위치가 $n \leq 8$ 개이므로, 최대 $5^8$ 개의 스위치 조합을 검초하면 문제의 상황에서 제시될 수 있는 모든 경우를 확인한 것임을 알 수 있다. 따라서, 그냥 이 모든 경우의 수를 돌면서 확인해 주면 된다.
여담 : 구현하기 생각보다 어려웠다. 왜 말렸는지 잘 모르겠다.
F. 파일 탐색기 [Gold 2]
설명 : natural sort 를 구현하는 문제. 구체적으로는, file10.txt 가 file2.txt보다 뒤에 오게 해주는 그런 방식인데, 문자열을 비교하다가 숫자를 만나면 숫자를 통째로 봐서 대소를 비교하고...뭐 그런 방식이다.
풀이 : 그대로 구현하면 된다. 나는 미리 문자열을 쭉 보면서 숫자들을 따로 파싱해놓고, vector<string> 끼리 서로 비교하는 식으로 구현했는데 이렇게 하면 조금 더 편할 것 같기도 하다. 시간은 넉넉하므로 대충 돌아도 된다.
숫자가 100자리까지 연속되어 올 수 있는데, bigint를 짠다거나 하기보다는 그냥 문자열로 시키는대로 비교하는게 좋다. 0의 개수를 미리 세면서 0을 떼놓고 숫자끼리 문자열 비교를 하면, leading zero가 없고 길이가 같은 숫자는 숫자의 대소가 문자열의 대소와 같다.
여담 : 이런 스타일의 문제가 늘 그렇듯, 한번 꼬이면 어디서 틀렸는지 찾기도 어려운데 못찾으면 그대로 퍼포먼스가 망하므로 침착하게 천천히 짜야 한다. 개인적으로 그걸 매우 어려워하기때문에 대회중에 만났으면 상당히 고통받았을것 같은데, 마음을 편안히 갖고 천천히 짜니까 되더라(...)
G. 게임 개발자 영우 [Platinum 2]
설명 : 설명하기는 좀 길다. www.acmicpc.net/problem/20211
풀이 : 먼저, 다음을 관찰하자.
1. 모든 경우에 경험치는 홀수만큼 주어지므로, 경험치의 parity는 매번 반드시 바뀐다.
2. 어떤 레벨이 구간 $[s, e]$ 에 해당한다면, 그 게임의 시작지점 $s$에서의 경험치는 짝수 (0) 이다.
3. 따라서, 2번을 이용하면, "$[s, e]$ 만큼이 한 레벨이라면 그 레벨에서 먹은 경험치" 의 양을 $O(1)$ 에 구할 수 있다.
이제, 레벨당 필요 경험치 $x$에 대해, 가능한 총레벨수 $y$를 찾는 방향으로 생각하자. $x$ 는 최대 $5n$ 이므로, 각 $x$에 대해 빠르게 ($O(n)$ 미만의 시간에) 가능한 답 $y$를 찾아야 한다.
현재 시작점을 알고 있다면, 내가 다음 레벨업을 하게되는 시점을 구하면 된다. 만약 앞에서부터 다음 레벨업 시점을 naive하게 구한다면, 최대 $n$개의 구간 $[s, e]$ 들을 실제로 계산해보는 것이 되고, 그러면 한 $x$에 대해 소요 시간이 $O(n)$ 이 된다. 이를 피하기 위해, '다음 레벨업 지점' 을 Binary search해 주자.
구간당 $O(1)$에 경험치량 구하기는 prefix sum array를 사용하면 되는데, 약간의 트릭을 쓰면 더 쉽게도 가능하다. 홀수/짝수에 따라 경험치가 1점/5점 또는 3점/3점으로, 어떤 경우든 홀짝에 따라 $t$ 또는 $6 - t$ 임을 이용하면 된다.
시간 복잡도 증명* : Worst Case를 생각하자. $x$에 대해, 봐야 하는 구간의 개수는 그 $x$에 대응하는 레벨의 수 * $\log n$ 으로 바운드를 잡을 수 있다. 레벨경험치 $x$에 대응하는 레벨의 수를 생각해 보면 전체 게임의 경험치는 $O(n)$점 주어진다고 볼 수 있으므로 (실제 최대 $5n$점), 레벨의 수는 대략 $O(n/x)$ 이라고 봐도 되겠다. 따라서 전체 시간복잡도는
$$ \log n \sum_{x = 1}^{5n} \frac{5n}{x} = \mathcal{O}(n \log^2 n)$$
이렇게 볼 수 있다.
* 증명까지는 아니고, Argue 정도 된다. Gap이 많다.
여담 : 이 대회 최고 난이도 문제. H가 난이도가 조금더 높을수는 있지만, '생각하는 난이도' 는 이 문제가 가장 어렵다.
다른 풀이를 모두 읽어보지는 못했지만 $O(n \log^3 n)$ 도 있다는듯 하다.
H. 나무는 쿼리를 싫어해~ [Platinum 2]
설명 : $[i, j]$ 에 $k$를 더하는 range addition query와, $k$번째 addition query까지 적용되었을 때 $[i, j]$ 구간 합을 구하는 time-machine range sum query (누군가 이렇게 부르는걸 듣고 직관적으로 마음에 들었는데 어디서 본건지 기억이 안난다) 를 처리하는 문제.
풀이 : time machine 형 쿼리는 (출처를 알 수 없는 표현이지만 마음에 드니까 그냥 쓰기로 한다) 업데이트 쿼리를 모아서 오프라인으로 시간 순서대로 처리하면 일반적인 쿼리처럼 해결할 수 있다. 즉 업데이트를 하다가 중간에 때가 되면 대답해 주면 된다. 따라서, range addition과 range sum query를 어떻게 잘 처리해 주면 되겠다. 정확히 이걸 위해 존재하는 자료구조인 Lazy-propagation Segment Tree 를 떠올릴 수 있다.
그러나, 이 문제는 구간이 최대 10억까지이므로 그냥 Lazy seg로는 풀 수 없다. 대신에, Segment tree에서 구간이 크지만 실제 사용하는 노드가 몇개 없는 상황일 때 쓰는 Dynamic Segment Tree가 있다.
두개를 합친 Dynamic Segment Tree with Lazy Propagation을 구현하면 된다. 처음 해본다면 매우 어려울 것이다.
나는 예전에 어디선가 본 구현을 조금 수정해서 쓰고 있다.
여담 : 다이나믹 레이지 세그먼트 트리를 알고 있다면 문제 자체는 어렵지 않다. 다만 그냥 저 자료구조가 플레 2 레벨일 뿐... 추가로, 출제자 분의 원래 의도는 이게 아니었던 것 같은데 (좌표압축 + 세그먼트 트리 같은식으로 할 수 있다) 거의 모든 검수진이 다이나믹 레이지 세그트리를 박았다.
나름 educational한 의미도 있고, 전반적으로 좋은 셋이었다고 생각한다. 다만 대회 중에 실제로는 뒷부분 문제들이 풀리지 않아서, E부터는 사실상 open contest를 위한 문제가 되었다.
간단한 문제라도 테캐 validation하고, 정해 짜고, 다른 풀이들의 허용여부를 결정하고 테스트하는게 생각했던 것보다도 더 어려운 과정임을 느낄 수 있었다.
출제진 / 검수진분들 수고많으셨습니다! 덕분에 재밌게 참여할수 있었습니다 :D
