구사과

http://www.codeforces.com/problemset/problem/449/D O(2^20 * N) cnt[i] = (i를 서브마스크로 가지고 있는 Aj의 수) 라고 정의하자. 즉 수열 A에서 (Aj & i == i) 인 원소의 수이다. 이건 O(2^20 * N)에 계산 가능하다.이제 답은 2 ^ cnt[0] 이.. 었으면 참 좋겠지만, 0이 아닌 다른 수를 서브마스크로 가지고 있는 Aj들이 존재하기 때문에 저럴 수는 없다. 고로 포함배제를 사용한다. 포함배제를 사용할때는, i의 비트의 수를 기준으로 포함 / 배제를 나눈다. i의 비트의 수가 홀수면 2 ^ cnt[i]를 빼주고, 아니면 2 ^ cnt[i]를 더해주는 식이다. O(2^20 * 20 + N)a[i] = (Aj == i인 j의 수..

http://oj.uz/problems/view/JOI14_constellation2삼각형 하나를 잡고 나머지 삼각형을 빠르게 세는..? 류의 방법으로 계속 시도를 해봤는데 진전이 별로 없었다. 실제 풀이는 굉장히 중요한 2개의 lemma에 의존하는데, * 1. 교차하지 않는 삼각형 쌍에 대해서, 두 삼각형을 완전히 분리시키는 직선이 항상 존재한다. * 2. 교차하지 않는 삼각형 쌍에 대해서, 삼각형 1의 점 - 삼각형 2의 점을 잇는 두 직선을 고려해 보자. (경우의 수는 9개). 이 중 두 삼각형을 완전히 분리시키는 직선이 항상 2개 존재한다. Lemma 1이 상당히 감명깊었다. 삼각형 쌍을 분리하는 법을 깔끔하게 정의한 것도 그렇고, (자명하지 않은) Lemma 2와 엮어서 실제로 문제를 깔끔하게 ..

