(5.14 첫 작성) 대회때 100 / 26 / 100점을 받았다.http://apio2016.org/results/ Problem 1. Boat처음 봤을 때 어려워 보이지는 않았고, 어쨌든 대회 시간 안에 풀수 있을 것이라 생각했다. 실제로도 아주 어려운 문제는 아니었지만, 완전히 잘못된 풀이에 낚여서 1시간 이상을 허비한 게 아직도 아깝다. 그걸로 코딩까지 했으니 원.. 틀린 아이디어를 완전히 버리고, subtask를 읽어나가면서 차근 차근 다시 생각하니, 이 때는 쉽게 풀렸다. 먼저 편의상 interval을 [ai, bi+1) 형태로 처리하자. 이러한 형태의 문제에서 가장 큰 걸림돌은 구간의 길이가 크다는 것이니, 어떠한 긴 구간을 빠르게 처리할 수 있는 방법을 고민해봐야 한다. 좌표 압축을 통해서..
결론 : 92등으로 R3 진출 + 티셔츠. 뭐랄까.. 내가 이때 약간 졸린 상황이라서, 그냥 500등 안에 드는 걸 목표로 하고 대회를 봤다. A는.. 처음에 DP같은 걸로 접근하다가 뭔가 이상한거 같아서, 트리를 그려놓고 빅픽쳐 (?) 를 보니까 이해가 갔다. 아주 좋은 문제라고 생각한다. (19:37 Small, 20:00 Large) B는 이상하게 어려웠다. 처음에 내 실수로 머리보다 손이 앞서서 이상한 코드를 짰었는데, 예제 안나오는 걸 보고 이대로 하다가는 말리겠다 싶어서 밀고 딴 문제 생각하다 다시 왔다. 다시 와도 polynomial 풀이가 생각이 안 나서 그냥 brute force를 짰는데, 이상하게 brute force에서 규칙이 보였다 (..) 왜 되는지는 모르겠지만 아무튼 규칙대로 짜..
sort(a, a+n, [&](const pnt &a, const pnt &b){if((pi(a.x, a.y) > pi(0, 0)) ^ (pi(b.x, b.y) > pi(0, 0))) return pi(a.x, a.y) > pi(b.x, b.y);if(ccw(a, b) != 0) return ccw(a, b) > 0;return hypot(a) < hypot(b);});앞문제를 풀다가 발견한 코드. 1 2 3 4 사분면에 상관없이 각도정렬을 할 수 있다. + 5.21 업데이트. 각도가 같을 경우 거리순으로 정렬한다. (hypot(p) = p.x^2 + p.y^2, pi = make_pair) + 2017.8.14 업데이트. 코드 길이를 많이 줄였다.
1. Antenna http://amugelab.tistory.com/entry/problem-solving-20160130 에 있는 phone cell 문제 + binary search. https://github.com/koosaga/olympiad/blob/master/CEOI/ceoi06_antenna.cpp 2. Queue N이 작은 케이스에서 시작하자. 이 때는 linked list의 요령으로 문제를 풀 수 있다. prev(i) = i번의 왼쪽 원소, next(i) = i번의 오른쪽 원소라고 했을때, 초기값은 i-1, i+1로 가득 차 있고, 질의가 들어왔다면, 일단 A를 삭제하고, B의 앞에 A를 박으면 된다. 방법은 생략. 이러한 식으로 처리한 후, 후에 배열의 값을 모두 저장해놓고, 그냥..
https://www.acmicpc.net/problem/12010 이해가 안가면 이 글과 참고해서 보면 좋다 : http://usaco.org/current/data/sol_landscape_platinum_open16.html여담으로 이 문제는 KOI 2005 소방차와 상당히 유사한 문제다. 같이 보면 좋을 듯 하다. http://koistudy.net/?mid=prob_page&NO=313 1. O((NK)^2)dirt의 개수만큼 위치를 저장해 놓은 수열을 펴보자. 예를 들어 3, 1, 5, 1과 같이 수열이 주어지면 0, 0, 0, 1, 2, 2, 2, 2, 2, 3과 같은 형태로 수열을 바꾸는 것이다.수열 A, B가 있을 때 진행하는 연산에 대해서 다시 생각해 보면* 1. 추가 -> 수열 B에 ..
https://www.acmicpc.net/problem/3319한동안 글을 한꺼번에 썼었는데 나눠 쓰는 게 여러모로 나을 듯 하다. 앞으로 그런 방향으로 바꿔나가려고 함.언제봐도 신기한 harbingers 문제를 다시 리뷰하려고 한다. O(N^2)dp[i] = Min(dp[j] + (depth(i) - depth(j)) * V[i]) + S[i] for all j = (ancestor of i) 이다. Special Cases : Line O(NlgN) 일직선에서 이 문제는 아주 유명한 컨벡스 헐 트릭이다. (depth(j), func(j)) 라는 형태의 일차함수가 순서대로 들어오고, V[i] 쿼리를 이진 탐색으로 처리해 주면 된다. 이해가 안가면 여기서 멈추고, http://dyngina.tistor..
Soap Time (CF 118E) http://codeforces.com/contest/185/problem/E 일단 45도 돌려서 chebyshev distance로 생각하고, 지하철역이 없을 때에 대한 corner case를 처리해주자. 먼저 minsub[i] = (i번 정점에서 가장 가까운 임의의 지하철역까지의 거리) 를 정의하고, 구한 후 시작하자. 시간 제한이 넉넉하기에 아무 방법이나 썼는데, 난 2d range tree를 짠 후 parametric search를 돌리는 방식으로 O(nlg^3n)에 해결하였다. 문제 해결에 있어서는 최댓값을 최소화하기 때문에 직관적으로 parametric search가 떠오른다. parametric search를 구현하는 것이 가장 어려운 부분이다. 일단 답이..
1. 지우개 https://www.acmicpc.net/problem/11881 Solution 1 : dp[i][j] = A(a1) < A(a2) ... < A(aj) N - K개의 점을 지났다라고 정의하겠습니다. dp[i][j] = i번 점을 j번째로 지났다 라고 정의하면, 다음과 같은 점화식을 유도할 수 있습니다.dp[i][j] = Min(dp[i-1][k] + |Xj - Xk| + |Yj - Yk|) for all 1 = 2) 시간 복잡도는 O(N^3). 3. 신기한 키보드https://www.acmicpc.net/problem/1796 고정된 알파벳에 대해서 생각해보면 각각의 알파벳의 위치는 딱히 중요하지 않습니다. 'a'를 값으로 가지는 가장 왼쪽 / 오른쪽 만 찍고 오면 되니까요.dp[i][..
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=249좀 많이 입풀이라... 가려 듣길 부탁한다 ㅠㅠ D : Travel검증되지 않은 풀이다. 제대로 읽었다면 s - t, u - v를 잇는 vertex-disjoint path를 찾는 문제로, maximum flow를 짰고 틀렸다. 데이터탓이라고 정신승리후 끝냄. E : Roommate 옛날에 AC했었다. 풀이는 대충... 이랬던거 같다.dp[i][j][t1][t2] -> 지성(0번)이 i번 task까지 "완벽히" 완료했으며, 영표(1번)가 j번 task까지 "완벽히" 완료했고, t1번째 사람이 i+1 / j+1번째 task를 t2 시간동안 돌렸다.점..
- Total
- Today
- Yesterday