Topcoder SRM 794, 795 후기

Topcoder는 알고리즘 대회인 Single Round Match (일명 SRM)을 비롯해 다양한 프로그래밍 분야의 온라인 대회를 여는 사이트이다. 온라인으로 알고리즘 문제 해결 대회를 정기적으로 여는 대표적인 사이트는 Topcoder 외에도 Codeforces, Codechef, AtCoder 등이 있는데, Topcoder SRM은 그 중에서도 가장 오랜 역사를 자랑하는 근본 넘치는 대회이다.

Topcoder SRM은 Div1 / Div2로 나뉘어 열리며, 각각 Easy / Medium / Hard의 3문제가 나온다. SRM 하나의 시간표는 보통 아래와 같이 진행된다.

코딩 (75분) -> 휴식(5분) -> Challenge(15분) -> System Test

코딩 시간에는 문제를 읽고 풀어서 코드를 제출하게 된다. 코드를 제출하면 점수를 얻는데, (문제를 연 시각)과 (코드를 낸 시각)의 차이가 작을수록 점수가 크다. 다른 플랫폼과 크게 다른 점은 제공하는 채점 데이터가 예제뿐이라는 것이다. 심지어 예제가 틀렸는지도 제출 시 따로 검사해주지 않기 때문에 로컬에서 테스트 및 디버깅을 충분히 해야 한다.

Challenge 시간에는 같은 Room (참가자를 20명 정도 단위로 Room에 나누어 배치한다) 안에 있는 다른 참가자들의 코드를 열어서 살펴보고, 틀린 점이 있다면 그것을 저격하는 테스트 데이터를 만들어서 "Challenge"를 걸 수 있다. Challenge가 성공하면, 즉 코드를 틀리게 하는 데이터를 정확히 만들었다면 점수를 얻고, 실패하면 점수를 잃는다. Codeforces의 "Hack" 시스템은 여기서 착안했다고 볼 수 있겠다.

System Test 시간에는 미리 준비해놓은 데이터 + Challenge 시간에 사람들이 찾은 데이터를 모두 돌려서 실제 채점을 한다. 이걸 통과하지 못하면 빨간색으로 "Failed System Test"라는 글자가 뜨는데 매우 기분이 나빠진다.

Topcoder SRM에 참가하기 위해서는 Java Applet을 하나 깔아야 하는데, 이게 디자인이 참 묘해서 처음 참가하는 사람한테는 적응이 좀 힘들 수 있다. 자세한 설명은 여기 가면 볼 수 있다.

나는 한 1~2년 전에 Topcoder를 시작해 보려다가 어떻게 하라는 건지 몰라서 못 했었는데, 얼마 전에 어떻게 시작을 해 보게 되었다. 12월 초에 열린 SRM 794, 795에 각각 참가하였다.

---

SRM 794는 계정 생성 후 첫 참가라서 Div 2로 참가하였다.

Easy : 두 자연수 N, D (1 ≤ N, D ≤ 9) 가 주어지면 D자리 수 N개를 반환하는데, N개의 수들의 첫 자리가 모두 달라야 하고, 마지막 자리도 모두 달라야 하고, 각 수 안에서 또 각 자릿수들이 모두 달라야 한다.

"123456789"의 앞 D자리를 떼 온 다음 한 칸씩 rotate해서 N개까지 채우면 된다. Div2 Easy라서 진짜 쉽다. 그 와중에 Challenge에서 이상한 코드 2개도 찾아서 100점 먹었다.

Medium : 길이 2N짜리 수열에서 0이 N개 있고 1이 N개 있다고 하자. 수열에서 인접한 두 수의 위치를 바꾸는 연산이 있다고 할 때 처음 수열을 "0101....01" 꼴로 만들기 위해 필요한 최소 연산 수를 구해라.

1이 2개 있으면 그 둘의 순서 관계를 바꿀 이유가 없기 때문에 앞에 있는 1부터 순서대로 어디로 갈지가 정해진다. 위치 차이의 절댓값을 합해주면 끝. 입력 형식이 수열을 그냥 주는 것이 아니고 1의 위치를 \( Ai+B \mod 2N \) 꼴로 주는 것이었는데, 위치 계산하다가 overflow 나는 코드가 4개나 있어서 200점을 먹었다...

Hard : 물과 땅으로 이루어진 grid가 주어진다. 맨 바깥 둘레는 무조건 물로 둘러싸여 있는데, 그곳은 "바다"이며, 땅으로 둘러싸인 물들은 "호수"이다. "호수" 내부에 위치할 수 있는 가장 큰 섬의 크기를 출력하라. (섬은 육지와 가로,세로,대각선으로 인접하면 안 됨)

