문제문제를 트리와 쿼리 형태로 생각하면 다음과 같다.초기에, 트리의 각 점에 $K_i$가 쓰여 있다.Relocation: 모든 depth $X_i$ 정점 $v$에 대해, 해당 정점의 $Y_i$ 깊이 조상이 $w$라면 $K_w$에 $K_v$를 더하고, $K_v$를 $0$으로 만든다.Immigration: $K_{A_j}$에 $L_j$를 더한다.Survey: $K_{B_j}$를 출력한다.풀이Subtask 1 (4점)트리가 스타 그래프 형태이므로, 문제가 매우 쉽다. Relocation은 그냥 모든 $K_i$를 루트로 모으는 것과 같고, Immigration과 Survey도 쉽다.Subtask 2 (12점)나이브 $O(NQ)$를 짜면 통과한다.Subtask 3 (25점)모든 정점의 깊이가 $20$ 이하라는 조..
문제 링크풀이문제를 보면 두 정점 사이의 최단 거리를 빠르게 구하는 유형이다. 그런데 일반 그래프에서 이건 엄청 어렵다. 따라서 주어진 그래프를 조금 제한적인 형태, 예를 들면 트리로 바꿀 수 있지 않을까 추측해볼 수 있다.그리고 실제로도 주어진 상황을 트리로 변형할 수 있다. 왜 그런지 생각해보면 나름 자명한데, $(a, b)$에서 $(c, d)$로 이동할 때 다음과 같은 그리디한 전략이 통하기 때문이다.$(a, b)$에서 시작하여, 현재 지점에서 High Jump를 하고 $(c, d)$로 이동할 수 없는 동안, 다음을 반복한다.High Jump를 하고, 도달할 수 있는 점들을 보자.이들 중 높이가 제일 높은 점으로 이동한다.만약 High Jump를 통해 $(c, d)$로 도달할 수 있다면, 이동한다...
문제 링크풀이시작점을 고정했다고 해 보자. 시작점이 WLOG $1$이라고 할 때, 스탬프 $1$과 $2N$을 swap하지 못한다.스탬프 제작소 $2N$개에 각각 $A_1, A_2, \cdots, A_{2N}$의 색 스탬프가 있다고 하자. 이때 모든 도장 카드에 도장을 찍을 수 있는 조건이 무엇일까? 바로 모든 $1 \le i, j \le N$에 대해 $(i, j)$가 $A$에 부분수열로 등장하는 것이다. 그런데 특정 $(i, j)$ 쌍에 대해, $j, j, i, i$ 순으로 배치된 게 아니라면 $(i, j)$는 항상 존재한다. 따라서 찍을 수 없는 스탬프의 수가 $j, j, i, i$ 순으로 배치된 스탬프 $(i, j)$ 쌍의 개수임을 알 수 있다.여기서, 각 스탬프가 두 번 등장하는데, 첫 번째 등장을..
한동안 학교 일로 바빴는데, 앞으로 문제를 더 열심히 풀어야겠다고 생각했다. 원래는 문제 여러 개를 풀고 묶어서 글로 썼는데, 이제부터는 더 문제 수가 적은 글들도 올라갈 것 같다.Subtask 1$N = 4$이고 $L \le 2$턴 안에 해결해야 한다. 처음에 자신이 parent인지 아는 사람은 딱히 문제가 없다. 나머지 사람은 $3$명이 있는데, 이들은 자신을 제외한 두 명에게 parent인지 물어볼 수 있고, 둘 다 parent가 아니라고 하면 질문을 안 해본 한 사람을 고르면 된다. void st1(){ const int n = 4, L = 2; printf("2\n"); for(int P=1; P who (n+1); /// 0: 모름, 1: 맞음, -1: 아님 ..
1. Bessie's Interview먼저 $K$명의 농부에 대해 인터뷰가 끝나는 시간을 priority queue 같은 자료구조로 관리한다고 생각할 수 있다. 그러면 여기서 가장 작은 값을 빼고, 다음 소에게 배정하는 과정을 반복해서 각 소의 인터뷰 시간을 구할 수 있다. 이 과정을 반복하면 Bessie의 인터뷰 시간도 $O(n \log k)$에 구할 수 있다. 여기까지는 쉬운데, 문제는 Bessie가 인터뷰하는 농부의 집합을 찾는 부분이다. Motivation을 대략 적어 보면, Bessie를 인터뷰하기 전에 어떤 소를 인터뷰했을지를 생각해 보자. Bessie가 인터뷰를 시간 $t$에 받는다면, 가능한 농부들은 어떤 소의 인터뷰를 시간 $t$에 끝내는 농부들이다. 그럼 또 그 전에는 어떤 인터뷰를 했..
scpc를 대비하기 위해 문자열 알고리즘을 공부해 보기로 했다. 대표적인 문자열 알고리즘으로는 KMP, 라빈 카프 (해싱), 트라이 등이 있다. Z와 Manacher는 그에 비해서는 조금 덜 유명한 알고리즘이지만, 알아 두는 것이 좋을 것 같아 공부해 두기로 했다. 다음 글들을 참고하였다.Zhttps://cp-algorithms.com/string/z-function.htmlhttps://gina65.tistory.com/29Manacherhttps://ialy1595.github.io/post/manacher/ Z 알고리즘Z 알고리즘이 구하고자 하는 것은 Z array이다. 어떤 길이 $n$인 문자열 $S$의 Z array는 $S$와 $S[i:]$ (모든 접미사)의 최장 공통 접두사 길이로 정의된다. ..
1. Sequence Construction먼저 $K$가 고정되었을 때 가능한 최소의 $M$ 값을 생각해 보자. $K$를 이진수의 합으로 나타낸다. (예를 들어 $13 = 2^3 + 2^2 + 2^0$) 이후 각각만큼의 $1$의 개수를 가지는 이진수들을 $a_i$로 정한다. (예를 들어 $a_1 = 2^8-1, a_2 = 2^4-1, a_3 = 2^1-1$) 이것이 합을 최소화하는 방법이다. 이제 $M$의 최솟값을 알았으니, 그보다 큰 $M$ 값들이 가능할 조건을 생각해 보자. 먼저 같은 수 두 개를 넣는 방법으로 합을 짝수만큼 늘릴 수 있다. 따라서 아까 구한 수보다 짝수만큼 큰 값들은 모두 가능하다. 홀수만큼 큰 값은 어떨까? 일단 $1$과 $2$를 넣는 것으로 xor 값을 안 바꾸면서 합을 $3$ ..
1. Target Practice II먼저 선분들은 기울기가 양수인 것과 음수인 것으로 나눌 수 있다. 이제 사각형의 네 점이 주어졌을 때, 각 점들에 양수 또는 음수 기울기의 선분을 배정해야 한다.위 그림에서 보다시피 오른쪽에 있는 두 꼭짓점 중 위의 것은 음수 기울기, 아래의 것은 양수 기울기를 배정해야 한다. 그러나 왼쪽에 있는 두 꼭짓점은 어떤 기울기로 배정해도 상관없다. 왼쪽에 있는 꼭짓점들에는 어떤 기울기를 배정해야 할까? 생각해 보면, 위/아래 반경을 줄이기 위해서는, 위쪽에 있는 꼭짓점에는 양수 기울기를, 아래쪽에 있는 꼭짓점에는 음수 기울기를 배정하는 것이 좋다. 따라서, 전체 선분 기울기 목록 중 양수 기울기인 것이 $a$개, 음수 기울기인 것이 $4N-a$개라면, 왼쪽에 있는 꼭짓점 ..