목록PS (25)
LoCeL
문제는 여기에서 확인할 수 있다. 방향이 없는 그래프에서 연결 요소는 다음 두 조건을 만족하는 부분그래프이다. 부분그래프 내의 임의의 두 정점을 연결하는 경로가 항상 존재한다. 정점 i에 대해서, i로부터 DFS나 BFS를 수행한다면, 탐색 중에 지나는 모든 정점은 i가 속한 연결 요소의 정점이다. 이 성질을 이용해서 그래프를 탐색하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include using namespace std; int N, M;vector v[1001];bool c[1001]; void bfs(int i) { queue q; q.push(i); while (!q.empty()) {..
문제는 여기에서 확인할 수 있다. 전봇대의 좌표를 $p$의 배수로 통일 시킬 때, 전봇대를 이동시키는 비용은 아래와 같다. $$f\left(p\right) = \sum \left\vert x_i - pi \right\vert$$ 따라서, $f\left(p\right)$를 최소화 시키면 되고, 이는 삼분탐색으로 가능하다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include using namespace std; #define ioinit() ios::sync_with_stdio(false); cin.tie(nullptr);#define INF INT_MAX#define LINF LONG..
문제는 여기에서 확인가능하다. Theorem. $L$을 리프노드의 수라고 하면, 노선수의 최소는 $\lceil L/2 \rceil$이다. Proof. 수학적 귀납법으로 증명이 가능하다. 1. 리프노드를 지웠을 때, 리프노드의 수가 유지되는 경우. 이를 만족하는 리프노드를 $x$라고 하고, 이와 인접한 노드를 $y$라고 하자. 그럼 $x$를 제거했을 때, $\lceil L/2\rceil$이 성립하고, 다시 $x$를 복구 시켰을 때, $y$에서 끝나는 경로를 $x$로 확장하면 된다. 2. 리프노드를 지웠을 때, 리프노드의 수가 유지되지 않는 경우. 차수가 2 이상인 $R$에 대해, 루트를 $R$로 잡고, $R$의 자식이 루트가 되는 서브트리를 두개 고른다. 그러면 리프노드가 항상 2개 이상인데, 두 리프노드..
문제는 여기에서 확인가능하다. A에 담겨있는 물의 양이 $x$, B에 담겨있는 물의 양이 $y$ 일 때, $(x, y)$라고 표현하자. 그럼 $(a, b)$에서 $(c, d)$로 도달하기 위한 작업의 최소 횟수를 BFS로 구할 수 있다. naive하게 생각하면, 탐색공간의 크기가 $100,000^2$으로 매우 크다. 하지만 관찰을 통해서 $x$와 $y$중 하나는 항상 $0$ 또는 물통에 담을 수 있는 물의 최대값이라는 것을 알 수 있으므로, 탐색공간의 크기를 $400,000$으로 줄일 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include using namespace std; typedef p..
문제는 여기에서 확인 가능하다. 수열이 주어졌을때 그 수열의 연속부분수열을 제외한 나머지 수 들의 평균을 최대화하는 문제이다. 제외할 연속부분수열을 기준으로 왼쪽 수열의 평균을 $X$, 크기를 $a$라 하고, 오른쪽 수열의 평균을 $Y$, 크기를 $b$라 한뒤, 일반성을 잃지 않고 $X \geq Y$라 하자. 그러면 다음 부등식이 성립한다. $$\frac{aX + bY}{a+b} \leq \frac{aX + bX}{a+b} = \frac{a+b}{a+b}X = X$$ 따라서 평균을 최대화 하는 수열은 index가 $0$에서 시작하는 연속부분수열이거나, $n-1$에서 끝나는 연속부분수열이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..
Uni-CODE 2019 2019년 11월 2일 토요일에 무사히 온사이트 대회를 개최하였습니다. Uni-CODE 2019 Uni-CODE는 UNIST의 컴퓨터공학/과학 연구 동아리 HeXA에서 주최한 알고리즘 문제해결 대회입니다. 과거 HeXA CTF, HeXA 해커톤 이후로 처음으로 개최된 대회이며, UNIST에서 처음으로 개최된 알고리즘 문제해결 대회입니다. 갑자기 대회 개최? 사실 Uni-CODE는 1학기때만 해도 계획에 없는 대회였습니다. 올해, 대학생의 신분으로 UCPC라는 대회에 처음 나가게 되었는데, 본선 이후에 다른 참가자분들과 대화를 나누는 과정에서, UNIST에는 PS가 잘 알려져있지 않다는 사실이 아쉬웠습니다. 마침 서울권 주요대학이나 KAIST 등에서 PS 스터디나, 대회가 열리는 ..
문제는 여기에서 확인할 수 있다.가장 가까운 점까지의 거리를 $D_{min}$, 가장 먼 점 까지의 거리를 $D_{max}$라 하자.최소화 하고 싶은 것은 $\frac{D_{min} + D_{max}}{2}$이므로, $D_{min} + D_{max}$의 값을 최소화하면 된다.어떤 점에 대해서 두 점 $A$, $B$까지의 거리의 합을 최소화 시키려면, 선분 $AB$위에 점이 놓여 있으면 된다.그리고 $A$가 가장 가까운 점, $B$가 가장 먼 점이 될 가능성을 높이려면, 어떤 점은 $A$위에 놓여있으면 된다.이런 관찰을 하고 나면, 나머지는 완전 탐색을 통해서 주어진 조건을 만족하는 점을 손쉽게 찾을 수 있다. 12345678910111213141516171819202122232425262728293031..
171819 팀으로 UCPC 인터넷 예선에 출전하여, 4솔브 52위로 본선 진출 자격을 얻었다. A, B, I, J를 풀었으며, 나는 J를 해결하였다. 대학 진학 후 처음 출전한 대회인데, 아쉽지만 첫 대회 치고는 만족스러운 결과이며, 공부를 위한 동기부여가 될 수 있었다. 처음 30분 동안은 풀 수 있어 보이는 문제는 없는데, 다른 팀들은 속속 해결하는 모습이 보이고, 문제 해결에 기여할 수 없을 것 같다는 생각이 계속 들어서 멘탈이 깨져있었다. 그래도 어느 하나라도 진득히 잡아보자는 생각으로 J를 잡았고, 1시간 20분 쯤 AC를 받았다. J밖에 풀지 못했지만, 문제 접근을 어떻게 해야하는지 그 느낌을 찾을 수 있었다.
문제는 여기에서 확인 가능하다. 주어진 두 수 $a$, $b$에 대해서 $\sum_{a \leq t \leq b} XCorr(t)$를 계산할 때, $x_i$와 곱해지는 $y_j$들을 생각하자. $p_i = max(0, i+a), q_i = min(n-1, i+b)$라고 하면 $x_i$와 곱해지는 $y_j$들은 $y_{p_i}, y_{p_1+1}, ..., y_{q_i}$가 됨을 알 수 있다. 따라서 구하고자 하는 것을 다음과 같이 바꿀 수 있다.$$\sum_{a \leq t \leq b} XCorr(t) = \sum_{i = 0}^{n-1} {\sum_{j = p_i}^{q_i} {x_i y_i}}$$ 이때 $\sum_{j = p_i}^{q_i} {y_i}$는 전처리를 통해서 $O(\log M)$에 구할..
문제는 여기에서 확인 가능하다. 한 번 플립이 수행될 때 마다, 디스크 하나를 사이에 두고 있는 두 디스크의 위치가 바뀐다. (문제에서의 그림 참고) 전체 디스크의 개수가 홀수이면 항상 검은 디스크와 흰 디스크를 분리할 수 있다. 반대로 디스크의 개수가 짝수라고 하자. 어느 한 디스크부터 시계방향으로 $1$부터 $m+n$까지 번호를 붙이면, 짝수 번호를 가지고 있는 디스크는 짝수 번호의 위치로만, 홀수 번호를 가지고 있는 디스크는 홀수 번호의 위치로만 움직일 수 있다. 두 종류의 디스크 중 흰 디스크가 연속적으로 모여있으면, 검은 디스크도 연속적으로 모여있게 된다. 흰 디스크를 연속적으로 모으는 경우만 고려하자. 흰 디스크를 연속적으로 모을 수 있다는 것은 짝수 번호를 가진 디스크의 수와 홀수 번호를 가..