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와 엮어서 실제로 문제를 깔끔하게 ..
- Total
- Today
- Yesterday