A 솔직히 5분도 너무 오래 걸린것 같다..5분 pretest pass. AC+ : 결국 어떤 문자열 S, T가 있을 때 S를 적당히 rotate해서 T로 만들 수 있느냐를 묻는 문제였다. 계속반에서 비슷한 문제 (기하 문제였다) 를 KMP로 푸는 사람들이 꽤 있었는데, KMP에 숙달되었거나 라이브러리가 있는게 아닌 한, 시간 버리고 점수 와장창 까이기 딱 좋은 방법이다. 적당한 기준 원소를 아무거나 잡고 (난 std::min_element 를 사용했다.) 그쪽을 기준으로 rotate하는 것이 가장 좋은 방법이라고 생각. stl 떡칠시 아주 빠르게 짤 수 있다. 특히 std::rotate가 꿀. 난 문제를 너무 대충 생각해서 코딩 + 시간이 살짝 말린 채로 시작했고 그 부분이 아쉽다고 생각한다. (다행이..

https://www.acmicpc.net/problem/2795딱 봐도 NP-hard같은 문제를 N = 100을 주고 출제한걸 보니 당황하지 않을 수가 없었다. 일단 유일하게 생각해 볼수 있을 만한 접근법은 http://koistudy.net/?mid=prob_page&NO=369 와 같은 류의 바이토닉 기반 DP인거 같다. 한번 그 점을 생각해보고 어떠한 식으로 DP를 짜야지 최적 경로를 고려하는 점화관계를 이끌어낼 수 있는지 알아보자. 일단 생각을 쉽게 하기 위해서 1 -> 2로 가는 임의의 경로를 고정시키고, 그 경로상에서 2 -> 1로 오는 경로를 그려놓았다.#1 같은 경우에는 그냥 플로이드 한번에 풀릴 거고#2 같은 경우에는 위 링크건 문제를 풀어봤다면 그렇게 어렵지 않다. 다음과 같이 dp를..

Hill Walk (USACO 2013.03 Gold)https://www.acmicpc.net/problem/5835x좌표를 쭉 증가시키면서, 현재 f(x) 값으로 정렬된 선분들을 들고 다니면 쉽게 풀 수 있다. 이런걸 하는 데 가장 좋은 툴은 뭐니뭐니해도 BST. 선분이 교차할 일이 없기 때문에 한번 삽입 할 때 제대로 삽입하면 끝까지 문제가 생기지 않음을 알 수 있다. 저런 정렬된 선분들을 제대로 들고 다니려면 1. comparator를 재정의해야 하고, 2. comparator의 반환값이 가변적이라는 사실에 언어가 x랄을 하지 않아야 문제를 풀 수 있다는 점을 유념해야 한다. 1번은 http://amugelab.tistory.com/entry/STL-priority-queue-%ED%99%9C%E..

Water Tree (CF 343D)http://codeforces.com/problemset/problem/343/D거꾸로 생각한다. 기본적으로 모든 노드에 물이 채워져 있고, 1 ~ N개의 노드에 물을 비우는 연산을 넣어 줬다고 가정하자. 비우는 연산이라 함은 해당 노드와 그 부모에 있는 물을 모두 제거함을 뜻한다. * Query 1 : v의 서브트리에, 물이 비우는 연산이 적용되어 있는 노드가 있다면, 모두 지워주고, v의 부모에 물을 비우는 연산을 적용한다. * Query 2 : v에 물을 비우는 연산을 적용한다. * Query 3 : v의 서브트리에 물이 비우는 연산이 적용되어 있었다면 0, 아니면 1을 출력한다. 문제가 아주 깔끔해졌으며, dfs number 순서대로 수를 보관해두면, 세그먼트..

http://59.23.113.171/pool/koi_tree/koi_tree.php?pname=koi_tree Observation 1.문제를 쉽게 해서 유사도가 2일 때를 가정해보자. 그 때는 - 부모가 같으면 연결되어 있다. - 부모가 다르면 연결이 안되어 있다.고로 완전 그래프인 컴포넌트들이 떠다니는 그래프를 상상할 수 있다. 부모가 같은 게 뭔가 중요해 보인다는 사실을 알 수 있고, 난 여기서 착안해서 계통 트리를 다음과 같이 재정의했다. * 계통 트리는 S+1개의 노드로 이루어진 트리로, 각각의 노드는 1 ~ N의 개체들을 0개 이상 포함하고 있다. 이 때, 모든 개체는 정확히 한개의 노드에 속한다. 말로 하기가 너무 뭐한데.. 저 말대로 예제를 그려보면 대충 이런 느낌의 트리가 나온다. 이렇..

프리스비 (USACO Gold 2014.12)https://www.acmicpc.net/problem/10649N이 작은 문제다. 1) 비트 DP를 한다. dp(S) = 현재 집합의 추가 가능한 스택 양 이라 정의하면, Min(dp(S\j), Pj - Sum(S\j)) 중 최대인 j를 고르면 된다. 이후 모든 부분집합 S 중에 높이 합이 H 이상인 애들에 대해서 최댓값을 고른다. 2) 그리디를 한다. 집합이 고정되어 있을때, P + W 순으로 정렬한 후 구한 Min(P + W - S) 값이 항상 가능한 순열 중 최대를 낼 수 있다는 것을 증명할 수 있다. 고로 초기에 P+W 순으로 정렬후 모든 집합에 대해서 시뮬레이션하면 된다. 이런걸 그리디로 할 때는, deadline first라는 걸 기억해두면 편한..

http://codeforces.com/contest/618/ 졸리기도 하고 코포를 보고 싶지 않아서 제낄라고 했는데, 이름을 밝힐 수 없는 어떤 분이 자꾸 "코포봐야죠 코포안봐여?" 해서 봤다. ..아 근데 진짜 졸리긴 졸렸음. 한시간 자고 한시 반에 일어났는데 너무 일어나기 싫더라.. A 함정이 있을까봐 걱정했지만 그런거 없었다.4분 (AC) B a|b를 a||b로 써놓고 한참을 찾았다. 하... 19분 (AC) C 문제 자체는 간단하고 쉬운 기하 문제다. 각도정렬을 알면 풀이 나오는 수준. 내가 C를 락하고 열심히 hack을 시도했었는데, 다들 너무 잘짜서 아무 것도 시도하지 못했다. 하지만 정작 systest를 하니까 정말 수많은 사람들이 나가떨어졌고, 나가떨어진 사람들의 소스코드를 열심히 읽고 ..

(Different Class, 1995)