2026.01.23 problem solving

티스토리 뷰

공부/Problem solving

CCC 2025 S1. Positioning Peter’s Paintings

답은 $2 \min(\max(A, C) + B + D, A + C + \max(B, D))$ 입니다.

$Q = 0$ 인 경우의 풀이를 먼저 정리합시다. 변호사가 종류를 바꾸지 않을 경우, 각 종류에 대해서 덕의 최댓값을 구한 후 이를 합한 것이 정답이 됩니다. 종류를 바꾸게 된다면, 현재 최댓값으로 선정된 업보 중 덕을 최소화하는 것을 빼서, 선정되지 않은 업보로 교체하는 것이 최적입니다. 즉, 이 때 얻을 수 있는 이득은 (최댓값 중 덕 최솟값) - (최댓값 아닌 업보 중 덕 최댓값) 으로 계산할 수 있습니다. 이 이득 값이 $0$ 이상이면, 최댓값의 합에 이를 더해주면 됩니다. 이렇게 하면 모든 계산을 $O(N)$ 시간에 할 수 있으니, 시간 복잡도는 $O((Q + 1) N)$ 입니다.

이를 최적화하기 위해서는, 각 종류 $i$ 에 대해서 해당 종류의 업보들을 덕이 증가하는 순서대로 관리하는 std::set 자료구조를 관리합시다. 또한, 현재 최댓값으로 선정된 업보, 그리고 그렇지 않은 업보들에 대해서도 각각 std::set 자료구조를 관리합시다. 마지막으로, 현재 std::set 에 들어간 업보들의 덕 합도 관리합니다. 이 자료구조들이 모두 관리되면, 문제를 해결하는 데 필요한 모든 정보를 계산할 수 있습니다.

각 업데이트에 따라서, 최대 $O(1)$ 개의 원소가 상태를 바꾸게 됩니다. 업데이트마다 적절히 원소들의 상태를 바꿔주는 것을 구현하면 전체 문제가 $O((N + Q) \log N)$ 시간에 해결됩니다.

NOI 2017 P5. Vegetables

귀중품을 종류별로 취급하지 않고, 각 귀중품 하나 단위로 취급합시다. 이 경우, 각 귀중품은 팔았을 때의 이득과 해당 귀중품이 만료되는 날짜로 표현 가능합니다. 귀중품을 한 개 이상 팔았을 때 얻게 되는 추가금 $S_i$ 는, 만료되는 날짜가 가장 늦은 귀중품의 이득에 더해주면 처리할 수 있습니다. 귀중품의 개수가 너무 많은 문제는 나중에 처리합시다.

떠나는 날짜 $T$ 가 고정되어 있을 경우, 그리디하게 문제를 해결할 수 있습니다. 모든 귀중품을 팔 수 있는지를 효율적으로 판별하는 것은, 각 날짜에 대해서 만료되는 날짜가 가장 이른 귀중품을 반복해서 파는 식으로 판별 가능합니다. 이제 어떤 귀중품을 팔 것인지를 결정해야 하는데, 모든 가능한 귀중품을 이득이 큰 순에서 작은 순으로 순회합니다. 만약 팔기로 결정한 귀중품들의 집합에 현재 귀중품을 포함시켜도 $T$ 일 안에 모든 물건을 팔 수 있다면, 해당 물건을 무조건 파는 것으로 결정할 수 있습니다. 이 알고리즘은 올바르며, 증명은 매트로이드를 포함하여 여러 방법이 있습니다.

