Educational Codeforces Round 107 (Rated for Div. 2)

역시 에듀는 마음이 편안하다. 하지만 그렇다고 엄청 잘 풀지는 못해서 블루 복구는 못했다.

 

A. Review Site

upvote하는 사람과 downvote하는 사람은 고정이고, 영화를 보지 않은 사람을 최대한 upvote쪽으로 몰아야 한다. 서버가 2개이므로, 한 서버 쪽으로 upvote하는 사람을 다 보내고 다른 서버 쪽으로는 downvote하는 사람을 다 보내버리자. 그리고 영화를 보지 않은 사람을 upvote만 있는 서버로 보내면, 전부 upvote를 하게 된다.

 

B. GCD Length

gcd(x, y)를 g, x/g = x', y/g = y'이라고 하자. x', y', g가 모두 소수라면 다른 예외사항 없이 항상 조건을 만족한다. 따라서 g를 c자리 소수, x'을 a-c+1자리 소수, y'을 b-c+1자리 소수로 정한다. 이 때, 곱셈을 해서 자리올림이 생기면 안되므로 가장 작은 소수로 정해야 할 것이다. 1~9자리 가장 작은 소수는 울프람알파로 찾아서 하드코딩하고, x'과 y'이 같으면 gcd가 달라질 수 있으므로 x'을 가장 작은 소수, y'을 두번째로 작은 소수로 정한다.

 

C. Yet Another Card Deck

같은 숫자가 여러 개 있어도, 가장 위에 있는 숫자만 움직이므로 인덱스만 저장해두고 좌표압축으로 줄여줄 수 있다. 압축한 수열을 b라고 하면 adj[i]를 b_i 앞에 있는 원소라고 정의해보자.

만약에 쿼리가 3이 들어왔다면, 저장해 두었던 3의 (압축하기 전) 인덱스를 출력한다. 그리고 맨 앞으로 옮겨야 하는데, 인접 리스트로 모델링하면 손쉽게 핸들링할 수 있다. 그림에서처럼 3의 앞에 있는 원소는 adj[3]의 멤버들(초록)이다. 이들 뒤에 있던 3이 앞으로 이동했으므로, 각 멤버들의 인덱스를 +1 하고, adj[]도 업데이트해준다.(파랑)  각 쿼리에 대해 같은 방식으로 계속 진행해 나가면 된다.

 

D. Min Cost String

인접한 두 문자 한 쌍을 한 요소로 생각해보자. 이 한 쌍을 간선으로 모델링해보면 다음과 같다.

세 개의 문자가 있을 때 나올 수 있는 모든 요소들은 aa, ab, ac, ba, bb, bc, ca, cb, cc로 총 9가지이다. 이들을 간선으로 만들면 루프+완전그래프 형태가 된다.(파랑)  따라서 문제를 재해석하면 루프+완전그래프에서 가능한 같은 간선을 지나지 않으면서 순회하는 방법을 찾는 문제가 된다. 각 정점마다 짝수개의 간선이 추가되므로 이 그래프는 무조건 한붓그리기가 가능하고, 오일러 경로가 답이 된다. dfs등으로 오일러 경로를 따라가면서 문자열을 만들고 조건에 맞는 길이만큼 출력하면 된다. 문자열보다 더 긴 길이가 필요하면, 문자열을 한 번 순회하는 것을 한 사이클로 생각하고 여러 번 순회하면 된다.

아이디어는 금방 떠올랐으나 오일러 경로를 순회하는 방법을 몰라서 복잡하게 구현했는데, Hierholzer's Algorithm이라는 dfs 비스무리한 아주 웰노운한 방법이 있다고 한다.

 

E. Colorings and Dominoes (업솔빙)

Green55의 해설을 듣고서야 이해했다. 풀이는 다음과 같다. 먼저 어떤 연속된 두 블록을 딱 고정해놓고 생각해보자. 세로로 두 칸을 고정했다면 파란색으로 칠하고 1점을 얻는게 확정이고, 나머지 칸은 상관이 없다. 따라서 모든 경우의 수에서 저 두칸에서 얻을 수 있는 점수는 2^(남은 o의 개수)이다. 당연히 서로 겹치는 사건이 존재하는데, 여기서 "가로 두 블록을 R로 고정했음"이라는 사건과 "세로 두 블록을 B로 고정했음"은 겹치지 않으므로 서로 독립적이다. 왜냐하면 어떤 한 칸이 가로 두 블록을 채우면서 세로 두 블록을 채울 수는 없기 때문이다. 그러면 결국 겹치는 사건들은, 연속되게 존재하는 칸에서만 발생한다는 것을 알 수 있다. 그럼 결국 우리가 궁금한 것은 "n칸이 연속되게 존재할 때, 이 칸에서 얻을 수 있는 점수의 합"이 된다. 백트래킹으로 완전탐색을 짜서 돌린 후 oeis에 치면 예쁜 점화식이 나오니까 가져다 쓰자. 찾은 점화식을 f(n)이라 하면, 결과적으로 답은 f( (연속된 o의 갯수) - 1 ) * 2^( (o의 총 갯수) - (연속된 o의 갯수) ) 의 합이 된다.

애초에 겹치는 사건 분류를 못해서 풀진 못했지만, oeis를 활용한 답이라니 정신이 혼미해진다. 에디토리얼 뜨기 전에 댓글들을 살펴보니 다들 oeis로 풀은 것 같았다. 에디토리얼의 정해는 마찬가지로 완전탐색 돌린 후, 규칙을 잘 찾으란건데... 확률이 1/4, 1/4 - 1/8, 1/4 - 1/8 + 1/16, 1/4 - 1/8 + 1/16 - 1/32, ... 이런 형태로 나타난다고 한다.

업솔빙 도중에 오버플로우가 안잡혀서 여러 번 틀렸는데, 템플릿을 구해서 사용했더니 바로 AC 받았다.