TopCoder SRM 425

SRM 425 Division 1은 250과 500점에 Brute Force 문제가 나왔고 1000에 그래프 이론과 수학적 사고력을 필요로 하는 문제가 출제되었다.

250은 비교적 어려운 느낌이었지만 250점 배점이 적당해 보였고 500점은 비교적 쉽게 느껴졌다. 1000점짜리는 문제의 난이도도 안드로로 달리면서 동시에 시스템 테스트 데이터에 버그가 있는 바람에 매치가 끝나고 한참 후에야 버그를 잡고 리저지를 하는 해프닝이 벌어졌다. 루머에 의하면 신 Petr님께서 테스트 데이터의 버그를 찾아 자신이 왜 petr인가를 보여줬다고 하는데 믿거나 말거나이다.

매치이전 레이팅 2928를 기록하던 JongMan님은 매치 시작전부터 타겟의 가능성이 점쳐져 왔다. 매치 시작후 내가 화장실을 갔다온 사이 이미 250을 패스티스트로 풀어버리면서 내가 250을 채 풀기도 전에 500까지 풀어내면서 타겟을 향해 점점 나아갔다. 결국 이번 매치에서 7등을 하며 우리나라 최초의 타겟이 탄생이 기대되었는데 결과는 2991점으로 타겟이 9점이 모자랐다.

나는 500에서 아주 캐초보적이면서 치명적인 실수를 범하며 매치 종료 30초를 남기고 통한의 리서밋을 하는 바람에 157점에 머물러 레이팅 19점 상승에 만족해야했다.


250 - Crazy Bot

통제불능의 로봇이 평면상에 있다. 이 로봇은 랜덤하게 n번 이동한다. 각 이동은 동서남북 중 한 방향으로 움직인다. 로봇에 한번 들렀던 곳을 다시 지나가지 않는 경로를 simple path라고 한다. n과 로봇이 동서남북으로 움직일 확률이 각각 주어졌을 때 이 로봇의 움직임이 simple path가 될 확률을 구하여라. 1 <= n <= 14

solving

n의 범위가 14까지 주어지므로 모든 경우의 수를 따져 문제를 풀 수 있다.

로봇이 움직일 수 있는 방향은 동,서,남,북 중 한 방향이고 n이 14인 경우 로봇이 취하는 움직임의 횟수는 13회 이다. 따라서 최악의 경우 모든 경우를 따질때 필요한 상태공간의 크기는 최대 4^13으로 7천만 보다 작다!!! 탑코더 저지 PC의 뛰어난 성능과 2초의 시간제한을 생각해보면 충분히 해볼만하다.

이동한 결과가 simple path이어야 하므로 현재 이동이 Simple Path를 만족하는 경우에 depth가 n이 될때까지 백트레킹을 진행한다. 모든 가능한 Simple Path의 확률을 더하면 답이 된다.
double ans; bool visit[100][100]; double pp[4]; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; void go(int n, int y, int x, double p) { if (n == 0) { ans += p; return; } if (p == 0) return; for (int i = 0; i < 4; i++) { int ny = y + dy[i]; int nx = x + dx[i]; if (visit[ny][nx] == false) { visit[ny][nx] = true; go(n-1, ny, nx, p*pp[i]); visit[ny][nx] = false; } } } class CrazyBot { public: double getProbability(int n, int east, int west, int south, int north) { int i,j,k; Mem0(visit); ans = 0; pp[0] = east/100.0; pp[1] = south/100.0; pp[2] = west/100.0; pp[3] = north/100.0; visit[50][50] = true; go(n, 50, 50, 1.0); return ans; } };

500 - Pieces Mover

5x5 보드위에 최대 5개의 말이 놓여있다. 각 말은 한번에 동서남북 네방향 중 한 방향으로 한 칸 이동할 수 있다. 5x5보드가 주어졌을 때 모든 말이 하나의 connected component를 이루기 위해 필요한 최소 이동 횟수를 구하라

solving

언뜻보기에 상당히 난이도가 있어보이지만 시간복잡도 분석을 잘 해보면 이 문제 역시 brute force로 풀 수 있다는 것을 알 수 있다.

5x5보드위에 5개의 말을 놓을 수 있는 경우의 수는 25C5 = 약 5만 정도가 된다. 각 경우에 대해서 하나의 connected component로 구성되어 있는지 구하는 것은 최악의 경우 O(25)정도가 된다. 하나의 connected component라는 것을 확인 하였다면 원래의 모양에서 connected component를 구성하는 모양으로 변이하기 위한 최소 이동 거리를 구해야 하는데 이 또한 모든 경우를 따져 최소를 구하면 된다. 이때 경우의 수는 5!이다.

우선 5개의 말이 만들 수 있는 모든 가능한 모양과 이 모양이 커넥티드 컴포넌트인지 구하는데 필요한 연산은 O(5만 * 25) = O(125만) 정도가 되고 그 중 하나의 커넥티드 컴포넌트로 구성된 경우에만 5! = 120 의 추가적인 연산이 필요하다.

언뜻봐도 2초의 시간이면 넉넉할 것 같다 코딩을 하자.
vector<pair<int, int> > BA, BB; int B[30]; int N; bool visit[5][5]; int cc = 0; int ans = 987654321; void test() { int dist = 0; for (int i = 0, j = 0; i <25; i++) if (B[i] == 1) BB[j++] = make_pair(i/5, i%5); do { dist = 0; for (int i = 0; i < N; i++) dist += abs(BA[i].first - BB[i].first) + abs(BA[i].second - BB[i].second); if (dist < ans) ans = dist; } while (next_permutation(BB.begin(), BB.end())); } void connected(int y, int x) { if (y < 0 || y >= 5 || x < 0 || x >= 5) return; if (visit[y][x] == true) return; visit[y][x] = true; int k = y*5 + x; if (B[k] == 1) { cc++; connected(y, x+1); connected(y, x-1); connected(y+1, x); connected(y-1, x); } } void candi() { for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { int k = i*5+j; if (B[k] == 1) { Mem0(visit); cc = 0; connected(i, j); if (cc == N) { test(); } return; } } } } void go(int n, int rem) { if (rem == 0) { candi(); return; } if (n == 25) return; go(n+1, rem); B[n] = 1; go(n+1, rem-1); B[n] = 0; } class PiecesMover { public: int getMinimumMoves(vector <string> board) { int i,j,k; N = 0; BA.clear(); for (i = 0; i < 5; i++) for (j = 0; j < 5; j++) if (board[i][j] == '*') { N++; BA.push_back(make_pair(i, j)); } BB.assign(N, make_pair(0, 0)); ans = 987654321; go(0, N); return ans; } };

1000 - Roads of Kingdom

Petr와 상의하세요