이 알고리즘을 단순히 구현하면 시간 복잡도가 큰 것이 문제이니 최적화해야 합니다. 첫 번째로, 모든 귀중품을 팔 수 있는지 여부를 효율적으로 판단해야 합니다. 모든 귀중품을 팔 수 있다는 것은, 모든 날짜 $t$ 에 대해서 만료되는 일자가 $t$ 일 이하인 귀중품이 $Mt$ 개 이하인 것과 동치입니다. 이 조건은 세그먼트 트리를 사용하여 판별할 수 있습니다. 두 번째로, 팔아야 하는 귀중품의 개수가 너무 많아서 일일이 열거할 수 없습니다. 각 종류에 대해서, 해당 종류의 귀중품 중 가장 만료되는 날짜가 늦은 귀중품을 순서대로 뽑는다면, $S_i$ 를 가장 늦은 귀중품에 더했기 때문에 가중치가 높은 순으로도 물건을 뽑게 됩니다. 즉, 현재 해당 종류의 귀중품에 대해서 위 알고리즘이 집합에 귀중품을 추가하지 못했다면, 남은 귀중품들은 만료 일자가 더 짧거나 가격이 더 낮기 때문에 추가하지 못 할 것이며 시도할 필요도 없습니다. 이렇게 각 종류에 대해서 "최적" 의 귀중품만 관리하는 식으로 하면, (집합의 크기) + $n$ 개의 원소에 대해서만 실제로 팔 수 있는지 여부를 체크하게 됩니다. 집합의 크기는 $mT$ 이하이기 때문에, 이렇게 하면 고정된 $T$ 에 대해서 시간 안에 문제를 해결할 수 있습니다.

모든 $d = 1, 2, \ldots, T$ 에 대해서 문제를 해결하기 위해서는, 날짜를 $1$ 일부터 늘려가면서 동일한 알고리즘을 사용합시다. 즉, 각 귀중품을 가중치가 높은 순으로 결정하는 알고리즘을 사용합니다. 각 귀중품을 처리하는 경우는 총 세 가지입니다:

$d$ 일 안에 판매가 가능하다면, 판매하고 다음으로 넘어갑니다.
$d$ 일 안에 판매가 불가능하고, 현재 귀중품을 총 $dT$ 개 판매했다면, $d$ 를 늘린 후 다시 반복합니다.
$d$ 일 안에 판매가 불가능하고, 현재 귀중품을 $dT$ 개 미만으로 판매하였다면, 아무리 날짜를 늘려도 이 종류의 귀중품은 판매가 불가능합니다. 고로 이 종류의 귀중품 전체를 삭제하고 다음으로 넘어갑니다.

이와 같이 해결하면 고정된 $T$ 의 경우와 크게 다르지 않은 방식으로 문제를 해결할 수 있습니다. 시간 복잡도는 $O((mT + n) \log n)$ 입니다.

CEOI 2020. Roads

편의상 $y$ 축에 평행한 선분이 없다고 가정합시다. (실제로는 이 경우 때문에 약간의 케이스가 생깁니다.)

$x$ 좌표가 증가하는 순으로 스위핑합니다. 현재 sweep line에 $k$ 개의 선분이 있다고 하면, 이 선분들은 지금 보고 있는 sweep line을 $k+1$ 개의 구간으로 분할합니다. 목표는, 이렇게 분할된 $k+1$ 개의 구간에 대해서, 이 구간에 있는 임의의 점과 교차 없이 연결해 줄 수 있는 점을 관리해 주는 것입니다. 이를 관리해 주면, 새로 sweep line에 선분이 들어왔을 때, 관리된 점과 해당 선분의 왼쪽 끝점을 연결해 주는 것으로 문제가 해결됩니다.

편의상, $y = -\infty$ 에 평행한 긴 더미 선분을 넣고, Sweep line에 들어있는 각 선분에 대해서 추가로 "해당 선분의 위쪽 ($y$ 좌표 증가하는 방향) 영역에 선분이 들어왔을 때 교차 없이 이어줄 수 있는 점" 정보를 저장합니다. 선분이 삽입 / 삭제 될 때, 다음과 같이 점을 계산할 수 있습니다.

선분 $L$ 이 삽입된다면, 해당 선분이 갈라서 생긴 $2$ 개의 영역에 대해 "교차 없이 이어줄 수 있는 점" 을 $L$ 의 왼쪽 끝점으로 설정
선분 $L$ 이 삭제된다면, 삭제됨으로써 새로 생긴 영역에 대해 "교차 없이 이어줄 수 있는 점" 을 $L$ 의 오른쪽 끝점으로 설정

std::set으로 (선분 교차 판정과 유사하게) sweep line을 관리하면 전체 문제가 $O(n \log n)$ 에 해결됩니다.

BOJ 33742. Bracket Problem Yet Again

$k = 0$ 인 경우를 먼저 해결합시다. 괄호 문자열이 올바르다는 것은 다음 조건과 동치입니다:

열린 괄호와 닫힌 괄호의 개수가 정확히 $n/2$ 개이다.
모든 $1 \le i \le n/2$ 에 대해서, 첫 $2i-1$ 개 괄호 중 최소 $i$ 개의 괄호가 열린 괄호이다.

이 변형된 조건을 사용하면 그리디 알고리즘을 통해서 문제를 해결할 수 있습니다. 문자열의 모든 문자를 닫힌 괄호로 두고, 초기 비용을 $\sum B_i$ 로 설정합시다. 특정 위치의 닫힌 괄호를 열린 괄호로 바꾸기 위한 비용은 $A_i - B_i$ 이니, $1, 3, 5, \ldots, n-1$ 번 위치에서 현재 가능한 선택지 중 최소 비용의 위치에서 닫힌 괄호를 열린 괄호로 전환하면 됩니다. 가능한 선택지를 priority_queue 에 저장할 경우 시간 복잡도 $O(n \log n)$ 에 $k = 0$ 인 경우가 해결됩니다.

$k = 1, 2, \ldots, n$ 를 해결하는 데는 위 알고리즘이 크게 도움이 되지 않는 것으로 보입니다. 대신, $k = i$ 인 해를 사용해서 $k = i+1$ 인 해를 구성하는 방식으로 문제를 접근합니다. $k = i$ 에 대한 임의의 최적해 ($0$ 을 설정한 위치 및 괄호 문자열 배정) 이 주어졌을 때, 다음 두 종류의 연산을 활용해서 $k =i+1$ 에 대한 최적해를 얻을 수 있습니다 (증명은 생략):

특정 위치에 펀치를 가하고, 괄호 문자열을 바꾸지 않음.
특정 위치에 펀치를 가하고, 해당 위치의 괄호를 뒤집은 후, 이에 따라 다른 위치에 괄호 역시 하나 더 뒤집음.

최적해를 얻기 위해서는 비용 차이가 최대인 연산을 찾아서 이를 수행해 주면 됩니다. 가능한 연산의 경우의 수가 $O(n^2)$ 이니 문제를 다항 시간에 해결할 수 있습니다. 이를 최적화해 주기 위해서는:

특정 위치에 펀치를 가하고, 괄호 문자열을 바꾸지 않는 경우는 쉽게 처리할 수 있습니다.
특정 위치에 펀치를 가하고, 두 위치의 괄호를 뒤집었다고 합시다. 두 가지 케이스가 있는데, ) ( 가 ( ) 가 되는 경우, ( ) 가 ) ( 가 되는 경우가 있습니다.
- 첫 번째 케이스를 올바른 괄호 문자열에 적용할 경우 그 결과는 항상 올바른 괄호 문자열이니, 비용 합만 세그먼트 트리 노드에 잘 관리하면 됩니다.
- 두 번째 케이스를 적용할 때는, 두 괄호 사이의 높이가 항상 $2$ 이상이어야만 합니다. 세그먼트 트리 노드에 구간의 괄호 높이 최솟값을 관리하고, 두 괄호 사이의 높이가 최솟값일 때 합치는 것을 금지한 케이스 / 두 괄호 사이의 높이가 최솟값일 때 합치는 것을 금지하지 않은 케이스를 따로 관리해 주면 됩니다. 이 값을 관리하기 위해서는, 특정 괄호가 구간의 왼쪽 / 오른쪽에서 최솟값만 사용해서 도달 가능한지 아닌지의 정보를 저장해야 합니다. 이 부분 때문에 구현이 다소 까다롭습니다.
괄호를 뒤집은 케이스의 경우 구간의 높이가 $+2$ 혹은 $-2$ 되기 때문에, 이를 Lazy propagation으로 처리해 줍니다.

위 풀이를 세그먼트 트리로 구현하면 $O(n \log n)$ 시간에 문제가 해결됩니다. 코치의 코드에서는, 두 노드의 덧셈 연산을 구현하는 부분이 그 외 모든 부분을 합한 것보다 코드 줄이 많습니다.

ICPC 2023 Tehran H. Star Wars

$dp[i][j]$ 를, 현재 흰색 말이 $(i, j)$ 에 있을 때 여기서 이동해서 잡을 수 있는 검은색 말의 최댓값으로 정의합시다. $dp[i][j]$는, $dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]$ 을 사용해서 계산할 수 있습니다. 이 때, 다음 칸이 보드 밖을 벗어나거나 흰색 말을 포함하고 있으면 계산에 포함하지 않도록 유의합시다. 모든 흰색 말이 있는 칸에 대해서 $dp[i][j]$ 의 최댓값을 취하면 됩니다. 시간 복잡도는 $O(nm)$ 입니다.