모든 땅 cell마다 주변 8방향까지 확장해서 체크해준 뒤, 체크가 되지 않은 물 cell에서 flood fill을 돌리면 된다. 8방향으로 dfs를 해야 되는 부분 하나를 4방향으로 해버려서 System Test에서 틀렸다..

Hard를 날려먹은 덕분에 1등도 날려먹고 10등 정도 했는데 레이팅이 1500이 넘어서 바로 Div1으로 갔다. 오예!

---

SRM 795는 Div 1으로 참가하였다.

Easy : 가중치 있는 N x N 인접 행렬이 주어지면, 모든 정점 순서쌍 (s, e)에 대해 "s에서 간선을 minDays번 이상 타서 e로 가는 가장 짧은 경로"들의 길이의 합을 구해라. (N ≤ 50, minDays ≤ 10^9)

\( D[i][j][t] \) 를 i에서 j까지 간선을 "정확히 t번" 타서 가는 가장 짧은 경로라고 정의하면 \( D[i][j][t] = min(D[i][k][t - 1] + adj[k][j]) \) 꼴이 되는데, \( D[i][j][X] \)를 행렬곱 하듯이 \( N^3 log(X) \) 만에 계산할 수 있어서 X = minDays까지 계산한 뒤 거기서 N번만 더 진행시켜보면 된다. 근데 나는 이상하게 풀어서 Challenge 당했다 ^^;

Medium : 무한히 넓은 체스판 위에 말이 N개 있다. 각 말은 한 번의 이동으로 상하좌우 중 하나로 이동할 수 있다. N개의 말을 "N x N 체스판 위에 룩 N개를 서로 잡히지 않게 둔 모양"이 되도록 적절히 옮긴다고 할 때, 가능한 최소 이동 횟수의 합를 구하여라.

일단 행 좌표와 열 좌표를 아예 따로 생각해도 됨을 알 수 있다. 이제 문제가 1차원으로 바뀌는데, \( f(X) \)를 "말 N개를 좌표 \( [X, X+N-1] \) 구간에 하나씩 놓는다고 할 때 필요한 이동 비용"이라고 하면 기울기가 단조증가하기 때문에 기울기에 대한 이분탐색으로 \( O(NlogN) \) 만에 최솟값을 구할 수 있다. 나는 놀랍게도 입력 생성하는 부분을 잘못 짜서 한 100점을 날려먹었다...

처음에 수열을 정렬한 다음에 i번째 좌표에서 i를 빼 주면 N개의 점을 한 곳으로 모으는 문제로 바뀌는데, 이를 이용하면 조금 더 쉽게 짤 수 있다. 그런데 이 풀이는 그 다음에 정렬을 한 번 더 안 하면 틀리기 때문에 그걸로 150점을 먹었다 ^^

Hard : 정점 N개짜리 양방향 가중치 그래프가 주어진다. 또, 할인권이 K개 주어진다. 비용이 A인 간선을 탈 때 비용 B짜리 할인권을 쓰면 통행 비용이 max(0, A-B)가 된다. 할인권은 일회용이며, 간선 하나당 한 개만 쓸 수 있다. 모든 서로 다른 정점 쌍 (s, e)에 대해, s에서 e로 할인권을 적절히 쓰면서 갔을 때 최소 비용의 합을 구하라. (N ≤ 20)

시작 정점 하나당 (현재 위치, 현재까지 쓴 할인권 상태)의 정점 \( N 2^N \) 개짜리 그래프를 만들어서 다익스트라를 돌리면 답은 나오지만, 시간이 어림도 없다. 나는 그것보다 좋은 풀이를 계속 생각해도 모르겠어서 던졌는데, 다행히도(?) 나한테만 어려운 건 아니었나보다.

나중에 코드포스 어딘가에서 풀이를 읽었는데, (s, e)에 대한 답이 "할인권을 사용하여 만든 MST들 중 s, e를 모두 포함하면서 cost 합이 가장 작은 것"이라는 사실을 관찰하면 그냥 크루스칼 알고리즘을 \( 2^N \)번 돌려서 풀 수 있다고 한다. 이런 생각은 어떻게 하는 걸까?

Easy가 맞았으면 한 10등 했을 거 같은데, 틀려버려서 40등 언저리가 되었다. 다행히도 레이팅은 올랐다. 군대 가기 전에 레드를 찍고 가면 좋을 것 같다.