문제 링크풀이문제를 보면 두 정점 사이의 최단 거리를 빠르게 구하는 유형이다. 그런데 일반 그래프에서 이건 엄청 어렵다. 따라서 주어진 그래프를 조금 제한적인 형태, 예를 들면 트리로 바꿀 수 있지 않을까 추측해볼 수 있다.그리고 실제로도 주어진 상황을 트리로 변형할 수 있다. 왜 그런지 생각해보면 나름 자명한데, $(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$개라면, 왼쪽에 있는 꼭짓점 ..
1. Cowmpetency먼저 $(a_j, h_j)$ 쌍들이 어떤 형태로 제시될 수 있는지를 생각해 보자. 만약 $a_1 h_1$이면 너무 당연히 모순이 된다. $h_1 사실 상황이 저렇게 되면 $(a_2, h_2)$ 쌍은 존재하는 게 큰 의미가 없다. 그래서 그런 쌍들을 모두 제거하고 생각해도 된다. 이제 남은 쌍들을 생각해 보면, $(a_j, h_j)$ 쌍들을 $a_j$의 크기 순으로 정렬했을 때, 무조건 $h_j \le a_{j+1}$임을 알 수 있다. (여기까지 확인하는 것은 정렬을 한 번 해놓고 적당한 처리로 $O(n \log n)$에 할 수 있다. 자세한 내용은 코드를 참고하자.) 이제 각각의 $(a_j, h_j)$ 쌍에 대해 생각해 보자. $mx[i]$를 $c_1, c_2, \cdots,..