Eau de Cologne
문제: https://codeforces.com/contest/1858/problem/E2 자료구조의 Persistency를 관리하는 문제다. 자료구조의 Persistency는 주로 다음과 같은 문제이다. 어떤 자료구조 $S$를 구현하여라. $S$의 가장 마지막으로 진행한 연산을 취소해라. 이런 문제는 대개 다음과 같은 방법으로 풀린다. $S$를 구현한다. 단, $S$에서는 "amortization"을 쓸 수 없다. $S$에 어떤 연산을 진행할 때, $S$의 변경 기록을 저장한다. $S$의 마지막 연산을 취소할 때, 변경 기록을 역으로 돌린다. 무슨 말인지 살펴보자. "amortization"을 쓸 수 없다. 우리가 쓰는 자료구조 중에서는, 각 연산은 오래 걸릴 수 있지만, 전체 연산의 시간 복잡도는 특..
문제 https://www.acmicpc.net/problem/21853 풀이 (Subtask 4) 더보기 $k$를 고정하고, Tree-DP를 사용합니다. 정점 $v$에서, 서브트리가 조건을 만족하고, $v$는 자식 정점과 연결되는 간선을 $k-1$개 이하가 되도록 할 때 가중치 합의 최솟값을 $A_v$라고 합시다. $v$에 대한 추가 조건이 없는 경우의 가중치 합의 최솟값을 $B_v$라고 합시다. 정점 $v$를 고정하고, $v$의 자식 정점의 집합을 $S$라고 합시다. 또한 $w(a, b)$를 $a$와 $b$를 잇는 간선의 가중치라고 합시다. $v$와 연결할 자식 정점의 집합을 $T$라고 합시다. 해당 자식 정점은, 부모와 이미 간선 $1$개가 이어져있기 때문에, $k-1$개의 간선만 이을 수 있습니다..
트리DP 탐험기 https://www.acmicpc.net/workbook/view/16329 문제집: 인류의 엔딩 크레딧 (rustiebeats) www.acmicpc.net https://www.acmicpc.net/problem/8872 https://www.acmicpc.net/problem/1693 https://www.acmicpc.net/problem/21141 https://www.acmicpc.net/problem/16859 https://www.acmicpc.net/problem/5477 https://cologne.tistory.com/55 https://www.acmicpc.net/problem/21853 https://cologne.tistory.com/65 https://www...
문제: https://atcoder.jp/contests/abc309/tasks/abc309_h 풀이: 더보기 $O(NM)$ 에 문제를 해결하는 것은 쉽습니다. $D_{r, c}$ 를 $A_1, \cdots, A_K$에서 출발해서 $(r, c)$로 도달하는 경우라고 합시다. 답은 $D_{N, B_1} + \cdots + D_{N, B_L}$입니다. $D_{1, c}$ 는 $A_i$에서 $c$가 등장하는 횟수입니다. $(1 \le c \le M)$ $D_{r, c} = D_{r-1, c-1} + D_{r-1, c} + D_{r-1, c+1}$입니다. $(1 \le c \le M)$ 단, $D_{r, 0}$ 와 $D_{r, M+1}$ 은 항상 $0$으로 가정합니다. 이제 이를 다항식 형태로 바꿔봅시다. $D..
우려냈을 때는 진한 주황색에서 갈색의 색이 나는 홍차입니다. 어떤 홍차인지는 써있지 않았습니다. 포장을 뜯었을 때 강한 파파야의 향인 났습니다. 코코넛과 매우 비슷한 향이었습니다. 쓰인대로 2분간 우리고 난 이후에 파파야의 향이 강하게 나지는 않았습니다. 단맛이 그렇게 강하지는 않았고 적당한 바디감과 함께 부드럽게 마실 수 있었습니다. 데일리로 마시기에는 향이나 가격이 조금 부담스럽고, 그렇다고 해서 특별하게 맛이나 향이 인상깊은 차도 아닌 것 같습니다. 차를 식혀서 얼음과 함께 먹는 것을 좋아합니다. 이렇게 먹으면 좀 더 은은한 향을 많이 즐길 수 있어서 좋은 것 같습니다.