TopCoder SRM 422

http://www.topcoder.com/stat?c=round_overview&er=5&rd=13513

일요일 새벽 1시에 SRM 422가 열렸다.

요즘 ACM-ICPC를 앞두고 SRM에 참가자 수가 많이 늘어난 것 같다. 오늘도 우리나라에서 DIV1에 20명이 넘는 사람들이 참가했다.
문제는 비교적 쉬운 250과 비교적 어려운 500, 그리고 비교적 쉬운 1000이 출제되었는데, 500이 어려워서 1000을 푼 사람이 별로 없는것 같다. 나는 대회때 쉬운 250을 너무 늦게 푸는 바람에 500은 컴파일도 못해봤다.

250 - Prime Soccer

두 팀이 축구 경기를 하는데, 두 팀이 소수(Prime number)의 골을 넣을지 궁금하다. 경기는 90분 동안 지속되고 분석을 쉽게하기 위해 5분간격으로 경기를 분할한다. 매 5분마다 A팀이 골을 넣을 확률과 B팀이 골을 넣을 확률이 주어진다. 두 팀 중 적어도 한 팀이 소수만큼의 골을 넣을 확률을 계산하라. 한 팀이 5분 내에 두 골을 넣을 수는 없다.

Solving

90분을 5분 간격으로 자르면 총 18개의 인터벌이 있다. 이 중 소수개의 인터벌에서 골을 넣는 확률을 구하면 된다. 인터벌은 18개이고 따라서 한 팀은 최대 18개의 골을 넣을 수 있다. 18보다 작은 소수는 {2, 3, 5, 7, 11, 13, 17}의 7개가 있다.

A팀이 n개의 시간중에 r개의 시간에서 골을 넣을 확률은 다음과 같다

P(a): a가 인터벌내에 골을 넣을 확률
Pnr(a): a가 n개의 시간중에 r개의 시간에서 골을 넣을 확률
Pnr(a) = nCr * P(a)^r * (1-P(a))^(1-r)

위의 수식은 고등학교 수학에 나오는 건데 대회중에 nCr을 빼먹는 바람에 한참 돌았다;

A팀이 18개의 시간중에 소수개의 시간에서 골을 넣을 확률은 다음과 같다

Pp(a) = P18,2(a) + P18,3(a) + P18,5(a) + P18,7(a) + P18,11(a) + P18,13(a) + P18,17(a)

B의 확률도 같은 방법으로 구할 수 있다.

A와 B중 적어도 한팀이 소수개의 골을 넣을 확률은 다음과 같다

P(P(A)∪P(B)) = P(A) + P(B) - P(A)*P(B)

double Combination(double n, double r) { if (r == 0) return 1.0; else return n/r * Combination(n-1, r-1); } class PrimeSoccer { public: double getProbability(int skillOfTeamA, int skillOfTeamB) { double pa = skillOfTeamA / 100.0; double pb = skillOfTeamB / 100.0; int primes[] = {2, 3, 5, 7, 11, 13, 17}; double ans = 0; double ga = 0; double gb = 0; for (int i = 0; i < 7; i++) { double bin = Combination(18, primes[i]); ga += bin * pow(pa, primes[i]) * pow(1-pa, 18 - primes[i]); gb += bin * pow(pb, primes[i]) * pow(1-pb, 18 - primes[i]); } return ga + gb - ga*gb; } };

500 - Cave Passage

여행자들이 동굴을 탐험한다. 동굴의 지도는 하나밖에 없고 동굴속을 탐험할때는 반드시 지도를 지니고 있어야 한다.동굴의 중간에는 다리가 있는데 이 다리가 버틸수 있는 몸무게의 제한때문에 모든사람이 한 번에 이 다리를 지나지 못한다. 따라서 사람들은 좀 더 작은 그룹으로 나누어 동굴을 이동해야하는데, 자신외에 다른 사람과 같은 그룹이 된 경우 그룸내에 자신이 신뢰할 수 있는 사람이 적어도 한 명은 있어야한다. 그룹을 지어 이동할 때에는 그룹에 속한 사람들 중 가장 이동속도가 느린 사람과 같은 속도로 이동한다.
동굴을 여행하는 사람들의 몸무게와 동굴을 이동하는데 걸리는 시간이 주어지고 신뢰하는 사람들이 주어질 때, 모든 사람이 이 동굴을 빠져나가는데 걸리는 최소시간을 구하라. 불가능하면 -1을 리턴하라

Solving

