1. 스포일러 방지 구간

문제 요약

공백과 알파벳 소문자와 숫자로만 이루어진 문자열 $s$가 주어진다. $q$개의 구간 $[l_1, r_1], [l_2, r_2], \cdots, [l_q, r_q]$가 주어지고, 이 구간에 포함되는 문자는 스포일러 방지 처리되어 있다.

$1, 2, \cdots, q$번 구간을 순서대로 클릭한다. 구간을 클릭할 때마다 구간에 포함되는 문자의 스포일러 방지가 해제된다. 어떤 단어의 모든 문자가 스포일러 방지 해제될 때마다 다음 조건을 만족하는 서로 다른 단어의 개수를 구해보자.

1. $q$개의 구간에 포함되지 않는 구간에 속하는 단어 집합이 있는데, 이 집합에 포함되지 않는다.
2. 지금까지 클릭한 구간에 포함되는 단어 집합이 있는데, 이 집합에 포함되지 않는다.

풀이

실제 문제는 지문이 좀 더 난해하고 모호했습니다(단어의 공개나 등장이 혼용됨). 단어마다 공개된 문자의 수를 유지하고, 단어가 완전히 공개될때마다 정리한 조건대로 판별합니다.

2. 신호등

문제 요약

$n(n \le 5)$개의 신호등이 $g_i, y_i, r_i (3 \le g_i + y_i + r_i \le 20)$초 씩 초록색, 노란색, 빨간색 신호를 반복해서 표시한다. 모든 신호등이 노란불이 되는 최초의 시각 $t(1 \le t)$를 구해보자.

풀이

$t \le 20^5$초 안에 정답이 존재하기 때문에 $t$초에 모든 신호등이 노란색인지 확인해봅니다. 나머지 연산을 이용하며 구현의 편의를 위해 $t$에서 $g_i$를 뺍니다.

$$(t - 1 - g_i) \mod (g_i + y_i + r_i) < y_i$$

3. 2-3 트리 구성하기

문제 요약

루트 노드는 자식을 한 개만 가지고, 나머지 노드는 자식을 0, 2, 3개만 가질 수 있는 트리를 구성해보자. 분배 노드란 자식이 2, 3개인 노드를 의미하는데, 같은 레벨의 분배 노드는 자식의 개수가 모두 같아야 한다.

분배 노드의 개수는 $d(d \le 10^9)$개 이하여야 한다. 리프 노드마다 루트 노드까지의 경로 상의 분배 노드가 가지는 자식 수들의 곱을 구할 수 있는데, 이 값이 $c(c \le 10^9)$ 이하여야 한다.

이렇게 구성할 수 있는 트리 중 리프 노드 개수의 최댓값을 구해보자.

풀이

못풀었습니다. 수학적으로 접근해야하는 것 같습니다.

4. 파이프 감염

문제 요약

정점이 $n(1 \le n \le 100)$개인 트리가 주어진다. $m$번 정점이 바이러스에 감염되어있다. 간선은 A, B, C 세 종류중 하나인데, 세 종류 중 한 종류를 선택해 파이프를 모두 열어 바이러스가 퍼지게 할 수 있다. 다른 행동을 하기 전에 파이프를 닫아야 한다. 이러한 행동을 $k(\le 10)$ 번 반복했을 때, 감염시킬 수 있는 최대 정점 개수를 구해보자.

풀이

$\mathcal{O}(3^{k} \times n)$ 브루트포스 + 그래프 탐색으로 시뮬레이션

5. 앱 옮기기

문제 요약

$n \times n$ circular 격자에서 $m$개의 앱이 배치되어있을 때 앱 중 하나를 옮기는 $q$개의 행동 시뮬레이션 하기

풀이

못풀었습니다. 구현하면 될 것 같습니다.

6. 패널 해제

문제 요약

$n \times m \times h$ 크기의 격자에서 $k(k \le 15)$개의 패널을 모두 해제하는데 최소 이동 거리. 단, 각 패널을 해제하기 위해서는 선행해서 해제해야 하는 패널이 존재한다.

풀이

패널이 위치한 좌표만 고려해도 최소 이동 거리를 구할 수 있습니다. $\frac{k(k - 1)}{2}$가지 최단 경로를 구하고 현재 해제한 패널 집합을 상태 공간의 정의에 추가해서 그래프 탐색합니다.

선행관계를 간선으로하는 그래프에서 각 패널에서 시작해서 도달할 수 있는 정점 집합을 구합니다. 이 집합은 해당 패널을 방문하기 위해서 이전에 방문해야하는 정점들을 의미합니다.

7. 도로 속도 제한

문제 요약

좌표 평면 위에 $n(n \le 1\,000)$개의 직선이 존재하고 직선의 중심에는 속도 제한 단속 지점이 위치한다. 직선 위에 $m(m \le 100)$개의 도시가 위치할 때, 1번 도시에서 나머지 도시로의 이동할 때 최대 속도를 모두 구한다. 출발할 때의 속도를 그대로 유지한다. 만약 단속 지점이 없다면 속도는 무한대.

한 도로는 어떤 도로와 최대 한 점에서 만난다.

풀이

직선의 길이는 중요하지 않고 모든 좌표간의 상대적인 위치만 중요하므로 좌표 압축을 통해 격자 위에서 그래프 탐색 문제로 바꿉니다. 이때, 도시의 위치, 도로의 시작과 끝, 도로끼리의 교점, 단속 구간을 모두 구해서 좌표 압축해야 합니다.

격자 위에서 인접한 칸으로 이동할 때, 같은 도로거나 교차한 도로여야 이동할 수 있는 것에 유의하여 구현합니다.

좌표 압축 후에는 격자 위에서 bucket queue bfs 등을 통해서 가장 제한 속도가 높은 격자를 우선해서 이동하는 그래프 탐색을 통해 각 도시까지의 최대 속도를 구합니다.