제3회 보라매컵 본선 Open Contest

두 병사의 스케줄을 맞바꾸는 횟수에 제한이 없으므로, 원하는 만큼 근무 스케줄을 수정하면 각 병사들의 근무 일자를 마음대로 바꿀 수 있습니다.

이때, 임의의 병사의 근무 횟수가 $\lceil \frac{N}{2}\rceil$회보다 많은 경우 어떻게 배치해도 연속하여 근무하지 않도록 스케줄을 변경할 수 없으므로, 병사의 근무 횟수가 $\lceil \frac{N}{2}\rceil$회 이하이면 YES, 초과이면 NO를 출력하면 됩니다.

제3회 보라매컵 본선 Open Contest - A - Editorial

두 가지 접근법으로 문제를 해결할 수 있습니다.

## 그래프 중심 풀이

임의의 전화기 A가 전화기 B에 착신전환 되어 있는 상황을 정점 A에서 B로 향하는 유향 간선이 존재한다고 생각하면, 문제 상황을 그래프로 추상화할 수 있습니다. 또한, 전화기가 먹통이 되기 위해선 해당 전화기가 임의의 착신 전환 사이클로 향하는 경로가 존재해야 한다는 사실을 확인할 수 있습니다.

임의의 정점에서 출발하는 간선이 없는 경우 사이클로 향하는 경로가 존재할 수 없음은 자명합니다. 또한, 모든 정점에서 출발하는 유향 간선이 존재하는 함수 그래프는 반드시 사이클을 포함하는 연결 요소들로 구성됩니다. 따라서 단순히 아직 착신전환되지 않은 전화기를 자기 자신을 제외한 임의의 다른 전화기로 착신전환을 걸어 주면 반드시 모든 전화기가 먹통이 된다는 사실을 확인할 수 있습니다.

## 직관적 풀이

만약 착신 전환이 걸려 있지 않은 전화기가 존재한다면, 해당 전화기에 전화를 거는 경우 반드시 전화가 제대로 걸리므로, 착신 전환이 걸려 있는 전화기는 존재하면 안됩니다.

또한, 만약 모든 전화기에 착신 전환이 걸려 있다면 어떤 전화기에 전화를 걸더라도 반드시 다른 전화기로 전화가 걸리고, 결국 전화가 걸리는 전화기가 전혀 없게 됩니다.

따라서, 단순히 착신 전환이 걸려 있지 않은 모든 전화기를 자기 자신을 제외한 다른 전화기로 착신 전환을 걸어 주면 모든 전화기가 먹통이 됩니다.

즉, $a_i = i$인 $i$의 개수가 문제의 정답이 되며, 최종 착신 전환 상태는 $a_i = i$인 경우에 대해서 $i=1$이라면 $2$, 아니면 $1$을 출력하는 등의 방식으로 구현할 수 있습니다.


제3회 보라매컵 본선 Open Contest - B - Editorial

$N$개의 오염 물질을 모두 정화하기 위해 필요한 최소 제독제의 양에 대해 생각해보면, 이 경우 모든 오염 물질의 오염도의 합만큼의 제독제는 반드시 필요하므로 이동 중 흘러내릴 제독제의 양을 최소화하는 것이 반드시 최적입니다. 그리고 흘러내릴 제독제의 양을 최소화하는 방법은 반드시 수직선 상에서 위치가 작은 순서대로 정화하는 방법과 위치가 큰 순서대로 정화하는 방법 둘 중 하나가 되어야 함은 자명합니다.

$N$개의 오염 물질을 위치가 작은 순서로 정화할 때 필요한 제독제의 양을 $L$, 큰 순서로 정화할 때 필요한 제독제의 양을 $R$이라 하면, 이 두 값을 활용하여 $i$번째 오염 물질을 정화하지 않고 나머지 $N-1$개의 오염 물질을 정화하기 위해 필요한 최소 제독제의 양을 빠르게 구할 수 있습니다.

