본문 바로가기

분류 전체보기

 (133)
백준 20045번 Trading System 문제 요약 길이 n인 배열이 주어진다. 여기서 최대 연속합 k개를 구해야 한다. n은 최대 25만이고 k는 최대 1만이다. 풀이 여담으로 대회 중에 상수 큰 로그 두개 붙은 풀이 떠올렸다가 짜보지도 못하고 박살났다. ㅜㅜ 배열 a의 누적 합 배열을 $p$라고 하자. [i...j]의 연속합은 $p[j] - p[i-1]$이다. 오른쪽 끝이 고정 됐을 때 가장 큰 연속합은 $p[0...j-1]$중에서 가장 작은 값을 $p[j]$에서 빼준 값이 된다. 그러면 오른쪽 끝이 j인 연속합에서 두번째로 큰 값을 $p[0...j-1]$에서 두 번째로 작은 값을 빼준 값이 된다. 이 점을 고려해서 문제를 풀 수 있다. 먼저 모든 $i$번째 원소에 대해서 $i$번째 원소에서 끝나는 가장 큰 연속합을 뽑느다. 그리고 이것들을..
백준 13538번 XOR 쿼리 문제 요약 다섯 종류의 쿼리를 처리해야 합니다. 배열의 끝에 원소를 하나 추가한다. $A_L \cdots A_R$에서 x와 xor한 값이 가장 큰 $y(=A_i)$를 출력한다. 배열의 끝에서 k개를 제거한다. $A_L \cdots A_R$에서 x보다 작거나 같은 원소의 개수를 출력한다. $A_L \cdots A_R$에서 K번째 수를 출력한다. 쿼리는 최대 50만개가 들어오고, 입력되는 수는 최대 50만이다. 풀이 A의 최대 길이는 50만입니다. 그래서 그냥 50만짜리 배열이 있고 원소가 추가된다고 치면 추가될 자리에 변경이 일어난다고 치고, 삭제 쿼리는 그냥 길이를 줄인다고 생각합시다. 이제 등장가능한 원소의 범위를 커버하는 세그먼트 트리를 만듭시다. $n$번째 원소의 제일 최근 업데이트를 가지고 있는 ..
백준 11012번 Egg 문제 요약 2차원 좌표 상에서 점이 N개 놓여 있습니다. 그리고 직사각형 쿼리가 주어지는데 해당 직사각형 안에 존재하는 점의 갯수를 구해야 합니다. 좌표의 범위는 최대 10만입니다. 풀이 2차원 세그트리를 만들어서 점들을 기록해 놓는다면 $O(log^2MAX), MAX=10^5$로 해결이 가능하지만 이거를 쌩으로 만들어 버리면 메모리가 $O(MAX^2)$가 필요해서 만들 수가 없습니다. 직사각형 쿼리가 $l, r, b, t$로 들어오는데 이 부분에 대한 구간합을 묻는 것과 동일합니다. tree[x][y]를 x좌표가 [0...x]인 점들 중에서 y좌표가 y인 점들의 개수라고 생각합시다. 그러면 해당 쿼리는 tree[r][b...t] - tree[l-1][b...t]를 묻는 것과 같습니다. tree[x]를 ..
백준 7469번 K번째 수 문제 요약 길이 N일 배열이 주어진다. 쿼리로는 [l,r,k]가 주어지는데 이는 배열 a[i...j]에서 k번째 수를 출력하라는 뜻이다. N은 최대 10만이고 쿼리 수는 최대 5000이다. 풀이 먼저 좌표압축을 하자. 좌표압축을 한 좌표들의 길이로 구간 합 세그먼트 트리를 만들도록 하자. a[1]부터 시작해서 a[N]까지 돌면서 a[i]에 해당하는 위치의 원소를 1씩 늘려줍니다. 이 때, 해당 세그먼트 트리를 PST로 만들어서 i번째 원소를 추가했을 때의 세그먼트 트리에 접근이 가능하도록 합시다. a가 [1,5,2,6,3,7,4]라고 하면 아래와 같이 업데이트가 진행되고 색깔이 바뀌는 부분들만 새롭게 노드를 추가하면 됩니다. 이런식으로 세그먼트트리가 갱신된다고 합시다. i번째 원소를 업데이트한 세그먼트 ..
백준 14176번 트리와 소수 데이터추가로 터졌습니다. 문제 요약 크기 N인 노드가 주어진다. 두 노드를 랜덤으로 골랐을 때 두 노드의 거리가 소수일 확률을 뽑아야 한다. N은 최대 10만이다. 풀이 모든 경로 중에서 경로의 길이가 소수인 경로의 개수를 찾는 문제다. 총 경로의 수는 $\frac{N(N-1)}{2}$이므로 소수인 경로의 개수를 찾고 이것으로 나눠주면 된다. rooted tree에서 root와의 거리가 d인 정점들의 개수를 구한다고 하자. 거리가 d인 정점들의 개수를 구하는 것은 트리를 순회하는 것만으로도 충분하다. 이제 서로 다른 서브트리에 두 노드가 위치해서 root를 지나는 경로를 살펴보려고 하는데 이 경로들을 일일이 전부 확인하려면 $O(N^2)$이 걸린다. 그러나, 이는 두 배열에서 수를 하나씩 골라서 합이 특..
백준 13431번 트리 문제 문제 요약 크기가 N인 트리가 주어진다. 처음에 모든 정점은 흰색이다. 다음과 같은 쿼리를 처리해야 한다. x번 정점을 파란색으로 색칠한다. x번 정점과 모든 파란 정점과의 거리의 합을 계산한다. 풀이 다행히도 파란색이 흰색으로 바뀌는 쿼리가 없다. 각 정점에 대해서 다음과 같은 dp값들을 정의하자. $$ dp(i) = \text{i번 노드를 루트로 하는 서브트리에서 i번 노드부터 파란 정점까지의 거리의 합} $$ 이제 1번 쿼리가 들어오면 x번 정점의 부모를 쭉 타고 올라가면서 부모의 dp값에 부모와 x번 정점간의 거리를 더해주면 된다. 그러나, 부모를 타고 가는 횟수는 최대 N-1번이고 트리가 선형으로 존재하고 리프노드부터 순서대로 타고 올라가면 $O(N^2)$으로 시간 초과가 난다. 이를 막기 위해..
백준 5820번 경주 문제 요약 크기가 N인 트리가 주어진다. 이 떄, 트리에 존재하는 경로 중에서 길이가 K면서 이루는 간선의 수가 가장 작은 경로의 간선 수를 출력하라. 만약에 길이가 K인 경로가 없다면 -1을 출력한다. N은 최대 10만, K는 최대 100만이다. 풀이 rooted tree에서 해당 트리에서 root와의 거리가 d인 정점 중에서 그 경로의 간선 수가 가장 적은 경우의 간선 수를 $min\_depth(d)$라고 합시다. 그러면 이러한 $min\_depth$는 각 서브트리를 순회하면서 갱신이 가능하고, 서브트리를 순회하면서 root와의 거리가 d인 정점을 만났을 때, $min\_depth(K-d)$가 초기값이 아니라 갱신이 되어 있는 상태라면 서로 다른 서브트리에서 root를 지나면서 길이가 K인 경로를 발..
백준 13514번 트리와 쿼리 5 문제 요약 크기 N의 트리가 주어진다. 각 정점은 1번부터 N번으로 숫자가 매겨져 있고, 처음의 모든 정점의 색은 검은색이다. 모든 간선의 길이는 1이며, 무방향 간서이다. 다음과 같은 쿼리를 처리 해야한다. i번 정점의 색을 바꾼다. 흰색이면 검은색으로, 검은색이면 흰색으로 i번과 가장 가까운 흰색 정점과의 거리를 출력한다. N은 최대 10만이고, 쿼리 수도 최대 10만이다. 풀이 트리 DP 형식으로 생각을 해봅시다. $$ dp(i)=\text{i번을 루트로 하는 서브트리에서 i번과 가장 가까운 흰색 정점의 거리} $$ 이런 값들을 잘 관리할 수 있다면 2번 쿼리가 들어왔을 때, 쿼리가 들어온 정점의 부모를 타고 가면서 (부모와 정점 간의 거리) + 부모의 dp값을 비교하면서 답을 찾을 수 있을 겁니다..

티스토리툴바