전체 글
-
7월 PS 정리카테고리 없음 2021. 7. 26. 12:26
Ascending Matrix $N \times M$ 격자에서 초기위치에서 특정 위치로 가는 서로 다른 경로의 수는 Lindström–Gessel–Viennot lemma를 이용해 구할 수 있으므로 $A_{R, C} = V$라면, 문제의 답은 2개의 다항식 $f(x) = \sum_{n = 0}^{K} nx^{n}$, $g(x) = \sum_{n = 0}^{K} det(p)x^{n}$를 interpolating했을 때, $K - (V - 1)$번째항의 계수가 된다. Xormites 주어진 수열의 xor sum이 0이면 항상 비기고, 그렇지 않을 때 수열의 길이가 짝수면 자명히 첫 번째 플레이어가 이기게 된다. 수열의 길이가 홀수일 경우엔 적절한 길이만큼 수열의 원소들을 오른쪽으로 shift해준 다음 0과 ..
-
Domino Covering카테고리 없음 2021. 6. 28. 16:29
https://www.acmicpc.net/problem/18607 문제의 답은 위와 같은데, 저대로 모든 값을 곱하는 것은 힘드니 Resultant를 통해 접근하자. 그래프 이론을 적용하면 경로 그래프의 완전 매칭의 수와 동치가 되므로 Binet–Cauchy formula에 의해 그래프의 교차하지 않는 경로들을 격자로 나타낸 행렬의 determinant를 이용해 식을 나타낼 수 있고 N, M에 각각 대응되는 식의 Resultant가 곧 타일링 가짓수가 된다. ${\LARGE f_{0} = 1 \text{ , } f_{1} = 1 +x \text{ , } f_{n} = (x + 2)f_{n - 1} - f_{n -2}}$ 위와 같은 점화식을 행렬멱법을 통해 구해준 다음 Resultant를 취해주면된다.
-
Link-Cut Tree에서 간선쿼리 처리하기카테고리 없음 2021. 4. 11. 11:54
if (M == 1) { cin >> x >> y >> z; if (x > y) swap(x, y); Link(Node[x], Node[N + eid]); Link(Node[N + eid], Node[y]); edge[{x, y}] = eid; node* n = Path(Node[N + eid], Node[N + eid]); n->Push(); n->lazy = z; n->Push(); ++eid; } else if (M == 2) { cin >> x >> y; if (x > y) swap(x, y); node* n = Lca(Node[x], Node[N + edge[{x, y}]]); if (n == Node[x]) Cut(Node[N + edge[{x, y}]]); else Cut(Node[x]); ..
-
20210218 PS 스케치카테고리 없음 2021. 2. 18. 23:53
풀고 싶은 문제가 많은데 하나같이 너무 어려워서 진전이 없다 BOJ 19017 Automorphism Subtree를 실시간으로 관리하기 위해 Dynamic Euler Tree를 생각했었으나 tree isomorphism 관련 글을 읽어보니 서브트리를 해싱해서 isomorphism을 찾고 간선 추가 쿼리를 오일러 트리를 쓰던 다른 BST 쓰던가 해서 관리하는 걸로 보인다. 아직 풀기엔 사전 지식이 부족해서 나중에 다시 제대로 잡아봐야겠다. BOJ 18761 Interesting Game 우선, 계모의 턴마다 계모가 취할 수 있는 최선의 전략은 수열에서 가장 큰 원소 B개를 지우는 것이라 볼 수 있다. 신데렐라의 최선 전략은 다음 턴에 0이 되는 가장 큰 B개의 원소들을 제외한 나머지 원소들에 수열 대체 ..
-
[Dynamic Tree With Subtree Query] 1.개요카테고리 없음 2021. 2. 9. 23:26
Dynamic Tree 자료구조 중 Link-Cut Tree는 Splay Tree의 특성상 임의의 노드 v의 서브트리의 정보가 올바르게 유지되지 않으며 이진 트리는 최대 2개의 자식만을 가질 수 있기 때문에 서브트리 쿼리를 다룰 수 없다. 체인과 서브트리에 대해 모두 다룰 수 있는 Top Tree와 같은 자료구조는 구현이 매우 복잡하고 시간 복잡도의 상수도 꽤 크기 때문에 실질적으로 잘 사용하지 않는다. 이진 트리의 자식은 최대 2개까지만 존재할 수 있으므로 3개 이상의 자식을 가진 노드를 고려하기 위해 virtual children과 virtual tree라는 개념을 도입하자. 이 때 splay tree 상에서 바로 연결된 자식 노드를 real children이라 부르며 트리에서 노드의 자식 노드는 여..
-
Top Tree & Maintaining Subtree Info In Link Cut Tree카테고리 없음 2021. 1. 24. 23:03
관련 문제 acm.taifua.com/bzoj/p/3153.html www.acmicpc.net/problem/17936 dmoj.ca/problem/ds5 테스트 케이스는 모두 동일한 것으로 보인다. Link Cut Tree는 트리를 동적으로 관리하기 위한 자료구조이지만 Path가 동적으로 바뀌면서 갱신되는 Auxiliary tree에는 기존 트리의 정보가 아닌 Access 이후의 경로에 대한 정보만 담겨있으므로 기본적으로 서브트리 쿼리는 다룰 수 없다. 오일러 투어 트리의 경우는 서브 트리 쿼리를 다룰 수 있지만 경로 쿼리는 처리할 수 없다. 물론 이를 개선해 동적으로 트리를 관리하면서 경로 쿼리와 서브트리 쿼리를 모두 처리할 수 있는 Topology Tree, Top Tree와 같은 자료구조가 있지..
-
Permutant카테고리 없음 2020. 12. 30. 23:27
koosaga.com/264 이 글을 보고 풀 수 있었다 주어지는 순열을 PER이라고 할 때 Cyclic Shift를 만족하는 행렬 C의 첫 행의 원소 P를 다음과 같이 구할 수 있다 순열의 인덱스를 저장하는 배열 SEQ를 선언하고 $SEQ[PER[i] - 1] = i$로 배열에 원소를 담는다 바뀐 순열의 인덱스를 담는 배열 PATH를 선언하는데 이 배열의 첫 번째 원소는 0이 되므로 배열 접근은 $N-1$번만 하면 된다 PATH의 원소는 SEQ와 이전항을 이용해 구할 수 있다 주어진 수열을 A라고 하면 i번째 PATH의 원소를 갱신하면서 P도 $P[i]=A[PATH[i]]$과 같이 갱신해준다 이렇게 구한 P를 이용해 $Resultant(P(x), x^n-1)$를 구해주면 AC를 받을 수 있다