구사과

https://www.acmicpc.net/problem/1156https://www.acmicpc.net/problem/6065 이 문제 데이터 오류가 있다. 대회 당시 워낙 어려웠던 문제라 이의제기가 안됐을 뿐... http://blog.myungwoo.kr/6 O(N^2Ti) 일단 관찰 하나가 필요한데, 그 날이 끝났을 때 굳이 소독을 어떻게 맡길지 결정할 필요는 없다. 장난감이 필요할 때마다, 그전 상황을 끼워맞춰 가는 식으로 최대한 이득을 보는 상황을 결정하는 것이 필요하다. 그 전날에 상황을 끼워맞출 수 있는 가짓수는 크게 세가지가 있는데 * 1. 장난감을 새로 샀다고 생각 * 2. 그 전에 썼던 장난감을 1번 소독소에서 가져왔다고 생각 * 3. 그 전에 썼던 장난감을 2번 소독소에서 가져왔다..

https://github.com/koosaga/iamcoder

http://codeforces.com/contest/487/problem/E 문제 설명은 생략함. HLD + BCC를 섞은 문제로써 헬문제였따.. 풀이를 대충 요약하겠다. BCC 파트가 제일 어려웠는데, 지금 열거하는 방법으로 BCC를 트리로 묶어줄 수 있다. 꽤나 스탠다드한 방법이 아닐까 싶다. 익혀두자. * 1. Cut Vertex + BCC Component가 정점이 된다.* 2. Cut Vertex와 연결된 BCC Component를 이어줌으로써 트리를 만든다. * 3. BCC Component에서 DFS Number가 가장 높은 애를 BCC Parent라고 정의한다. 이건 내가 쓴 BCC 알고리즘에서, 처음 새 컴포넌트를 spawn한 노드와 동치라고 할 수 있다. * 4. 문제 특성상 각각의 ..

글을 읽기 전에 SCC와 절점 절선 개념을 배우고 오길 추천함. 간단히 요약하자면 그래프에서 사이클 비슷한 건 정점 하나로 묶어버리고 트리라 치는 알고리즘이다.이러한 점에서는 SCC랑 엄청 비슷하다. 실제로 SCC의 무향 버전이라고 생각해도 좋음. SCC는 사이클을 정점 하나라고 묶어버리고 DAG로 만드는 방법이면 BCC는 사이클을 간선 하나라고 묶어버리고 트리로 만드는 방법이다. 결국은 다 사이클이 싫어서 하는 짓임. 사용 용도도 SCC랑 상당히 비슷하다. BCC에는 두가지 종류가 있다. SCC는 하나만 있는데 얘는 좀 다르다. * Vertex-disjoint biconnected component : 그래프에서 절점을 제거함으로써, 컴포넌트를 나눔 * Edge-disjoint biconnected c..

https://www.acmicpc.net/problem/1859 O(N^2lgN)Ti / Pi 증가 순으로 정렬된 시험 결과들을 토대로 avg(D)를 정의하자. avg(D)는 그리디 전략으로 D개의 과목을 드랍했을 때 베시의 점수이며, (T(N-D+1) + .... T(N)) / (P(N-D+1) + ... P(N)) 이다.이 때 베시가 더 좋은 점수를 낼 조건은 Sum(T) / Sum(P) > avg(D) 를 만족하는 크기 D의 집합이 있다는 조건이다. 비슷한 유형을 풀어보면 알겠지만, 이는 Sum(T - avg(D) * P) > 0 을 만족하는 크기 D의 집합이 있다는 것과 동치이다. Sum(T - avg(D) * P) > 0을 만족하는 집합이 있는지... 는 굳이 말 안해도 다들 알겠지만, 1 ~..

https://www.acmicpc.net/problem/6007 O(N^4)Maximum Toll Cost의 경우의 수가 O(N)이니. 이걸 고정시키고 O(N^3) Floyd Warshall을 돌리면 된다. Toll cost T보다 값이 크면 그 근처에 있는 에지들을 몽땅 날려버리고 플로이드. 반복 반복... 시간 복잡도는 O(N^4). TLE다. O(N^3)플로이드 와셜의 루프. For(i, j, k) dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);를 생각해 보자.맨 바깥쪽 루프에서 도는 것은 중간 경유지이다. 2차원 배열에 중간 경유지를 모두 돌면서 업데이트하는 것이다.그러면, 어떠한 j , k에 대해서, j -> k로 가는 최단 경로가, i까지 경..

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-18-shortest-paths-ii-bellman-ford-linear-programming-difference-constraints/30분 정도부터 보면 된다. 간략히 말하자면 변수 x1 ... xn N개와, xj - xi

http://www.koistudy.net/?mid=prob_page&NO=2058 재밌는 문제.. 텔레포터를 타고 여기저기 옮겨나간다는 문제의 개념이 상당히 당황스러울 가능성이 높다. 막히지 않으려면 "그래프"라는 사실을 빠르게 파악해야 한다. 나뉘어진 선분 구간은 정점이고. 텔레포트는 간선이라는 것을 관찰하면 * 경로 간선의 개수를 최대화 * indegree와 outdegree는 모두 1이다 (시작 끝점 빼고) * 텔레포터의 설치는 두 정점 i, j의 나가는 간선의 교환이다 이 사실을 파악하면 문제가 상당히 깔끔해진다. 먼저 그래프의 성질을 관찰하자. * 컴포넌트 내의 indeg / outdeg가 모두 1이면 컴포넌트는 사이클을 이룬다. * 고로 그래프는 사이클 컴포넌트들의 집합이다.. 근데 시작 끝..

https://www.acmicpc.net/problem/3323 일전에 한번 멘붕이라고 언급한 적이 있었는데 (http://amugelab.tistory.com/entry/201573-2015723-problem-solving) 제대로 접근하면 아주 어렵지는 않다. 먼저 삼각형 쿼리를 뜯어보자. 한 점이 원점인 삼각형이면, 각도 범위 안에 있는 점들 중에서, 해당 선분 아래에 있는 점이 존재하는가? 를 묻는 문제가 됨을 알 수 있다.그러면 각도 범위를 무력화하면 어떨까..? 그러면 꽤 유명한 문제다. (https://www.acmicpc.net/problem/7057) 들어오는 점 집합을 Convex Hull만 남겨두고, 이진 탐색을 하면 풀 수 있다. 복잡한 설명은 생략.. 문제는 쿼리가 구간으로 들..

https://www.acmicpc.net/problem/2434http://koistudy.net/?mid=prob_page&NO=375 모든 점을 통괄하는 경로는 교차할 수 없기 때문에, 윗바닥과 아랫바닥을 먹는 두 선이 갈린다고 생각할 수 있다. 두 선의 상태는 그렇게 많지는 않아서, 이 "두 선"을 바탕으로 점화식을 세우는 것이 좋을 것이다. 나의 경우에는 다음과 같은 세개의 상태가 나왔다. * U[i] = i번 줄까지의 원소들을 다 봤고, i+1번째 줄의 위에서 1 - 2번째 원소에 발을 내린, 그 외에는 전혀 건들지 않은 상태 * M[i] = i번 줄까지의 원소들을 다 봤고, i+1번째 줄의 위에서 1 - 3번째 원소에 발을 내린, 그 외에는 전혀 건들지 않은 상태 * D[i] = i번 줄까지..