(대충 누군가의 블로그)

일단 이 글은 생성함수함(이하 젠펑), 기댓값 등에 대한 기초 이해를 필요로 합니다.1. 더블카운팅과 기댓값의 선형성사실 둘은 같은 말인데, 기댓값의 선형성에서 전체 경우의 수를 곱하면 더블카운팅이 된다. 25441 디지털 회로문제를 요약하긴 귀찮으니 문제 요약은 하지 않도록(? 하겠다. 사실 식을 정리하면서 얻은 관찰 등이 있지만, 이를 생략하고 가자면결론은 이 문제는 기댓값으로 접근하면 쉽다는 것이다. 당연히 다음과 같은 DP 느낌으로 접근한다.- $DP[i]$ : $i$번째 노드가 1이 되는 경우의 수 이렇게 되면, $DP[i]$는$($자식 중 1개 이상이 1이 되는 경우의 수$) + ($ 2개 이상이 1이 되는 경우의 수$) \dots$가 된다. 이를 다시 정리하면,$ 1 \times ( $ 자식..

교내 동아리 입부시험을 위해 문제 출제를 하게 되어, PS문제를 2개정도 만들게 되었습니다.개인적으로 묻히기에는 꽤 좋은 문제라고 생각해 여기에 후기를 올립니다. 문제에 앞서 ...저희 동아리는 PS동아리가 아닌 관계로 정보 문제를 직접적으로 낼 순 없어서 변형을 좀 가했습니다 ㅋㅋ;;문제 스토리?등도 있지만 설명하면 너무 길어지는 관계로 간단한 요약 설명합니다. 문제 1. 구울$4N$개의 수가 원형으로 배치되어 있습니다. 각 수는 $-1, 0, +1$중 하나이며, $+1$이 정확히 $3N$개 있습니다. 최종 목표는 모든 $+1$의 위치를 찾아내야 합니다. 이를 위해 $3N-1$번의 쿼리를 이용할 수 있습니다. 하나의 쿼리는, 원 위에서 인접한 수들을 골라 그 합을 반환받을 수 있습니다. 풀이더보기먼저 ..

재밌게 푼 문제라 풀이를 적어봅니다. 풀이만 있는게 아니라 잡설도 좀 있을예정 .. 문제 요약 .. ? 은 귀찮으니 안하겠습니다 ㅋㅋ;;    제일 중요한 핵심은 이거라고 생각했습니다.어떤 정점에 대해, 서브트리중 제일 깊은 서브트리를 제외하면 나머지 서브트리에서는 Unique City가 나올 수 없다모든 방향의 Unique City를 계산하면 TLE가 나므로, 깊은 곳을 제외하면 탐색을 최대한 하지 않게 하는게 풀이의 핵심이라고 생각할 수 있습니다. 그래서 지름을 생각했습니다.  저 빨간 친구가 Unique City가 되는 정점들은, 저 빨간 정점의 서브트리 내부 외에는 존재할 수 없습니다. 그래서 서브트리 내부만 잘 계산해주는 느낌이라고 생각했는데,지름 위의 정점은 잘 처리해주기가 힘들었습니다. 저걸..

$+1$과 $-1$로 되어있는 길이 $N$의 수열이 주어집니다. 그리고 $Q$개의 구간쿼리가 들어옵니다.구간쿼리 내용은구간의 수를 앞에서부터 누적합할 때와 뒤에서부터 누적합할 때, 음수가 나오지 않도록 $-1$을 몇 개 제거할 수 있다. 최소 횟수를 구하시오.     풀이앞, 뒤 누적합이 아닌 한쪽 방향만 고려해봅시다. 누적합 그래프를 그려보면, 음수가 되지 않을 조건은 그래프가 처음 시작점보다 아래로 내려가지 않는 것입니다. $-1$을 하나 없애는 것은, 그 이후의 값 전체에 $+1$, 즉 뒤를 들어올리는 것과 같은 연산이 됩니다. 최저점이 0 이상이 될 때까지 끌어올려야 하므로, 시작점, 즉 $l-1$에서의 누적합 최댓값 - $l~r$에서의 누적합 최솟값이 답이 됩니다. 이를 좀 다르게 접근할 수도 ..

코포를 쳤습니다. 생각보다 실력보다 잘 나온 것 같아 기분이 좋아 후기를 써 보려고 합니다 ㅋㅋ;;  A. Kevin and Arithmetic 간단한 케웍이였습니다. $S[i]$를 2로 나눈 나머지가 $i$인 수의 개수라고 하면, $(S[0]?1:0) + (S[0]?S[1]:S[1]-1)$가 답이 됩니다. B. Kevin and Geometry 좀 고생했습니다. 슼보를 보는데 다른분들은 슥삭하는데 저는 풀이가 안떠오르더라고요 ㅋㅋ;; 그래서 그냥 찍었는데 맞았습니다. $a==b$인 제일 큰 $a$를 찾고, 나머지중에서 계차로 남은 두 변을 만들었습니다. 끝나고 알게 된 사실인데 B가 테케가 약해서 $1 5 5 7$을 넣으면 터지는 코드가 많았다고 합니다 ㅋㅋ 다행히도 제꺼는 살았습니다. C. Kevin..

정점 $N$개의 그래프와, 그 그래프 위의 $K-coloring$이 주어집니다. 색 차이가 1 (mod K)만큼 나는 인접한 정점으로 이동해 모든 정점 사이를 이동할 수 있게 새로운 $K-coloring$을 찾으면 됩니다.        단순이 생각해봅시다. $K-coloring$은 $NP$문제입니다. 그러면 입력에서 준 $coloring$을 재활용해야 합니다. 제일 쉬운 방법은 그냥 색 전체에 $+a$를 하는 겁니다. 제 풀이도 이걸 이용합니다. $1$번 정점의 색을 고정시킵니다. 그리고 나머지 전체의 색을 평행이동해, $1$과 어떤 정점이 연결되게 합니다. 그리고 그 둘을 묶어서 생각합니다. 다시 또 평행이동하고, 새로 연결하고를 반복하면 됩니다. priority queue와 imos로 구현할 수 있습..

길이 $N$의 수열 $w_i$가 주어집니다.적절한 인덱스를 골라$1\leq i_1 \leq i_2 \leq i_3 \dots \leq i_k \leq N$$max( ( w_{i_1} + w_{i_2} ) , ( w_{i_2} + w_{i_3} ) \dots , ( w_{i_K} + w_{i_1} ) )$를 최소화시키면 됩니다.       $max(a, b, c)$와 같은 형태이므로 파라메트릭을 사용합시다. 상한을 $x$로 정했다고 생각합시다. 여기서 그리디하게 접근해봅시다. 이때 길이 $K$ 이상의 수열을 구성할 수 있으면 됩니다.가장 작은 원소는 무조건 먹는 것이 이득일 것입니다.그 다음 작은 원소도 무조건 먹는 것이 이득입니다.세 번째 작은 원소는? 현재 수열에$w_1 \dots w_3 \dots w..

$N$개의 정점이 있는 트리 위에, 간선에 가중치가 유향으로 2개씩 붙어있습니다. 즉, $a->b$ 가중치와 $b->a$ 가중치가 따로 붙어있습니다. 어떤 정점을 특별관광도시로 선택하면, 모든 간선의 특별관광도시로 오는 방향의 가중치가 비용에 더해집니다. $K = 1, 2, \dots , N$에 대해, $K$개의 특별관광도시를 선택할 때 비용의 최댓값을 구하시오.물론 한번 가중치가 더해진 간선이 새로 특별관광도시를 선택한다고 가중치가 또 더해지진 않습니다.      $K=1$일 때는 간단히 tree DP로 구할 수 있습니다. $K=2$의 경우는 어떻게 할까요? 신기하게도 이도 tree DP로 구할 수 있습니다.미리 $f(x)=(x하나만 먹었을 때 가중치)$를 계산해둡시다.만약 어떤 정점 $x$를 한쪽 끝..

정점 수가 $N$인 트리가 주어진다. 간선에 방향을 부여해 이동할 수 있는 정점 쌍의 수를 최대화하라.사실 최솟값도 구해야하지만 쉽게 $N-1$임을 알 수 있으므로 생략했습니다.          간선의 방향은 어떤 정점 $r$을 기준으로 어떤 서브트리는 내려가는 방향, 어떤 서브트리는 올라오는 방향으로 하는 것이 최적이다. 증명은 만약 아니라면, 간선의 방향을 바꾸어 증가시킬 수 있다는 것으로 충분합니다.이제 그러면 $r$을 중심으로 나머지 서브트리를 최대한 잘 반띵하는 것이 목표가 됩니다.과연 어떤 정점 $r$을 잡는 것이 이득일까요? $r = cent$일 때 최적해를 가진다 만약 사이즈가 $N/2$보다 큰 서브트리가 있다면, 그 방향으로 한 칸 움직이는 것으로 더욱 최적임을 알 수 있습니다. 그러면 ..

문제는 간단합니다. 수족관을 모든 정점에서 계산하면 됩니다. 당연히 모든 정점에서 다시 DFS를 하면 TLE가 뜹니다. 그렇기 때문에 값을 재활용하는 것을 생각해 볼 수 있습니다. $1$번 정점에서 DFS를 해서 나오는 $pq$와, 그 정점과 인접해있는 $2$번 정점에서의 $pq$의 차이를 생각해봅시다. 사실, $1$번 $pq$에서 $2$개의 원소를 넣고, $2$개의 원소를 빼면 $2$번 $pq$가 됩니다.넣고 빼는 원소는 미리 리루팅 DFS를 이용해 구해줄 수 있습니다.그 후는 DFS를 한번 더 하면서, $pq$를 그 루트 그대로 데려가주면 됩니다.정확히는 $삽입 / 삭제 / 상위 K개 원소 합$ 연산을 수행할 수 있는 새로운 자료구조를 하나 만들면 됩니다.이는 $multiset$을 이용하면 쉽게 구현..