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 시간동안 돌렸다.점..
오늘 3월 19일은 대회가 두개나 있었다.. CROC 2016새벽에 했던 대회. 출제진에 대한 걱정이 컸었다. 저번 Div1D의 심슨 어쩌구에 대한 강한 기억이 아직도 (...) 물론 난 그 때 B도 못풀었지만 말이다. (그리고 폭풍 -118) CC부터 풀었다. 부분 합 + 이진탐색을 쓰는 쉬운 문제. 6분 AC. http://codeforces.com/contest/645/submission/16785733 B그리디. 일반식을 쓸까 하다가 BIT 짜는게 더 빠를거 같아서 그렇게 했다.9분 AC. http://codeforces.com/contest/645/submission/16786132 A당황스러웠던 문제. 쉬운 방법이 있을법도 하다 싶었지만, 그냥 백트래킹을 짰다.14분 AC. http://cod..
Network (ICPC Seoul Regional 2007)https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=283&page=show_problem&problem=1903처음에 DP로 접근했다 시간을 많이 날렸다. (DP 풀이는 잘 모르겠다.) 대충 이런 그리디를 짜서 live archive AC를 먹였는데, 데이터를 믿을 수 없는 저지이기 때문에 (...) 반례가 있다 싶으면 지적해주길 바란다. * 리프 노드를 깊이가 큰 순으로 정렬해서 처리한다. * 처리중인 노드에서 거리 K 이하에 서버가 없으면 노드의 K번째 조상에 서버를 지어준다. 아니면 넘어간다. 복잡도는 O(N^2)이다. Superset ..
http://www.codeforces.com/contest/484/problem/E질의를 볼 때 모든 길이 w의 subsegment를 다 볼거라는 생각으로는 진전이 없다. 대신, 답을 정해놓는 식의 binary search를 유용하게 쓸 수 있다. binary search로 접근해보자. 질의의 답이 H[i]라고 가정했을 때, 구간 [l, r] 내에서 주어진 조건을 만족하려면, H[i] 이상의 원소들로만 이루어진 연속 최대 구간의 길이가 W 이상이어야 한다.즉 문제는 구간 [l, r] 내에서 H[i] 이상의 원소들로만 이루어진 연속 최대 구간의 길이를 구하는 것으로 정리되었다. 크게 두가지 방법이 있다. * 1. Persistent Segment Tree기본적으로 구간 [l, r] 내에서 연속 최대 구간..
https://www.acmicpc.net/problem/9482Solution 1 :원으로 생각하면 골치아프니 (x, y, z)를 중심으로 하는 2k 길이의 정육면체를 생각하고, 여기 안에 있는 점들을 일일히 순회한다. 순회를 할 수 있다고 치면 복잡도는 얼마일까? 답에 도움이 안되는 점들은 정육면체 - 구 영역에 존재할 것이다. 이러한 영역은 8개이며, 8개 영역 각각에 속하는 모든 점들은 서로의 거리가 K 이하이다. 고로 각 영역에 이러한 점들은 많아야 O(sqrt(ans))개. 순회만 할수 있으면 된다.순회를 하는 건.. z축 기준으로 스위핑을 하며, 스위핑 과정에서 세그트리 + std::set을 사용했다. std::set은 y축 기준 정렬, 세그트리는 x축 기준이고, x축은 이 때문에 약간의 좌..
Problem : N개의 점이 주어졌을 때 가장 거리가 가까운 점 쌍을 출력하라. 거리는 유클리드 거리를 기준으로 한다.https://www.acmicpc.net/problem/2261 Solution : 모든 쌍을 보는 문제에서 자주 쓰는 기법인 분할 정복을 사용한다. 분할 정복에 대해서 대충 안다면, * Divide : Solve(s, e) 함수를 호출했을 때, Solve(s, m) / Solve(m+1, e) 로 두개의 집합 내에서의 모든 쌍을 본다.* Conquer : 한쪽이 왼쪽 집합 / 한쪽이 오른쪽 집합일 때 왼쪽 집합과 오른쪽 집합간의 Closest pair를 빠르게 찾는다. 한쪽 끝이 왼쪽 / 한쪽 끝이 오른쪽이니까 뭔가 빠르게 되지 않을까. 라는 기대와 함께 (?) 와 같은 메커니즘으로..
http://codeforces.com/contest/650 A x같은거 + y같은거 - 둘다같은거 3분 AC B 문제를 읽다가 내가 제대로 읽은건지 긴가민가해서, 시간을 너무 낭비한 문제. (큰 차이는 없었지만..) 시작 점을 binary search하던지, 답을 binary search 하던지, two pointers를 쓰던지... 16분 AC C tourist가 10분 안에 풀기에, 적어도 코딩은 쉬운 문제이구나라고 생각했는데, 결국 코딩이 쉬운 방법은 찾지 못했다. 그런 사람들 보고 함부로 문제 평가하지 말아야.. ㅠㅠ. 약간의 WA끝에 pretest를 통과. 풀이도 썩 쉽지는 않다. 같은 행 - 열에 있는 점들간에 그래프스럽게 에지를 이었다 생각하고 dfs하는게 풀이. 꽤 까다로운 문제였고 그런..
- Total
- Today
- Yesterday