CEOI 2005. Depot Rearrangement

각 숫자가 정확히 어느 위치에 들어가야 하는지를 정하기가 어렵지만, 각 숫자가 정확히 어느 위치에 들어가야 하는지를 (예를 들어 brute-force 등으로) 알 수 있다고 합시다. 이 경우, 각 수의 초기 위치에서 목표 위치로 방향 간선을 이으면, 사이클의 합집합 형태의 그래프를 얻게 됩니다. 이 경우, 길이 $1$ 의 사이클은 무시해도 되고, 그 외 길이 $l$ 의 사이클은 $l+1$ 번의 작업을 통해서 정렬할 수 있습니다. (예를 들어 길이 $2$ 의 사이클은 $\text{swap}$ 연산의 구현과 동일하게 처리 가능하며, 길이 $3$ 이상도 유사하게 가능합니다.) 여기서 얻을 수 있는 교훈은, 수들은 가능하면 해당 위치에 가만히 있는 것이 좋으며 (길이 $1$ 의 사이클), 만약 해당 수를 이동시켜야 한다면 가능한 적은 "사이클" 을 이루면서 이동시키는 것이 낫다는 것입니다.

배열을 $n$ 개의 길이 $m$ 구간으로 쪼갭시다. 각 구간에서 숫자들은 $0$ 번 등장하거나, $1$ 번 등장하거나, $2$ 번 이상 등장합니다. $1$ 번 이상 등장하는 수들은, 정확히 하나씩 해당 구간에 남겨둡시다. 이렇게 할 경우, 해당 구간을 떠나야 하는 숫자들(의 위치) 와, 해당 구간에 들어와야 하는 숫자들을 알 수 있습니다.

정점 $n + m$ 개의 방향 그래프를 만듭시다. 이 중 $n$ 개의 정점은 각 구간에 대응되고, $m$ 개의 정점은 각 숫자에 대응됩니다. 어떠한 구간이 특정 숫자를 필요로 한다면, 숫자에서 구간을 향하게 방향 간선을 이어주고, 어떠한 구간이 특정 숫자를 버리고 싶다면, 구간에서 숫자를 향하게 방향 간선을 이어줍니다. 그래프의 모든 정점에 대해, indegree와 outdegree가 동일하기 때문에, 각 컴포넌트에 대해서 오일러 투어가 존재합니다. 오일러 투어를 계산한 후, 얻은 사이클에 따라서 각 숫자들을 이동시켜주면 문제가 해결됩니다. 시간 복잡도는 $O(nm)$ 입니다.

CERC 2023 L. Labelled Paths

고정된 $t$ 에 대해서 문제를 해결해 봅시다. $F[v]$ 를, $v \rightarrow t$ 로 가는 모든 경로 중 라벨의 사전순 최솟값으로 정의합시다. $s(v \rightarrow w)$ 를 $v \rightarrow w$ 간선의 라벨이라고 할 때, $F[v] = \min_{v \rightarrow w} (s(v, w) + F[w])$ 라는 점화식이 성립합니다. 다음 점 $w$ 를 고정했을 경우 $w \rightarrow t$ 로 가는 경로 중 사전순 최소만 고려하면 되기 때문입니다.

