탑코더 로그 보관소

250 - AvoidingProduct. /again 당시의 챌린지 포인트는 n 을 넘어가는 수가 답에 들어갈 수 있다는 것. prod > n break 최적화 걸어서 가뿐히 시간 안에 나옴.
bool seen[1100]; struct AvoidingProduct { vector <int> getTriple(vector <int> a, int n) { REP(i,a.sz) seen[a[i]] = true; ll bestDiff = 1157625001; vector<int> ret(3); FOR(x,1,n+51) if(!seen[x]) FOR(y,x,n+51) if(!seen[y]) FOR(z,y,n+51) if(!seen[z]) { ll prod = ll(x*y)*z; ll diff = abs(n - prod); if(diff < bestDiff) { ret[0] = x; ret[1] = y; ret[2] = z; bestDiff = diff; } if(prod > n) break; } return ret; } };
500 - BinarySum ; 3개의 n비트 정수 a, b, c 가 주어질 때, 이들의 비트 순서를 적절히 바꿔서 a + b = c 를 홀드하는 최소의 c 찾기. DP 자체는 트리비얼했는데, a 와 b 에 각각 남아 있는 1의 개수를 쓰는 변수를 해당 비트에 1 이 있는가로 헷갈려서 조건 문 잘못 썼다가 고생..
const int inf = 2147483647; int cache[31][31][31][31][2]; struct BinarySum { int n; int go(int here, int aOnes, int bOnes, int cOnes, int shouldCarry) { if(here == n) return (aOnes + bOnes + cOnes + shouldCarry == 0 ? 0 : inf); int& ret = cache[here][aOnes][bOnes][cOnes][shouldCarry]; if(ret != -1) return ret; ret = inf; REP(bits,8) { int ao = aOnes, bo = bOnes, co = cOnes, sc = 0; int ones = 0; if(bits & 1) { --ao; ++ones; } if(bits & 2) { --bo; ++ones; } if(bits & 4) { sc = 1; ++ones; } int add = 0; if(ones % 2) { --co; add = (1 << (n-1-here)); } if(ones < 2 && shouldCarry) continue; if(ones >= 2 && !shouldCarry) continue; if(ao < 0 || bo < 0 || co < 0) continue; int cand = go(here+1, ao, bo, co, sc); if(cand == inf) continue; ret <?= cand + add; } return ret; } int rearrange(int a, int b, int c) { n = 0; int ai = 0, bi = 0, ci = 0; while(a || b || c) { if(a % 2) ++ai; if(b % 2) ++bi; if(c % 2) ++ci; a /= 2; b /= 2; c /= 2; ++n; } CLEAR(cache,-1); int ret = go(0, ai, bi, ci, 0); if(ret == inf) return -1; return ret; } };

1000 - DanceParty. k명의 안 좋아하는 사람이랑도 춤 출수 있다는 조건을 빼도 살짝 어렵다. 방법은, 싱크 -> 슈퍼싱크의 캐퍼시티를 1로 놨다가 라운드마다 1씩 늘려가면서 이분매칭 하는 것. 이렇게 하면 전 라운드에서 춤췄던거 바꿔서 오버라이딩하면서도, 한 라운드에 두 사람이랑 한꺼번에 춤추는 걸 막을 수 있음. 증명을 포멀하게 하지 않았는데, 망설이다가 그냥 갔다. k 에 대한 것은 별개의 노드를 추가해서 쉽게 해결.

