구사과

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가 꿀. 난 문제를 너무 대충 생각해서 코딩 + 시간이 살짝 말린 채로 시작했고 그 부분이 아쉽다고 생각한다. (다행이..