이 점화식을 단순히 계산하기에는 $F[v]$ 의 길이가 너무 길어질 수 있습니다. 하지만, 문자열 자체를 저장하지 않고, 대신 $F[v]$ 의 최솟값이 나오는 경로를 이루는 각 부분 문자열을 리스트 형태로 저장할 수 있습니다. 각 리스트의 길이는 최대 $O(n)$ 이니, 충분히 저장할 수 있습니다. 두 리스트를 비교하는 것은, 만약 두 부분 문자열이 $S[i_1:i_2], S[j_1:j_2]$ 가 같은지 여부를 $O(1)$ 시간 안에 판별할 수 있으면, 문자열을 왼쪽에서 오른쪽으로 보면서 같은지를 확인하다가, 달라지는 부분문자열의 위치에서 이분탐색을 해서 다른 지점을 찾는 식으로 리스트의 비교를 $O(n + \log k)$ 시간에 구현할 수 있습니다. 임의의 두 부분 문자열이 같은 지는 해싱이나 Suffix Array 등을 사용하여 구현할 수 있습니다.

각 정점 $v$ 에 대해서 리스트 비교 연산을 $deg(v)$ 번 수행해야 하고, 각 비교가 $O(n)$ 시간에 가능하니, 고정된 $t$ 에 대해 문제를 $O(nm)$ 시간에 해결할 수 있습니다. 이를 모든 $t$ 에 대해 반복하면 전체 문제가 $O(n^2 m)$ 시간에 해결됩니다.

PA 2025 4-2. Zbieranie klocków

체스말을 제거할 수 없다는 것은, 체스말이 다음 구조 중 하나에 속한다는 것과 동치임을 증명할 수 있습니다:

체스말로 이루어진 $2 \times 2$ 격자
체스말로 이루어진 계단 형태의 경로 (가로/세로가 반복해서 등장) -- 이 때, 경로의 시작과 끝은 모두 $2 \times 2$ 격자 형태를 이룸.

예를 들어, 아래 네 형태는 위에서 말한 계단 형태의 구조의 예시입니다:

##....     ##....    ....##     ....##
###...     ###...    ...###     ...###
..##..     ..##..    ..##..     ..##..
...###     ...##.    ###...     .##...
....##     ....##    ##....     ##....
           ....##               ##....

이 성질을 활용해서 고정된 체스말에 대해서 $O(k \log k)$ 시간에 문제를 해결해 봅시다. 먼저, 체스말로 이루어진 $2 \times 2$ 격자 (이제부터 박스 라고 부릅니다) 를 입력에서 모두 찾아줄 수 있습니다. 위에서 서술한 계단 구조는 총 $4$ 가지 형태로 분리될 수 있는데, 일단 $y = x$ 방향으로 향하는 계단인지 $y = -x$ 방향으로 향하는 계단인지로 분리할 수 있고, 또한 계단의 홀짝성에 따라서 분리할 수도 있습니다. 예를 들어, $y = x$ 방향으로 향하는 계단의 경우, 계단의 "위쪽" 선을 $y = x + c$ 라고 했을 때 $c$ 의 홀짝성에 따라서 타입을 달리 할 수 있습니다.

이렇게 $4$ 가지 형태로 계단을 분리하면, 박스에 속하지 않으면서 계단에 속하는 모든 체스말은 정확히 한 가지 형태의 계단에만 속함을 알 수 있습니다. 고로, 각 계단에 대해서 답을 구한 다음 이를 합쳐주면 됩니다. 각 계단에 대해서 답을 구하는 것은, 박스에 속하는 두 점을 고정하고, 두 점 사이에 있으며 박스에 속하지 않는 점들이 꽉 찬 형태를 이루는지로 확인할 수 있습니다. 예를 들어, $y = x + c$ 형태의 계단일 경우, $(y - x, y + x)$ 기준으로 박스에 속하는 점을 정렬한 후 $y - x$ 가 같은 인접한 쌍 사이가 "꽉 차있는지" 를 확인할 수 있습니다. 고로, 전체 문제를 $4$ 조각으로 분할한 후, 각 조각에 대해서 점들을 정렬하고, 박스에 둘러쌓인 꽉 찬 구간들에 대해서 구간 길이를 합해주면 문제가 해결됩니다.

쿼리가 들어올 경우:

매 쿼리마다 최대 $O(1)$ 개의 박스가 추가되고 제거됩니다.
두 인접한 박스 사이가 꽉 차있는지는, 좌표 압축 후 BIT를 사용하여 판별할 수 있습니다.
박스에 속하는 체스말이 갱신되는 경우, 인접한 박스 쌍이 최대 $O(1)$ 개 갱신되니, 위 판별을 활용하여 답을 갱신해 줍니다.
박스에 속하지 않는 체스말이 갱신되는 경우, 해당 체스말을 포함하는 박스 쌍이 정확히 한 개 있으니, 이것이 새롭게 계단을 이루는지 아닌지를 판별하면 됩니다.