const int MAXV = 220; struct NetworkFlow { int flow[MAXV][MAXV], cap[MAXV][MAXV], totalFlow, V; NetworkFlow(int V): V(V) { CLEAR(cap,0); CLEAR(flow,0);totalFlow = 0; } void addEdge(int a, int b, int c) { cap[a][b] += c; } void push(int a, int b, int c) { flow[a][b] += c; flow[b][a] = - flow[a][b]; } int res(int a, int b) { return cap[a][b] - flow[a][b]; } int pushFlow(int source = 0, int sink = 1) { vector<int> pred(V, -1); queue<int> q; q.push(source); pred[source] = source; while(!q.empty() && pred[sink] == -1) { int u = q.front(); q.pop(); for(int v = 0; v < V; ++v) if(res(u,v) > 0 && pred[v] == -1) { pred[v] = u; q.push(v); } } if(pred[sink] == -1) return 0; int h, amt = 987654321; h = sink; while(pred[h] != h) { amt <?= res(pred[h], h); h = pred[h]; } h = sink; while(pred[h] != h) { push(pred[h], h, amt); h = pred[h]; } printf("\n"); totalFlow += amt; return amt; } }; struct DancingParty { int maxDances(vector <string> likes, int k) { int n = likes.sz; int SNK = 4*n; NetworkFlow flow(n*4 + 1); for(int i = 0; i < n; ++i) { flow.addEdge(i, n+i, k); flow.addEdge(2*n+i, 3*n+i, k); flow.addEdge(3*n+i, SNK, 1); for(int j = 0; j < n; ++j) if(likes[i][j] == 'Y') flow.addEdge(i, 3*n+j, 1); else flow.addEdge(n+i, 2*n+j, 1); } printf("oops\n"); int rounds = 0; while(true) { bool ok = true; for(int i = 0; i < n; ++i) { int amt = flow.pushFlow(i, SNK); if(amt == 0) { ok = false; break; } } if(!ok) break; ++rounds; if(rounds == n) break; for(int i = 0; i < n; ++i) flow.addEdge(3*n+i, SNK, 1); } return rounds; } };

250 - AvoidingProduct
public class AvoidingProduct { public int[] getTriple(int[] a, int n) { boolean[] hit = new boolean[1051]; long bestDiff = Long.MAX_VALUE; int[] ret = new int[3]; for(int i = 0; i < a.length; ++i) hit[a[i]] = true; for(int x = 1; x <= n+50; ++x) if(!hit[x]) for(int y = x; y <= n+50; ++y) if(!hit[y]) for(int z = y; z <= n+50; ++z) if(!hit[z]) { long prod = (long)(x*y) * z; long diff = Math.abs(prod - n); if(diff < bestDiff) { bestDiff = diff; ret[0] = x; ret[1] = y; ret[2] = z; } if(prod > n) break; } return ret; } }

500 - BinarySum ; memoization pattern 을 어떻게 하면 빠르게 짤 수 있을까?
public class BinarySum { int n; int[][][][][] cache; boolean[][][][][] done; int go(int here, int ao, int bo, int co, int shouldCarry) { if(here == n) { if(ao == 0 && bo == 0 && co == 0 && shouldCarry == 0) return 0; return Integer.MAX_VALUE; } if(done[here][ao][bo][co][shouldCarry]) return cache[here][ao][bo][co][shouldCarry]; int ret = Integer.MAX_VALUE; for(int bits = 0; bits < 8; ++bits) { int ones = 0; int nao = ao, nbo = bo, nco = co, nsc = 0; if((bits & 1) > 0) { ++ones; --nao; } if((bits & 2) > 0) { ++ones; --nbo; } if((bits & 4) > 0) { ++ones; nsc = 1; } int add = 0; if(ones % 2 > 0) { --nco; add = (1 << (n-1-here)); } if(ones >= 2 && shouldCarry == 0) continue; if(ones < 2 && shouldCarry == 1) continue; if(nao < 0 || nbo < 0 || nco < 0) continue; int cand = go(here+1, nao, nbo, nco, nsc); if(cand == Integer.MAX_VALUE) continue; ret = min(ret, cand + add); } done[here][ao][bo][co][shouldCarry] = true; cache[here][ao][bo][co][shouldCarry] = ret; return ret; } public int rearrange(int a, int b, int c) { n = 0; int ao = 0, bo = 0, co = 0; while(a > 0 || b > 0 || c > 0) { if(a % 2 > 0) ++ao; if(b % 2 > 0) ++bo; if(c % 2 > 0) ++co; a /= 2; b /= 2; c /= 2; ++n; } cache = new int[32][32][32][32][2]; done = new boolean[32][32][32][32][2]; int ret = go(0, ao, bo, co, 0); return ret == Integer.MAX_VALUE ? -1 : ret; } }