오염 물질의 위치를 오름차순으로 봤을 때, 위치 상 $i$번째 오염 물질을 제외하고 나머지를 정화하기 위해 필요한 최소 제독제의 양을 $f(i)(1 \leq i \leq N)$라 하겠습니다.
- $1<i<N$일 때, $f(i)=\min(L-(p_i+x_N-x_i), R-(p_i+x_i-x_1))$

$i=1, N$인 $f(i)$에 대해서는 제독 시작, 종료 위치가 달라짐에 유의해야 합니다.
- $f(1)=\min(L-(p_1+x_N-x_1), R-(p_1+(N-1)(x_2-x_1)))$
- $f(N)=\min(L-(p_N+(N-1)(x_N-x_{N-1})), R-(p_N+(x_N-x_1)))$

모든 $f(i)(1 \leq i \leq N)$ 값 중 최솟값이 정답이 되며, 정렬에 의해 총 시간복잡도는 $\complexity{N\log N}$입니다.

제3회 보라매컵 본선 Open Contest - C - Editorial

헌혈을 최소한으로 해서 가산점 M점 이상을 모으는 문제이므로, 이득이 되는 날에 헌혈을 적절히 해서 각 헌혈 횟수별 최대 가산점을 구한 후, 최대 가산점이 M점이 넘는 최소 헌혈 횟수를 구해주면 됩니다.

이때 다음과 같은 $dp$식을 세울 수 있습니다.

- $dp[i][j]$ : $i$일 까지 휴식이 끝나도록 $j$번 헌혈을 할 때 얻을 수 있는 최고 가산점

따라서 다음과 같은 식을 통해 $dp$ 테이블을 채워줄 수 있습니다.
- $dp[i][j] = \max(dp[i - 1][j] + s[i], dp[i - d][j - 1] + A)$


이때 문제의 조건에 따라서 $N$일에도 헌혈을 할 수 있으므로 i의 범위를 $D \le i \le N + D - 1$로 잡아야 하는 것에 주의합시다.

해당 방식으로 문제를 풀어주면 총 시간복잡도 $\complexity{N^2}$만에 답을 구할 수 있습니다.

제3회 보라매컵 본선 Open Contest - D - Editorial

난이도 커브는 문제들을 난이도 오름차순으로 배치할 경우 결국 $x_n - x_1$이 되므로 가장 쉬운 문제와 가장 어려운 문제의 난이도 차가 최소가 되게 하면 됩니다.즉, $x_1$과 $x_n$을 적절하게 잡아 해당 범위 안에 모든 알고리즘 문제가 존재하지 않는다면 범위를 늘려주고, 모든 알고리즘 문제가 존재한다면 범위를 줄여주면 됩니다.

따라서 (문제의 난이도, 문제의 알고리즘 종류)를 오름차순으로 정렬한 뒤, 대회에 낼 문제들 중 가장 쉬운 문제의 번호 $l$, 가장 어려운 문제의 번호 $r$을 잡아줍니다.이후 set등의 자료구조를 통해 $[l , r]$의 범위 안에 모든 종류의 문제가 존재하지 않는다면 $r$을 증가시키고 모든 종류의 문제가 존재하면 $l$을 증가시킵니다.

위와 같이 포인터의 범위를 조정해주면서 해당 범위 내에 모든 종류의 알고리즘이 존재할 때 마다 ($r$번째 문제의 난이도 - $l$번째 문제의 난이도)를 기존의 최솟값과 비교해주며 갱신하면 됩니다.

해당 풀이로 문제를 해결하면 총 시간복잡도는 $\complexity{NK\log{(NK)}}$입니다.

제3회 보라매컵 본선 Open Contest - E - Editorial

주어지는 그래프가 트리라고 가정해 봅시다.