네 가지 경우를 전부 구현할 필요는 없어서 구현이 생각보다는 간단한 편입니다. 시간 복잡도는 $O((k + q) \log (k + q))$ 입니다.

PA 2025 4-3. Piracka Chciwość

문제가 다소 어려워 보이지만, 모든 선원이 탈락한 시점에서부터 거꾸로 접근할 경우 간단한 다항 시간 풀이가 있습니다. $dp_{i, j}$ 를, 지금까지 $1, 2, \ldots, i$ 번 선원이 탈락했을 때 $j$ 번 선원이 얻게 되는 금괴의 개수 (탈락한다면 $-\infty$) 로 정의합시다. $dp_{i+1, i+2}, dp_{i+1, i+3}, \ldots, dp_{i+1, n}$ 이 모두 계산되어 있다면, 이번에 $i+1$ 번 선원이 제안을 했을 때 각 선원들이 분배안에 찬성하게 하기 위해 지불해야 할 금괴의 개수는 $\max(0, dp_{i+1, j} + a_j)$ 개 임을 알 수 있습니다. 만약 $\lceil \frac{n-i}{2} \rceil$ 명 이상의 선원을 동의하게 할 만큼의 금괴가 없다면, $i+1$ 번 선원은 탈락하고, 나머지 선원들은 $dp_{i+1, j}$ 개의 금괴를 얻습니다. 그렇지 않다면, $i+1$ 번 선원은 지불해야 할 금괴 수가 최소인 $\lceil \frac{n-i}{2} \rceil - 1$ 명의 선원에게 금괴를 나눠주고, 남은 금괴는 모두 자신이 가집니다. 문제 조건에 의해서, 만약 같은 선원이 요구하는 금괴의 수가 동일하다면 번호가 큰 선원을 우선하여 나눠줍니다.

이 풀이는 매 분배안을 계산하기 위해 정렬이 필요하기 때문에, 총 $O(n^2 \log n)$ 시간이 걸립니다. 이 풀이를 개선하기 위해서 필요한 관찰은 다음과 같습니다. $A = \max a_i \le 64$ 라 합시다.

Lemma 1. $i$ 번 선원이 제시하는 분배안에서, $i$ 번 선원을 제외한 모든 선원은 최대 $A$개의 금괴를 받는다.

Proof. $j$ 를 $dp_{i+1, j} \neq -\infty$ 인 첫 $j$ 라고 정의합시다. 즉, $i$ 번 선원이 탈락한다면, $j$ 번 선원이 제시하는 분배안이 승인됩니다. $j$ 번 선원의 분배안에서는 최대 $\lceil \frac{n-j+1}{2} \rceil$ 명이 금괴를 받습니다. 즉, 최소 $\lfloor \frac{n-j+1}{2} \rfloor$ 명이 금괴를 받지 못합니다. $j > i$ 일 경우 $\lfloor \frac{n-j+1}{2} \rfloor \le \lceil \frac{n-i+1}{2} \rceil - 1$ 가 항상 성립하기에, $i$ 번 선원은 (금괴만 충분하다면) $d_j = 0$ 인 선원들에게만 금괴를 제공하는 분배안도 제안할 수 있습니다. 이 제안에서 각 선원이 최대 $A$개의 금괴를 받으니, 실제 제시되는 분배안에서도 각 선원이 최대 $A$개의 금괴를 받습니다. $\blacksquare$