1000 - DancingParty; NetworkFlow 클래스 자바로 재구현 ㅋㅋ
class NetworkFlow { private int v, totalFlow; private int[][] flow, cap; public NetworkFlow(int n) { v = n; flow = new int[v][v]; cap = new int[v][v]; for(int i = 0; i < v; ++i) for(int j = 0; j < v; ++j) flow[i][j] = cap[i][j] = 0; } public void addEdge(int a, int b, int capacity) { cap[a][b] += capacity; } private int residual(int a, int b) { return cap[a][b] - flow[a][b]; } private void push(int a, int b, int amt) { flow[a][b] += amt; flow[b][a] = -flow[a][b]; } public int pushFlow(int source, int sink) { int[] pred = new int[v]; for(int i = 0; i < v; ++i) pred[i] = -1; LinkedList<Integer> q = new LinkedList<Integer>(); q.addLast(source); pred[source] = source; while(!q.isEmpty()) { int here = q.removeFirst(); for(int there = 0; there < v; ++there) { if(residual(here, there) > 0 && pred[there] == -1) { pred[there] = here; q.addLast(there); } } } if(pred[sink] == -1) return 0; int h, amt = Integer.MAX_VALUE; h = sink; while(pred[h] != h) { amt = min(amt, residual(pred[h], h)); h = pred[h]; } h = sink; while(pred[h] != h) { push(pred[h], h, amt); h = pred[h]; } totalFlow += amt; return amt; } } public class DancingParty { public int maxDances(String[] likes, int k) { int n = likes.length; NetworkFlow flow = new NetworkFlow(4*n+1); for(int i = 0; i < n; ++i) { flow.addEdge(i, n+i, k); flow.addEdge(n+n+i, n+n+n+i, k); for(int j = 0; j < n; ++j) if(likes[i].charAt(j) == 'Y') flow.addEdge(i, n+n+n+j, 1); else flow.addEdge(n+i, n+n+j, 1); } int ret = 0; int SINK = 4*n; for(int rounds = 1; rounds <= n; ++rounds) { boolean ok = true; for(int i = 0; i < n; ++i) flow.addEdge(n+n+n+i, SINK, 1); for(int i = 0; i < n; ++i) if(flow.pushFlow(i, SINK) == 0) { ok = false; break; } if(ok) ret = rounds; else break; } return ret; } }

250 Truckload: /simple
메소드 내용은 C++ 에 그대로 붙여도 돌아가겠다. -_-;

public class Truckloads { public int numTrucks(int numCrates, int loadSize) { if(numCrates <= loadSize) return 1; return numTrucks(numCrates / 2, loadSize) + numTrucks(numCrates / 2 + numCrates % 2, loadSize); } }

500 Measures: /implement
그냥 문제 내용에 따라서 주의깊게 구현하면 되는 문제. nested loop 로 구리게 구현했다.

public class Measures { public int beatsPerM(int[] loudness) { for(int bpm = 2; bpm <= 10; ++bpm) { if(bpm > loudness.length) break; for(int begin = 0; begin < bpm && begin + bpm <= loudness.length; ++begin) { int measures = 0, fulfilled = 0; for(int measureBegin = begin; measureBegin + bpm <= loudness.length; measureBegin += bpm) { boolean ok = true; for(int i = 0; i < bpm; ++i) if(loudness[measureBegin+i] > loudness[measureBegin]) ok = false; if(ok) ++fulfilled; ++measures; } if(measures == 0) continue; if(measures * 8 <= fulfilled * 10) return bpm; } } return -1; } }


1000 SnakeCount ; 2차원 1/0 배열에서 1 의 나열로 된 뱀을 세는 문제. 다양한 예외 조건들이 있다. 어렵게 풀고 싶은 유혹을 뿌리치고 대충 일반화한후에 직감을 믿고 고고싱 -ㅅ-