최근에 본 500문제중에 가장 어려운 문제가 아닌가 생각한다.

사람의 수가 최대 13명이다. 동굴의 아직 지나지 않은 사람들의 조합으로 상태를 만들면 2^13 = 8192개의 상태가 존재한다. 동굴을 지나간 사람의 상태역시 8192개가 존재한다. 이동 가능한 그룹의 가지수역시 최대 8192개가 가능하다.

우선은 다리가 버틸수 있는 무게와 사람들 사이의 신뢰 관계를 이용해서 같이 이동 가능한 그룹을 구한다. 2^n의 모든 가능한 그룹을 검사하여 이 그룹에 속한 사람들의 무게의 합이 다리가 버틸 수 있는 무게 이하이고, 개개인 별로 그룹내에 적어도 믿을 수 있는 사람이 한 사람 이상 존재하면 이동 가능한 그룹이 된다.

동굴을 지나가기 전 상태의 집합을 Sa, 지난 후의 상태의 집합을 Sb라 하자. 모든 상태에 대해 도달가능한 최소시간을 저장하는 메모리를 마련해 각각 Ma, Mb라고 하고 'Ma[a] = Sa의 원소 a에 도달가능한 최소시간'으로 정의한다.

초기상태는 모든 사람이 동굴을 지나가지 않았고 걸린 시간이 0인 상태이다. 이 상태에서 이동 가능한 그룹을 찾아 Sb로 상태를 전이시킨다. 각각의 이동가능한 그룹마다 이동에 걸리는 시간이 다르기 때문에 가장 시간이 적게 걸린 상태를 우선적으로 선택하여 상태를 계속 전이해 나간다. 이 때 Ma와 Mb에 도달 가능한 시간의 최소를 갱신하면서 이 값보다 큰 상태가 발생하면 이 상태는 무시한다.

우선순위큐를 이용하여 알고리즘을 효율적으로 구현할 수 있다.

int T[10000]; int Mem[2][10000]; struct State { int state; int time; int side; State(int s, int t, int si) {state = s; time =t; side = si;} bool operator < (const State& rhs) const { return time > rhs.time; } }; class CavePassage { public: int minimalTime(vector <int> weights, vector <int> times, vector <string> table, int strenth) { int i,j,k; int n = weights.size(); int m = 1<<n; memset(T, 0xFF, sizeof(T)); memset(Mem, 0xFF, sizeof(Mem)); for (i = 0; i < m; i++) { bool possible = true; int weight = 0; int time = 0; for (j = 0; j < n; j++) { if (i & (1<<j)) { bool trust = false; int no = 0; for (k = 0; k < n; k++) { if (j == k) continue; if (i & (1<<k)) { if (table[j][k] == 'Y') { trust = true; break; } else no++; } } if (no == 0) trust = true; if (!trust) { possible = false; break; } weight += weights[j]; time = MAX(time, times[j]); } } if (possible && weight <= strenth) { T[i] = time; } } T[0] = -1; priority_queue<State> que; que.push(State(m-1, 0, 0)); for (i = 0; i < 10000; i++) Mem[0][i] = Mem[1][i] = INT_MAX; Mem[0][m-1] = 0; while (!que.empty()) { State cur = que.top(); que.pop(); if (cur.time > Mem[cur.side][cur.state]) continue; for (i = cur.state; i > 0; i = (i-1) & cur.state) { if (T[i] != -1) { State next((~cur.state & (m-1)) | i, cur.time + T[i], 1-cur.side); if (Mem[next.side][next.state] > next.time) { Mem[next.side][next.state] = next.time; que.push(next); } } } } if (Mem[1][m-1] == INT_MAX) return -1; return Mem[1][m-1]; } };

1000 - Workers On Plane

금과 은이 매장된 땅을 사서 사람들을 고용해 일을 시키려 한다. 지도가 주어지고 금과 은이 매장된 좌표와 일터의 좌표가 주어진다. 일꾼 한 사람마다 금광, 은광, 일터를 하나씩 할당하는데 일터에서 금광까지의 거리와 일터에서 은광까지의 거리가 K이하여야 한다. 지도에서 금광은 'G' 은광은 'S' 일터는'W'로 표시되며 바위는 'X'로 표시된다. 일꾼은 오직 '.'로 표시된 잔디를 통해서만 이동할 수 있고 동서남북 네 방향으로만 이동할 수 있다. 하나의 금광, 은광, 일터에는 두 명 이상의 일꾼을 할당할 수 없다.
지도가 주어졌을 때, 고용할 수 있는 최대한의 일꾼의 수를 구하여라.

