Problem Solving102 Google Codejam Round 1A 2016 Problem A. The Last Word 각 단계마다 그리디하게 앞에 붙이는 것이 좋은지 뒤에 붙이는 것이 좋은지 선택. char S[1005]; int main() { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); int runs = 1; int T; for (scanf("%d", &T); T--;) { scanf("%s", S); string a = ""; for (int i = 0; S[i]; i++) { string b = a + S[i]; string c = S[i] + a; if (b > c) a = b; else a = c; } printf("Case #%d: %s\n", runs++, a.c_str()); }.. 2016. 4. 16. 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. 이전 1 ··· 13 14 15 16 17 18 19 ··· 21 다음