public class SnakeCount { int w, h; int[][] map; String[] image; final static int dx[] = { 1, -1, 0, 0, -1, 1, 1, -1 }; final static int dy[] = { 0, 0, 1, -1, -1, -1, 1, 1 }; private void dfs(int y, int x, int with) { if(y < 0 || x < 0 || y >= h || x >= w) return; if(map[y][x] != -1) return; if(image[y].charAt(x) != '1') return; map[y][x] = with; for(int k = 0; k < 4; ++k) dfs(y + dy[k], x + dx[k], with); } public int number(String[] image) { this.image = image; w = image[0].length(); h = image.length; map = new int[h][w]; for(int i = 0; i < h; ++i) for(int j = 0; j < w; ++j) map[i][j] = -1; int regions = 0; for(int i = 0; i < h; ++i) for(int j = 0; j < w; ++j) if(image[i].charAt(j) == '1' && map[i][j] == -1) dfs(i, j, regions++); boolean[] canBeSnake = new boolean[regions]; int[] seenOnes = new int[regions]; int[] pixels = new int[regions]; for(int i = 0; i < regions; ++i) { canBeSnake[i] = true; seenOnes[i] = 0; pixels[i] = 0; } for(int i = 0; i < h; ++i) for(int j = 0; j < w; ++j) { if(map[i][j] == -1) continue; int sn = map[i][j]; int connected = 0; pixels[sn]++; for(int k = 0; k < 8; ++k) { int ni = i + dy[k], nj = j + dx[k]; if(ni < 0 || nj < 0 || ni >= h || nj >= w) continue; if(image[ni].charAt(nj) == '0') continue; if(k < 4) ++connected; if(map[ni][nj] != sn) canBeSnake[sn] = false; } if(connected > 2) canBeSnake[sn] = false; if(connected == 1) seenOnes[sn]++; } int ret = 0; for(int i = 0; i < regions; ++i) if(canBeSnake[i] && seenOnes[i] == 2 && pixels[i] >= 3 && pixels[i] <= 20) ++ret; return ret; } }

* 문제 해법

 동적 계획법으로 해결할 수 있는 문제입니다만, 문제의 트릭을 빨리 파악하신다면 좀 더 간단한 방법으로도 풀 수 있는 문제였습니다.

 이 문제에서의 핵심 포인트는 "토끼는 페이크다"라는 점입니다. 토끼는 아무리 많아도 괴물과 당신을 해칠 수 없습니다. (물론 서로 해칠수도 없지만요) 당신이 토끼를 만나서 토끼를 죽이던 죽이지 않던 당신이 살아남는 확률은 monster에만 영향을 받는다는 점입니다.

 우선 M이 0인 경우 살아남을 확률은 1.0이라는 것을 알 수 있습니다. 또한 M이 1인 경우 당신은 살아남지 못한다(확률 = 0.0)는 것을 알 수 있습니다.

 M이 1보다 큰 경우, 임의로 두 유닛을 골랐을 때, 몬스터만 두 마리 골라질 확률을 구해봅시다. 당신과 M마리의 몬스터를 선택하는 경우의 수는 (M + 1) * M / 2가 됩니다. 여기에서 몬스터만 두 마리 골라지는 경우의 수는 M * (M - 1) / 2가 되지요. 몬스터와 당신이 선택되는 경우의 수는 M 가지가 되는 것이고요.

 table(i) = i마리의 몬스터가 있을 때 당신이 살아남을 확률이라고 정의합시다. 그러면 당신이 살아남을 확률

 table(i) = P{choose 2 monsters} * table(i - 2) + P{choost 1 monster and you} * 0.0

 가 됩니다. 좀 더 정리하면 table(i) = (M - 1) / (M + 1) * table(i - 2) 가 되겠네요. 위의 점화식을 사용하면 쉽게 답을 구할 수 있습니다. 또한 위의 식을 풀어서 간단하게 나타내면 아래의 소스처럼 표현이 가능하지요.

struct MonstersAndBunnies { double survivalProbability(int M, int B) { if (M % 2 == 0) return 1.0 / (M + 1); return 0.0; } };

 물론 위의 방식대로 구현하지 않고, 2차원 동적 계획법으로도 풀 수 있습니다. (하지만 소스가 좀 더 길어지겠지요.)

 p.s) 제가 이 문제에서 챌린지로 275점을 획득하였는데, 확률 계산을 하는 과정에서 B가 영향을 주는 소스코드들에 {998, 999}라는 데이터를 넣어주었습니다 :)