노드의 종류를 2가지, 즉 부대가 주둔하는 노드와 주둔하지 않는 노드로 나누면 효용성은 각 노드에 대해 인접한 노드 중 자신과 다른 서로 다른 노드의 개수를 뜻합니다.
하나의 간선은 서로 다른 두 도시를 연결하므로 간선이 연결하는 두 도시가 다른 종류의 노드일 경우 하나의 간선 당 최대 $1$의 효용성을 얻을 수 있습니다.
이때 그래프가 이분 그래프가 되도록 부대를 주둔시키면 모든 간선에 대해 1의 효용성을 얻을 수 있으므로 총 $N-1$의 효용성을 얻을 수 있고, 이는 간선의 개수와 동일합니다.

이제 실제로 주어지는 그래프를 보면 해당 그래프는 여러개의 연결 요소들로 이루어져 있으며, 각 연결 요소들의 노드의 개수를 $a_i$라고 하면 간선의 개수 역시 $a_i$개 임을 알 수 있습니다. 따라서, 각 연결 요소들은 단 하나의 싸이클을 가진다는 것 역시 알 수 있습니다.
각 연결 요소에 존재하는 싸이클의 길이에 따라 다음과 같이 case를 나눌 수 있습니다.

1. 싸이클의 길이가 $2$인 경우
2. 싸이클의 길이가 짝수인 경우
3. 싸이클의 길이가 홀수인 경우

1.싸이클의 길이가 $2$인 경우, 해당 그래프는 여전히 이분 그래프이지만 추가된 도로가 이미 존재하는 도로와 완전히 동일하므로 추가적인 효용성을 얻거나 잃을 수 없습니다.
따라서 해당 연결 요소는 사실상 트리와 동일한 그래프가 되므로 최적해는 여전히 $a_i - 1$입니다.

2.싸이클의 길이가 짝수인 경우, 해당 그래프는 여전히 이분 그래프입니다.새로 추가되는 하나의 간선에서 $1$의 효용성을 추가로 얻을 수 있으므로 최적해는 $a_i$입니다.

3.싸이클의 길이가 홀수인 경우, 해당 그래프는 이분 그래프가 될 수 없으며, 새로 생긴 간선에서 절대로 효용성을 얻을 수 없습니다. 
새로 생긴 간선은 반드시 부대가 주둔하는 도시끼리, 혹은 부대가 주둔하지 않는 도시끼리 연결하기 때문입니다. 따라서 최적해는 $a_i-1$입니다.

위와 같이 그래프에 존재하는 모든 연결 요소들을 순회하며 case를 나눠 각 연결 요소의 최적해들을 모두 구해서 더해주면 총 시간복잡도 $\complexity{N}$으로 답을 구할 수 있습니다.

제3회 보라매컵 본선 Open Contest - F - Editorial

우선 임의의 박스 그룹을 $j$번 분대가 정리해야 한다고 가정해 봅시다. 그리고 그 박스 그룹의 군수품 개수의 총합을 $s$라 합시다. 해당 분대의 병사들에게 박스 그룹의 군수품을 최대한 공평하게 분배한다면, 분대에 속한 병사 $b_j$명 중 가장 많은 군수품을 정리하게 될 병사가 정리할 군수품의 개수는 $\lceil \frac{b_j}{s} \rceil$개임은 자명합니다.

각 분대가 맡아 정리할 박스 그룹의 상대적인 위치와 가장 많은 군수품을 정리할 병사가 정리할 군수품의 개수를 임의로 정해둔다면, 그 개수에 부합하도록 박스 그룹의 범위를 나눌 수 있습니다. 따라서 다음 결정 문제를 생각해 봅시다.
- 주어진 입력에서, 가장 많은 군수품을 정리할 병사가 정리할 군수품의 개수가 한도 $x$ 이하인 경우를 만들 수 있는가?

해당 결정 문제의 답은 $x$가 특정 값 이상일 때 항상 참이고 특정 값 미만일 때는 항상 거짓이므로, 한도 $x$에 대해 이분탐색을 활용할 수 있으며, 한도 $x$를 초과하지 않으면서 분대별로 맡은 박스 그룹의 범위를 최대한 크게 가져가는 방식으로 결정 문제의 참/거짓 여부를 확인할 수 있습니다.

