Problem Solving/ICPC13 ACM ICPC 2016 인터넷 예선 E번 1. 한 다각형 P(k)를 어떤 선분 L(k)로 치환하는데 L(k)를 구성하는 두 점은, P(k)를 구성하는 점들 중 원점으로부터 각도 최소인 점과 최대인 점2. L들을 각도순으로 본다.2-1. L에서 선분의 시작이면, 힙에다가 해당 선분을 넣음.2-2. L에서 선분의 끝이면, 힙에서 해당 선분을 삭제함. 2-2-1. 힙의 중간 부분에 있는 원소이면, 힙의 마지막 원소랑 해당 번째랑 자리를 바꾸고, 올릴 수 있는 만큼 올리고, 내려갈 수 있는 만큼 내려보냄. 2-2-2. 힙의 끝에 있는 원소이면, 힙의 사이즈만 줄이면 됨. 어떤 단위 각도 구간에 대해서 원점에 가까운 선분 L1은 원점에 보다 먼 선분 L2보다 이후의 구간에서 계속 더 가까운 성질을 이용하면 된다. 이 성질이 성립하는 이유는 교차하는 선분.. 2016. 10. 1. BAPC 2015 연습 결과 및 반성 대회 공식 스코어보드(BAPC 2015) 나는 A번과 K번을 풀고 Rikang형이랑 같이 J번을 해결했다. A는 Parametric Search + Greedy 였는데, Greedy 방법을 증명하고 코딩하느라 생각보다 시간이 오래 걸렸다. K번은 디오판토스 방정식을 활용하면 쉽게 풀 수 있는데, 계산식을 적다가 오타난 부분마저 그대로 옮겨 적었고 그걸 찾느라 많은 패널티를 받았다. 많이 아쉽다. 도중에 준식의 양변을 GCD로 나누는 부분이 있었는데, 결과는 변하지 않음에도 결과값에 GCD값을 곱하는 실수를 했다. GCD가 1이 아닌 예제만 하나 넣어보았어도 쉽게 찾을 수 있는 오류였다. J번은 해법 자체는 그렇게 어렵지 않은데, 최적화해서 TLE를 줄이는데 많은 공을 들였다. 어떻게든 해결할 수 있어서 .. 2016. 9. 24. 2016-2017 CT S03E01(BAPC 2010) 연습 결과 및 반성 대회 링크 : http://codeforces.com/gym/101078 결과H번을 붙잡지 말고, E번을 시도했어야 하는 점이 아쉬웠다.사실 제일 아쉬웠던 점은 7문제를 해결한 시점에서, 내가 B번을 풀 수 있음에도 불구하고 H번을 먼저 시도했다는 점이다. 이후에 잡다한 얘기를 하느라 집중력이 떨어졌고, 이게 전체적인 성적에 악영향을 미쳤던 것 같다. 창수가 B번 문제 내용을 제대로 이해하지 못했다는 사실을 인지하고 있었음에도 불구하고, 내가 H에 집중해서 풀어내고 창수가 B를 맞추면 최상위권으로 갈 수 있다는 판단이 너무 과욕이었던 것 같다.실제 대회에서는 이런 실수를 하지 않도록 이후에 있을 연습에서부터 참고하여야겠다. 2016. 9. 10. ACPC 2015 연습 결과 및 H. Capital City 풀이 대회 링크 : https://codeforces.com/gym/100676 결과 ACPC 2015 H. Capital City 문제가중치가 있는 무방향 그래프가 주어진다. 여기서 '사이클'이란, 어느 하나의 간선을 지워도 어떤 정점 u에서 정점 v로의 경로가 존재할 때에 u와 v는 같은 '사이클'에 속한다고 정의한다. 두 정점 사이의 거리는 다음과 같이 정의된다.1. 두 정점 u와 v가 같은 사이클 내에 속한다면, 둘 사이의 거리는 0이다.2. 두 정점 u와 v가 같은 사이클 내에 속하지 않는다면, 둘 사이의 거리는 둘 사이를 잇는 최단 경로의 길이이다.문제에서 요구하는 것은 다음과 같다. f(s)를 정점 s로부터 시작되는 최장 경로로 정의할 때, f(x)=min[f(s)]인 정점의 번호 x를 출력하는 .. 2016. 8. 30. 2016.6.14 http://codeforces.com/contest/504/problem/E : 답 정하고 점핑하면 Q log^2 N이라 TLE. 양 옆을 커팅해내고 LCA 하듯이 해서 Q log N.http://arc017.contest.atcoder.jp/tasks/arc017_4 : X(i+1)-X(i)로 Segment Tree. GCD(A, B, C) = GCD(A, |A-B|, |B-C|)http://arc048.contest.atcoder.jp/tasks/arc048_c : |∑| ^ [min(L) + (gcd(L(i)-min(L))+1)/2]http://arc049.contest.atcoder.jp/tasks/arc049_d : reverse 이용해서 seg tree하는 것까진 생각했는데 좀 더 생각해보아.. 2016. 6. 15. 이전 1 2 3 다음
