구사과

이번 라운드는 할말이 별로 없는듯.. 푼 순서대로 서술한다 A 이 라운드가 dynamic scoring 인줄 몰랐다 맨 처음엔. 내가 너무 싫어하는 lexicographical + bracket 의 연속이라 정말 풀기 싫었는데 5분만에 E번을 푸는 사람이 나오면서 아 이거 dynamic scoring이구나를 깨닫고 던졌다. 결국 라운드 끝날 때 A가 가장 어려운 문제로 확인. 솔직히 딱 봐도 어려워 보인다. E 5분만에 AC가 나와서 아 저거 복붙충 아니냐 **.. 은 농담이고. 쉬운가 싶어서 바로 봤다. (다만 3~5분 AC는 복붙이 맞는 거 같다) 처음 문제를 봤을때는 풀수 없음을 증명하는게 빠르지 않을까 (...) 하고 당황했는데 제약 조건을 본 후 그냥 평이하게 풀리는 문제임을 확인했다. 20분 ..

http://poj.org/problem?id=2104https://www.acmicpc.net/problem/7469 1. Naive - O(MNlgN)더 이상의 자세한 설명은 생략..O(N) Selection Algorithm이 있지만 느리면 느렸지 빠르진 않을 듯.여담으로, 잘 컷팅하면 이걸로 2번보다 빠르게 풀수 있다 ㅡㅡ; 2. Query Sorting - O(NlgN + M*N^0.5*lgN)http://amugelab.tistory.com/entry/%EB%A3%A8%ED%8A%B8-%EC%95%BC%EB%A7%A4때문에 역시 자세한 설명은 생략.간단히 설명하자면, 맨 처음 좌표압축을 한 다음에 링크 1번 트릭 + K번째 원소 BIT를 구현해 주면 된다.시간이 간당간당한 편이다.. 버킷 사이..

pdf로 대신한다.

https://www.acmicpc.net/problem/2519 새로운건 없는데 다까먹었네.. 다음과 같은 논리식들을 만족하는 막대기가 필요하다.1. 교차하는 막대기 두 쌍이 있다면, 두 쌍 중 한 쌍이 사라져야만 한다.2. 3개의 막대기 중 한 막대기를 사용한다면, 나머지 두 막대기는 사용하면 안된다.고로 2-SAT으로 풀리는 문제이다. 논리식을 만들어주자. 2번은 너무 당연히도 명제이다. 막대기 A를 지운다는 것을 E(A) 라고 표현했을 때, 2번은 E(A) -> ~E(B), E(A) -> ~E(C)... 를 6 (3 * 2)개 만들어주면 된다.1번은 약간 변형해줘야 명제가 된다. E(A) || E(B) 라는 식의 명제인데. 논리식은 가정이 참이면 결론이 참이어야 하고, 가정이 거짓이면 항상 참이다..

핵어렵다 ㅎㅎ https://www.acmicpc.net/problem/5474 1. Greedy - O(NHlgH)그리디 전략을 설명하기 전에 사실 돛대의 순서들이 문제에 전혀 상관이 없다는 사실을 알아야 한다. 때문에 돛들을 편한대로 정렬한 다음에 쓰면 된다.그리디 전략은 다음과 같다. 돛대라는 말은 어감이 짜증나니(?) 막대라는 말로 대신하겠다." 막대들을 길이가 증가하는 순서대로 정렬한 후, 각 막대에 대해서 H개의 돛들을 꽂을 수 있는 열 중 가장 꽃혀있는 돛이 적은 열에 꽃는다. 이를 모든 돛에 대해서 반복한다. 이후 열에 꽃혀있는 돛의 개수가 n개일 경우 n * (n-1) / 2를 각 열에 대해서 더한다." 딱 봐도 될거같은 이 그리디 전략은 실제로 된다. (^^;) 왜 되는지는 나도 모르니..

tl;dr 우여곡절이 많았는데 생각보다 많이 올라서 기분좋다 (+85 = 2057) A패스 여담으로 코드를 개더럽게 짰다 (나만 더럽게 짠건 아닌듯 ㅎㅎ) B그래프를 이것저것 그려보며 생각을 해봤다 사실 처음에는 Hopcroft Karp가 아닐까 하는 알지도 못하는 알고리즘에 대한 개쓸데없는 생각을 하면서 멘붕을 시전했지만 역시 개쓸데없는 생각이었고 그냥 위상정렬하면 되더라.. http://183.106.113.109/pool/ioi_islands/ioi_islands.php… 를 얼마전에 푼게 엄청 도움된듯. 여러분도 푸세여! 디버깅하는데 시간을 꽤 날렸는데 너무 아깝다 Dynamic Scoring 상에서 500점이라서 멘붕했었는데 시스템에서 1000돼서 행복했다. 다행이도 시스템 테스트에서 사람들이 ..

ppt 자료로 대신.

http://geniusainta.com/problems/view/APIO14_palindrome 이 문제의 정해는 Manacher's Algorithm + Suffix Array이다.난 전자는 알지만 후자는 모르기 때문에 (...) SA 대신 Hash를 사용해서 풀었다. 때문에 처음부터 해시를 사용했다는 가정 하에 설명한다. unordered_map을 기준으로 설명한다 (괜히 로그떼면 기분 좋으니까 (?)) 1. Naive - O(n^2)substring의 개수가 O(n^2)이며 해싱을 사용하면 팰린드롬 판별은 O(1)에 가능하다. 모든 팰린드롬을 map에 때려박고 개수를 세면 된다. 2. Hash + Manacher + Tree - O(n)일단 한 문자열의 서로 다른 팰린드롬의 개수는 n개임을 알고 ..

https://www.acmicpc.net/problem/5465 격자상에 어떠한 점도 Mecho가 일찍 도착하는 것이 무조건 이득이라는 점을 쉽게 관찰할 수 있다.이는 Mecho가 t만큼 꿀을 빨고 출발했을 때 도착할 수 있다면, t보다 작거나 같은 시간 u만큼 꿀을 빨고 출발해도 항상 도착할 수 있다는 것을 의미한다. 때문에 t의 정의역을 설정해 준 후 Parametric Search를 해주면 문제를 쉽게 풀 수 있다.이제 과제는 시간 t만큼 꿀을 빤 이후에 Mecho가 집에 도착할 수 있는지에 대한 문제로 귀결된다. 먼저, 벌들의 위치를 한꺼번에 Queue에 넣은 다음에 너비 우선 탐색을 할 경우, 한 격자에 도달하기까지 벌이 걸리는 시간을 쉽게 O(n^2) 에 precompute할 수 있다.벌이 ..

http://koistudy.net/?mid=prob_page&NO=593 1. Naive ( O(N^2lgN) ) 트리에 대한 기본적인 지식이 있으면 풀 수 있다. 서브트리의 경우의 수가 N개이니, N개의 각 경우에 대해서 내부에 있는 노드를 Greedy하게 더해서 경비병을 최대화 하면 된다.내부 노드에 있는 cost들을 그때 그때 sort해주면 N^2lgN이다. 2. Naive (...) ( O(Nlg^2N) ) 일단 그때 그때 sort해주기 보다는 priority_queue 등의 자료구조를 사용해서 서브트리에 있는 원소들을 재귀적으로 합쳐주자.이 역시 O(N^2lgN)이 걸린다. 이 때 합치는 대상이 되는 힙을 "가장 원소 개수가 많은 힙" 으로 설정해주자.약간의 커팅.... 은 무슨, 이걸로 시간..