문제를 제한 시간 내에 해결하기 위해서는 아직 더 최적화해야합니다. 따라서 다음 결정 문제를 생각해 봅시다.
- 어떤 분대가 맡은 고정된 시작 위치를 가진 박스 그룹에 대해, 박스 그룹 범위의 끝 위치가 $y$일 때 박스 그룹을 맡은 분대 내에서 가장 많은 군수품을 정리할 병사가 정리하게 될 군수품의 개수가 한도 $x$ 이하를 만족하는가?

임의의 지정된 $x$에 대해서 이 결정 문제의 답 또한 $y$가 특정 값 이하일 때 항상 참이고 특정 값을 초과할 때는 항상 거짓이므로, 어떤 박스 그룹 범위의 끝 위치 $y$에 대해 이분탐색을 활용할 수 있습니다. 그리고 이 과정에서 누적합을 활용하면 해당 결정 문제의 참/거짓 여부를 $\complexity{1}$에 확인할 수 있습니다.

따라서 총 시간복잡도는 $\complexity{N+M!M\log(5 \times 10^{11})\log(N)}$입니다.

제3회 보라매컵 본선 Open Contest - G - Editorial

$x$축과 $y$축은 서로 독립적이므로, $x$축에 대한 움직임만을 따로 확인해 봅시다.

만약 모든 UFO의 $dx=1$이라면, 해당 문제는 닫힌 구간 $[x_i, \min{(x_i + T - 1, 100\,000)}]$이 $N$개가 주어졌을 때 $x=q_i$를 포함하는 구간의 개수를 구하는 문제로 치환할 수 있으며, 해당 문제는 부분 합 및 imos법을 활용하면 $\mathcal{O}(N + \max(q_i))$의 시간복잡도로 해결할 수 있습니다.

만약 모든 UFO의 $dx=2$라면, 초기 위치의 $x$좌표가 홀수인 UFO와 짝수인 UFO는 이동 중에 서로 만나지 않습니다. 따라서, 홀수 위치에 존재하는 UFO와 짝수 위치에 존재하는 UFO를 서로 그룹으로 묶은 뒤, 각 그룹에 대해 $dx=1$인 풀이와 동일하게 문제를 풀어줄 수 있습니다. 이 경우에도 총 시간 복잡도는 $\mathcal{O}(N + \max(q_i))$입니다.

이를 일반화하면, 만약 모든 UFO의 $dx = K$라면 초기 위치의 $x \mod \lvert K\rvert$가 동일한 그룹끼리 imos법을 활용하여 쿼리를 처리해줄 수 있고, 이 경우 각 그룹에 대해 필요한 연산 횟수는 약 $\max(q_i) \div \lvert K\rvert$회 입니다.

$\lvert dx\rvert$값이 작으면 작을수록 연산 횟수가 더 많아지므로, 최악의 경우는 $\lvert dx\rvert$값이 작으며 $x \mod dx$값이 서로 다른 UFO가 $N$대 존재하는 경우입니다. 이때, 각 $\lvert dx\rvert$값에 따라 존재할 수 있는 서로 다른 $x\mod \lvert dx\rvert$값의 개수는 총 $\lvert 2dx\rvert$개므로, 대략 $2\sqrt{N}$개 정도의 서로 다른 $dx$값들로 서로 다른 $(dx, x\bmod dx)$쌍을 만들 수 있습니다.

$N\leq 100\,000$이므로 x축 이동을 모두 시뮬레이션 할 때 필요한 최대 연산 횟수는 $2\sqrt{N} \times \max(q_i) \simeq317\times100\,000 = 62\,400\,000$회 입니다. 이를 $y$축에 대해서도 연산해 주면, 최대 연산 $124\,800\,000$회로 모든 경우의 수를 순회할 수 있으며, 제한 시간 $3$초 내에 문제를 해결할 수 있습니다.
