본문 바로가기

전체 글

 (31)
LGCPC 2025 본선 D. 배달 풀이 Subtask 1. $B_i = 1$이기 때문에 정답은 항상 모든 $A_i$의 합입니다.Subtask 2. 여러 가지 풀이가 있습니다. QNlog^2N + QNBlogN 풀이와 QNB 풀이를 소개합니다. QNlog^2N + QNBlogN ) tree DP를 하면서 현재 정점 c를 볼 때 c의 서브트리만 고려한 상태에서 선택된 최적 물건들을 생각합니다. c의 자식들을 n1, n2, ..라 할 때 각각의 최적 물건들을 전부 다 합친 후, A[c]를 B[c]개 추가한 후, 물건의 개수가 sz[c]가 될 때까지 가장 작은 원소를 빼는 작업을 반복하면 됩니다. 이는 트리의 euler tour을 생각하면 interval scheduling 꼴이 되므로 증명 가능합니다. 이를 small-to-large으로 구현하면..
LGCPC 2025 예선 D. 신호기 풀이 제곱 풀이를 최적화하는 방향으로 전체 문제를 풀 수 있습니다. dfs를 하며 문제를 해결합니다. c의 subtree에 대해, DP[c][d]를 'c의 서브트리의 신호기만 켜고 끌 수 있으며' 'c에서 조상으로 가는 경로 기준 높이 d까지 커버'하는 최소 비용이라 합시다. 이럴 경우, tree DP를 하면서 다음 처리를 해 주어야 합니다. c의 자식 n에 대해서, DP[n]에 대해 dep가 dep[n] ~ dep[c]-1인 값들의 minimum을 DP[n][dep[c]]에 대입해줍니다. 이게 정당한 이유는 c - n edge 위에 정점이 없기 때문입니다. c의 자식에 대해 두 DP식이 다음과 같이 합쳐지게 됩니다. dp1과 dp2에 대해, '그냥' 합치기 -> new[max(l,r)] = dp1[l] ..
Game Theory 1 : Grundy, Green Hakenbush, Red-Blue Hakenbush
LGCPC 2024 예선 D. 보안 점검 풀이 3가지 정도의 풀이가 있습니다. 1. DnC opt DnC opt의 아이디어를 이용합니다. 항상 답이 단조감소한다는 관찰을 할 수 있습니다.  DnC opt를 하듯이, DnC(int l, int r)에서 초기에 추가된 간선(쿼리로 추가되지 않은 간선)들 중 이 시점에서의 답에 관여하는 간선들의 vector S를 관리합니다. mid = (l + r) / 2에 대해서 시점이 mid일 때의 답을 구한 후, 이를 ans라고 합시다. (이 때의 답을 구할 때, S에 쿼리 번호 l ~ r 사이 간선 추가/중요도 증가/한계점 증가 쿼리를 반영하고, (|S|+r-l)log|S| 등 |S|와 r-l에 관한 시간복잡도로 구할 수 있도록 해야 합니다. 이는 DnC opt 과정에서 t=l, t=r일 때의 답을 구해놓고, 미리..
PMA Chapter 6 : The Riemann-Stieltjes Integral Definition. let [a, b] given interval, a partition P of [a, b] :finite set of a points x_0, x_1, ..., x_n where a = x_0 \delta_x_i = x_i - x_(i-1).suppose f : bounded real function defined on [a, b]. for each partition P of [a, b], M_i = sup f(x) (x_(i-1) U(P, f) = sigma M_i \delta_x_i, L(P, f) = sigma m_i \delta_x_iintegral a, b^ = inf U(P, f), integral a^, b = sup L(P, f) if same, then f is Ri..
PMA Chapter 5 : Differentiation 왠만해선 real function만 다룰 것이다. ## Derivative of Real function Definition. f가 [a, b]에서 정의된 real-valued function일 때, any x \in [a, b]에 대해 \phi(t) = (f(t) - f(x)) / (t-x) (a0 f'(x) 생각시 존재 안함. f(x) = x^2 sin(1/x) if x!=0, else 0으로 잡자. f' = 2x sin(1/x) - cos (1/x)이고, lim x->0 f'(x) 생각시 f'(0) = 0. 즉 이 함수에서 f는 all point x에서 differentiable(즉 f' 존재) 하지만, f'이 continuous하진 않다. (0에서 discontinuous) ## Mean valu..
PMA Chapter 4 : Continuity ## Limit of Functions Function의 Limit가 정의되어야 한다. Definition. X, Y가 metric space일 때, E \in X인 E에 대해, f maps E into Y이고 p가 E의 limit point라 할 때, x -> p일 때 f(x) -> q라고 쓰거나, 혹은 lim x->p f(x) = q라 하려면, 다음을 만족하는 q \in Y가 존재해야 한다. for all \epsilon > 0. Exist \delta > 0, 0 0 p f(x) != f(p)일 수도 있다. (조건상에서 0 ..
PMA Chapter 3 : Numerical Sequences and Series ## Convergent of Sequences 엡실론, 델타. {p_n} is sequence in a metric space X. {p_n} is converge if..there is a point p \in X, for every e > 0, exist int N such that n >= N -> d(p_n, p) {p_n} converges to p.. p is limit of {p_n}. p_n -> p으로 표기.(or lim n->inf p_n = p) not converge -> diverge. set of all {p_n} : range. Theorem. {p_n} is sequence in metric space X.(a) {p_n} converges to p \in X every ..

티스토리툴바