본문 바로가기

알고리즘/코드포스44

cf 626 div2 D - present (수론, 이분탐색) https://codeforces.com/contest/1323/problem/D 어렵지만 여기저기서 출제된 적이 있는 문제. 핵심 아이디어는 가져가자 최대 4e5개의 원소 n개를 갖는 배열이 있다. 원소는 1e7이하의 자연수를 갖는다. n개 중 2개 원소의 가능한 모든 쌍에 대해 합을 구해 모두 xor한 값을 구해라 (a1+a2)⊕(a1+a3)⊕ … ⊕(a1+an)⊕(a2+a3)⊕ … ⊕(a2+an)…⊕(an−1+an) 한 쌍의 합의 최댓값은 2e7이므로 답을 ans라 했을때 ans는 24개 비트로 표현 가능하다. ans의 k번째 비트가 켜져있는지 nlogn에 알 수 있다. a의 원소들은 k+1번 이후의 비트는 k번째 비트에 영향을 주지 않는다. b 2020. 3. 15.
cf 564 div2 D - Nauuo and circle (tree, graph dp) https://codeforces.com/contest/1173/problem/D 정확하지 않은 잘못된 점화식을 쓰려다 실패 최대 2e5의 정점 n개를 갖는 트리가 주어진다. 정점을 원위에 일정한 간격으로 배치했을 때 간선이 교차하지 않는 경우의 수를 구하라. n=4, edge = {(1,2), (1,3), (2,4)}인 경우 8. 아래 그림 참조 원의 맨 위를 1로 고정(전체드리의 루트 고정)시킨 후 경우의수를 구해서 마지막에 n을 곱하자 f(u) : u를 루트로하는 서브트리를 간선이 교차하지 않도록 배치하는 경우의 수 (각각의 자식노드를 루트로 하는 서브트리(sub(v))를 비어있는 원 위에 순서대로 배치하면 된다. 이 때, 각각의 칸 안에도 sub(v)의 루트와 그 자식들이 순서대로 배치돼야 한다... 2020. 3. 15.
Codeforces #627 div3 F - Maximum white subtree (graph dp, reroot) https://codeforces.com/contest/1324/problem/F reroot 첫 성공 무방향트리가 주어진다. 각 정점마다 하얀색(1)또는 검은색(0)으로 색칠되어 있다. i번 정점을 포함하는 서브트리 중 하얀색정점의 개수 - 검은색 정점의 개수가 최대인 경우 그 값을 각각 구해라 (i=1,2,3,4...n) 1번 정점을 root로 하는 전체 트리에서 dp[u] : u를 포함한 서브트리에서 cntw-cntb 최대값 u에 인접한 v에 대해 ans[v] = dp[v] + max(dp[u],0)이다. v에서원하는 값 ans[v]가 u,v에대한 상태로만 정의되므로 reroot 적용가능하다. dp[u] -= max(dp[v],0) dp[v] += max(dp[u],0) go(u,v) dp[u] =.. 2020. 3. 14.
Educational #56 D - GCD counting (트리(숲) 지름, 소인수분해) https://codeforces.com/contest/1101/problem/D 소인수분해 시간복잡도를 잘못 파악하고 있었다. 루트n인줄 알았는데 소인수분해는 loglogn이다. (에라토스가 루트n이다) 트리 지름 구하는 방법은 알고 있었지만 숲에서 최대 지름을 구하는 것을 O(n)에 할 방법을 생각하지 못했다. 같은 시간복잡도를 갖는 코드라도 시간제한이 빡빡해서 최적화를 해줘야 한다. (난이도에 비해 푼 사람이 적은 이유인듯) 단일 트리와 다른 특별한 알고리즘을 사용하진 않는다. 한 점 잡고 제일 먼 점 u와 u에서 제일 먼 점 v와의 거리를 모든 트리에 대해 구하면 된다. 하나의 트리에 대해 최대 지름을 구한 후, 방문처리를 위한 vst배열을 초기화하지 않고 다음 트리에 대해 최대 지름을 구하는 부.. 2020. 3. 13.

티스토리툴바