Lemma 1에 따라서, 선원 $j$ 를 제외하고 $d_i \le A$ 가 성립합을 알 수 있습니다. $j$를 예외 케이스로 두고, $(a_i, d_i)$ 에 따라서 각 선원들을 분류합시다. 분배안을 계산하기 위해서는 요구하는 금괴 수가 최소인 $\lceil \frac{n-i}{2} \rceil - 1$ 명의 선원의 집합을 알아야 합니다. 이 집합은 요구하는 금괴의 수가 $k$ 미만인 선원들의 전체 집합 + (요구하는 금괴의 수가 정확히 $k$ 인 선원들 중 인덱스가 높은 선원들의 집합) 으로 표현됩니다. 각 $(a_i, d_i)$ 에 대해, 해당 값을 가지는 선원들을 적당한 자료구조에 저장합시다. 요구하는 금괴의 수가 $0, 1, 2, \ldots, A$ 인 선원의 수를 쉽게 $O(A^2)$ 시간에 계산할 수 있으니, 해당 $k$ 가 무엇인지와, $k$개의 금괴를 요구하는 선원이 몇 명 필요한지를 알 수 있습니다 ($z$ 명이라고 합시다). 이 자료구조가 다음 연산을 효율적으로 지원한다면 문제가 해결됩니다:

$k$ 개의 금괴를 요구하는 선원들 중 인덱스가 높은 $z$ 명의 선원을 골라야 합니다. 대응되는 자료구조가 $A$ 개 있습니다. 각 자료구조에서 특정 값 이상의 원소의 개수 를 빠르게 셀 수 있다면, 이분 탐색을 통해서 문제를 해결할 수 있습니다. 즉, 해당 쿼리가 $O(A \log n)$ 번 필요합니다.
각 $A$ 개의 자료구조에서 인덱스가 큰 선원들은 $k$ 개의 금괴를 받고 작은 선원들은 $0$ 개의 금괴를 받습니다. 이에 따라 자료구조를 인덱스에 따라서 두 조각으로 분할합시다. 분할 쿼리는 $O(A)$ 번 필요합니다.
금괴를 받는 선원들은 $(a_i, d_i)$ 가 모두 $(a_i, d_i + a_i)$ 로 변합니다 ($d_i = -\infty$ 인 경우는 예외 처리 필요). 이를 $O(A^2)$ 번 진행해야 합니다.
금괴를 받지 않는 선원들은 $(a_i, d_i)$ 가 모두 $(a_i, 0)$ 으로 변합니다. 여러 자료구조가 한 자료구조로 합쳐지기 때문에 병합 이 필요합니다. 이를 $O(A^2)$ 번 진행해야 합니다.
마지막으로 $i, j$ 번 선원을 집합에 삽입 해야 합니다. 최대 $O(1)$ 개입니다.

Mergeable segment tree를 사용하면, 각 연산을 $O(\log n), O(\log n), O(1), O(1), O(\log n)$ 시간에 처리할 수 있습니다 (네 번째 연산은 amortized입니다.) 이를 구현하면 전체 문제가 $O(nA \log^2 n + nA^2)$ 시간에 해결되며 AC를 받을 수 있습니다. 필요하지는 않지만, 만약 AC가 나오지 않는다면 추가적으로 다음과 같은 최적화를 진행할 수 있습니다:

첫 번째 쿼리는 $A$ 개의 세그먼트 트리를 타고 내려가는 식으로 $O(A \log n)$ 시간에 구현할 수 있습니다. 이를 구현하면 전체 문제가 $O(nA \log n + nA^2)$ 시간에 해결됩니다.
$d_i \le A$ 이기 때문에, $A$ 개 이상의 분배안을 거친 선원들은 $0$ 개의 금괴를 받는 시점이 언젠가 옵니다. 즉, 최대 $A$ 명의 선원을 제외하면 모든 선원들에 대해서 $d_i$ 는 $a_i$ 의 배수입니다. 이에 따라 서로 다른 $(a_i, d_i)$ 쌍의 수는 최대 $O(A \log A)$ 개가 되어서 전체 문제가 $O(nA \log n + n A \log A)$ 시간에 구현됩니다.
위 관찰에 따라서 $A$ 명의 선원들을 예외처리하면, 1번 / 2번 쿼리에서 고려해야 할 자료구조의 개수는 $k$ 의 약수 뿐입니다. 이에 따라 전체 문제가 $O(n \sqrt A \log n + n A \log A)$ 시간에 해결됩니다.

IOI 2025 Day 2 (0)	2025.08.12
IOI 2025 Day 1 (0)	2025.08.08
2025.07.05 problem solving (0)	2025.07.06
2025.01.05 problem solving (0)	2025.01.06
Faker's algorithm (1)	2024.11.18

구사과

티스토리 뷰