rkm0959, jhhope1이랑 진행한 문제풀이의 간략한 풀이. 스포일러에 주의하자. BOJ 15313. 정과프 해적단 $[l, r]$ 값이 없는 문제는 좌표압축 + 세그먼트 트리를 이용한 dp로 $O(n\log n)$에 해결할 수 있다. 이 때 $l$이 증가할수록 조건을 만족하기 위해 필요한 최소의 $r$도 증가하므로 inchworm을 얹어주면 $O(n^{2}\log n)$이 된다. BOJ 15504. 프로그래밍 대결 제일 실력이 높은 선수를 제외하고, 각 선수마다 ‘자신을 이기는 선수’를 정해주면 스패닝 트리가 유일하게 결정된다. 해당 작업을 mcmf로 모델링하면 $O(n^{4})$. 늘 그렇듯 플로우 문제에서 시간복잡도는 아무 의미 없다....
교육용으로 사용한 10문제의 풀이입니다. 용어가 원본 문제와 다를 수 있습니다. BAPC 2021 F. “Fair Play” $n$이 홀수인 경우는 당연히 불가능하고, 짝수인 경우 $(b, p)$를 std::pair 와 같은 방식으로 정렬한 것을 $(b_{1}, p_{1}), \cdots, (b_{n}, p_{n})$이라고 둡시다. 이 때 유일하게 가능한 매칭 방법은 $(b_{1}, p_{1})$을 $(b_{n}, p_{n})$과, $(b_{2}, p_{2})$를 $(b_{n-1}, p_{n-1})$과 … 매칭해주는 것입니다. 이렇게 해서 벡터합이 모두 균일하다면 possible, 그렇지 않다면 impossible 입니다. BAPC 2021 I “Implementation Irregularities” $s_{i}$가 증가하는 순서대로 원소들을 배열하고, $s_{i} = -1$인 원소들을 제외합시다....
SWERC 2019 H번 문제이다. BOJ 18300번이기도 하다. ...
SWERC 2019 J번 문제이다. BOJ 18302번이기도 하다. 대회 중에는 rkm0959가 풀었다. 너무 긴 본문이 읽기 싫어서 알큼이 요약해준 문제 설명대로만 코드를 짰다가 중요한 디테일을 누락시켜서 엄청 고생했다… 간단히 말해서, inorder traversal (LDR 순회)이 주어진 수열이 나올 수 있는 binary tree의 개수를 구하는 문제이다. 단, 이 tree는 min-heap의 조건 (자식 $\ge$ 부모)를 만족해야 한다. ...
SWERC 2019 K번 문제이다. BOJ 18303번이기도 하다. rkm0959한테 문제 요약만 들어서 본문을 잘 모른다(…) Unweighted Directed graph에서 어떤 고정된 정점 $T$에 대해 $u \to T$ 간선이 있고, 이 간선을 사용하지 않으면 $u$에서 $T$로 이동할 수 없는 정점 $u$를 모두 구하는 문제이다. 정점 개수와 간선 개수는 $10^{5}$개 이하. ...