전체 글110 Indeterminate Value 실수 연산을 하는 경우, 값들의 대소관계를 판별하기 위해 매우 작은 수인 epsilon 개념을 넣어서 >, y, x < y, x == y); } 2016. 4. 7. BAPC 2005 Preliminaries D - Mandalas Problem Link500개 이하의 원들이 주어지면, 몇 개의 영역으로 나뉘는지를 묻는 문제이다.오일러의 정리에 따르면 V - E + F = 2이고, "위키피디아 - Planar graphs 부분"을 보면 평면그래프에서는 V - E + F - C = 1이라고 한다.따라서 원들의 교차점을 V라 보고, E는 원들로 인해서 나누어지는 호들의 개수, F는 우리가 구하고자 하는 영역의 개수, C는 원들의 component 개수라 보고 풀면 된다.두 원의 교차점들 중, 같은 점들에 대한 중복처리 등을 신경써서 해야한다. epsilon값을 너무 작게 주어도 안되고, 적당히 1e-5 정도로 주어야 맞게 판정된다. 2016. 4. 5. Lowest Common Ancestor(최소 공통 조상) 1. 두 노드 a와 b에 대해, 서로 높이가 다르다면 높이를 맞추어줌. 2. 2의 거듭제곱 꼴로 높이를 낮추다가 공통 조상이 없어지는 곳으로 이동. int lca(int a, int b, int K) { if (a == b) return a; //a = b // LCA는 a나 b보다 최소 높이 1보다 위에 있음. for (int i = K; i >= 0; i--) { if (parent[i][a] != parent[i][b]) return lca(parent[i][a], parent[i][b], i); //분기되는 최초의 지점으로 이동 } return parent[0][a]; // LCA는 바로 위의 조상. } 3. a와 b가 같아지거나 LCA를 찾기 이전까지 계속 '2.'를 반복. 2016. 3. 31. 627A - XOR Equation 8VC Venture Cup 2016 — Final Round A번 문제이다. (Div.1 Edition B번, Div.2 Edition C번)별로 어렵지 않은 문제인데 한참동안 해매어서 정리.두 양의 정수 a와 b의 합이 s이고 XOR한 결과가 x일 때에, 가능한 (a, b) 순서쌍의 개수를 구하는 것이 문제이다.접근법 1)a+b = s, a^b = xb = (s-a)a^(s-a) = xs-a = a^x. 양번에 a를 XOR하면 a^(s-a) = a^x여기서 잘못됨을 깨닫고 다른 관계식을 시도함.접근법 2)a^b = a+b - 2(a&b)XOR라는 연산이 두 bit가 다르면 1이기 때문에 덧셈에서 자리올림을 빼면 그 결과가 XOR와 같다는 식.정리하면 (s-x)/2 = a&b여기서 매 digit마다 (.. 2016. 3. 10. Codeforces Round #192 (Div. 1) A : 가로줄, 세로줄을 이분그래프로 모델링하고, 가로줄에 유량 n, 세로줄에 1만큼 준 다음에 max flow 돌려본다. 답이 안 나오면, 세로줄에 유량 n, 가로줄에 1만큼 준 다음에 max flow 돌려본다. 이래도 답 안 나오면 -1.B : 시작점에서 BFS, 도착점에서 BFSC : n이 7 이하면 모든 간선에 대해서 골라보고 아니면 1~n까지의 수열을 계속 랜덤 셔플해보면서 인접한 정점들에 대해 간선을 줌. 할 수 있는 동안 해보고 안되면 불가능 했더니 맞음. 2016. 3. 8. 이전 1 ··· 14 15 16 17 18 19 20 ··· 22 다음
