Topcoder SRM 667 Round1 div2
1.
입력으로 점 A와 B가 주어진다. 점 A,B와 같지 않으면서 유클리드 거리 dist(A,B)>dist(B.C)인 C를 찾는 문제 인데 C가 있을 수 있는 범위가 -100<=x,y<=100이라는 조건이 있어서 그냥 200 * 200으로 돌려 보면 된다.
2.
길이 m인 이진수가 n개 주어진다. 이제 이 이진수들을 재배치 하는데 재배치 순서에 따라 그 이진수들의 cost가 결정 된다. cost는 이진수들을 순서대로 봤을때 그 이진수에서 이전에 등장하지 않은 1의 위치의 갯수의 제곱이다. 즉, 110 -> 100 이라면 110에서 처음 등장한 1의 위치 갯수는 2개 이므로 +4, 100에서 제일 왼쪽 1은 110에서 등장하므로 +0 전체는 4. 이런 식이다. 0<n,m<=20이므로 비트마스트 DP를 사용하면 O(m*2^n)의 시간복잡도로 해결 할 수 있다. 많은 사람들이 그리디로 접근해서 틀렸다.
3.
풀어보고 올리겠다.
입력으로 점 A와 B가 주어진다. 점 A,B와 같지 않으면서 유클리드 거리 dist(A,B)>dist(B.C)인 C를 찾는 문제 인데 C가 있을 수 있는 범위가 -100<=x,y<=100이라는 조건이 있어서 그냥 200 * 200으로 돌려 보면 된다.
2.
길이 m인 이진수가 n개 주어진다. 이제 이 이진수들을 재배치 하는데 재배치 순서에 따라 그 이진수들의 cost가 결정 된다. cost는 이진수들을 순서대로 봤을때 그 이진수에서 이전에 등장하지 않은 1의 위치의 갯수의 제곱이다. 즉, 110 -> 100 이라면 110에서 처음 등장한 1의 위치 갯수는 2개 이므로 +4, 100에서 제일 왼쪽 1은 110에서 등장하므로 +0 전체는 4. 이런 식이다. 0<n,m<=20이므로 비트마스트 DP를 사용하면 O(m*2^n)의 시간복잡도로 해결 할 수 있다. 많은 사람들이 그리디로 접근해서 틀렸다.
3.
풀어보고 올리겠다.
댓글
댓글 쓰기