Solving

max flow 문제이다. 우선 K를 기준으로 W에서 도달가능한 G와 S를 찾아 그래프를 만든다. 플로우 네트워크를 구성하기 위해 Start -> Gold -> Workplace -> Silver -> Sink 형태의 그래프를 구성한다. 즉 하나의 Start노드를 만들고 이 노드에서 모든 G까지 연결을 한다. 그리고 모든 S에서 Sink노드로 연결을 한다. 

G, W, S에 한 명의 일꾼밖에 할당을 못하므로 Vertex Connectivity를 구해야 한다. Vertex Connectivity는 최대플로우를 이용하여 구할 수 있는데 maxflow-mincut 이론에 따르면 최대플로우는 Egde Connectivity와 같다. Vetex Connectivity는 각 노드를 둘로 나누어 이 사이에 capacity가 1인 에지를 추가한 다음 Egde Connectivity를 구하면 된다.

const int INF = INT_MAX; template<class T> class FlowGraph { public: enum {WHITE,GRAY,BLACK}; vector<vector<T> > flow, cap, resCap; vector<int> parent, color, que; vector<T> minCap; int size, source, sink; T maxFlow; T MaxFlow_EK(const vector<vector<T> >& _cap, int _source, int _sink) { size = _cap.size(); cap = resCap = _cap; flow.assign(size, vector<T>(size, 0)); minCap.assign(size, 0); parent.assign(size, 0); color.assign(size, 0); que.assign(size, 0); source = _source; sink = _sink; maxFlow = 0; while (BFS_EK(source)) { maxFlow += minCap[sink]; int u, v = sink; while (v != source) { u = parent[v]; flow[u][v] += minCap[sink]; flow[v][u] -= minCap[sink]; resCap[u][v] -= minCap[sink]; resCap[v][u] += minCap[sink]; v = u; } } return maxFlow; } // BFS in O(V²) bool BFS_EK(int source) { for (int i = 0; i < size; i++) { color[i] = WHITE; minCap[i] = INF; } int first = 0; int last = 0; que[last++] = source; color[source] = GRAY; while (first != last) { int v = que[first++]; for (int u = 0; u < size; u++) { if (color[u] == WHITE && resCap[v][u] > 0) { minCap[u] = MIN(minCap[v], resCap[v][u]); parent[u] = v; color[u] = GRAY; if (u == sink) return true; que[last++] = u; } } } return false; } T VertexConnectivity(const vector<vector<T> >& _G, int _source, int _sink) { int i, j, k; int n = _G.size(); vector<vector<T> > cap(n*2+2, vector<T>(n*2+2, 0)); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { if (_G[i][j] == 1) cap[i+n][j] = INF; } cap[i][i+n] = 1; } cap[n*2][_source+n] = INF; cap[_sink][n*2+1] = INF; return MaxFlow_EK(cap, n*2, n*2+1); } }; vector<vector<int> > G; vector<string> F; bool visit[31][31]; int N, M, S, K; void BFS(int y, int x, char dest) { memset(visit, 0x00, sizeof(visit)); queue<pair<int, pair<int, int> > > que; que.push(make_pair(0, make_pair(y, x))); int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; while (!que.empty()) { pair<int, pair<int, int> > cur = que.front(); que.pop(); int cy = cur.second.first; int cx = cur.second.second; int depth = cur.first; if (cx < 0 || cx >= M || cy < 0 || cy >= N) continue; if (depth > K) continue; if (visit[cy][cx] == true) continue; visit[cy][cx] = true; if (F[cy][cx] == dest) { G[y*M+x][cy*M+cx] = 1; continue; } if (depth && F[cy][cx] != '.') continue; for (int k = 0; k < 4; k ++) que.push(make_pair(depth+1, make_pair(cy + dy[k], cx + dx[k]))); } } class WorkersOnPlane { public: int howMany(vector <string> field, int kk) { int i,j,k; N = field.size(); M = field[0].size(); S = N*M; K = kk; F = field; G.assign(S+2, vector<int>(S+2, 0)); for (i = 0; i < N; i++) { for (j = 0; j < M; j++) { char a = F[i][j]; if (a == 'G') { BFS(i, j, 'W'); G[S][i*M+j] = 1; } if (a == 'W') { BFS(i, j, 'S'); } if (a == 'S') { G[i*M+j][S+1] = 1; } } } FlowGraph<int> fg; return fg.VertexConnectivity(G, S, S+1); return 0; } };