2021-08-27 Problem Solving

요즘도 꾸준히 1일 1문제는 해결하려고 노력 중이다. 지난 번에 글 쓰고 나서 풀었던 문제들 중 일부를 뽑아서 풀이를 올려본다.

17114. 하이퍼 토마토

간단한 BFS를 통해 문제를 해결할 수 있다...만, 11차원 입력을 효율적으로 처리하는 것이 중요한 문제다. 나는 11차원 배열을 선형으로 펴고, 적절한 사칙연산을 통해 11차원 벡터와 선형 배열 인덱스 사이의 변환을 해주는 방식으로 구현했다. 나의 구현 방식으로 문제를 해결하기에는 다소 빠듯한 면이 있어서, 빠른 입출력 등의 여러 최적화를 함께 사용하여 문제를 해결했다.

22967. 구름다리

성게 그래프를 출력하면, 답이 2 이하임이 보장된다. 이제, 답을 1로 만들 수 있는지를 확인해줘야 하는데, 이는 완전 그래프인 경우에만 가능하다. 따라서, $N(N-1)/2 \le 2N-2$ 부등식을 해결하면, $N \le 4$인 경우만 따로 답이 1이 될 수 있는지를 확인해주면 됨을 알 수 있다.

18817. Heroic Heist

$k$번 방 까지 갈 수 있는지를 판별하고 싶다고 하자. 어떻게 할 수 있을까?

 

$k$번 및 그 이전 방들과 그 방들에서 나오는 열쇠를 고려하자. 방들을 왼쪽 노드로, 열쇠를 오른쪽 노드로 하는 이분 그래프를 만들자. 방과 열쇠 사이의 간선은 열쇠가 방 이전에 등장하고, 열쇠로 방을 열 수 있을 때 간선을 잇자. 이 그래프에서 매칭의 크기가 잠겨있는 방의 개수와 같음이 $k$번 방까지 갈 수 있을 필요-충분조건이 된다.

 

이를 이용하여 순차적으로 $k$를 1씩 늘려가며 확인해보든 이분 탐색을 하든 선호하는 방법을 적용하여 문제를 풀면 된다.

4718. Not One Bit More

어떤 수 $X$에 대해, $f(X)$를 $X$에 대해 일어나는 연산의 수로 정의하자. 그러면, $f(X) = f(X\text{의 켜진 비트 수}) + 1$ 이 일반적으로 성립함을 확인할 수 있다.고로, $f(X)$를 $X \le 60$에 대해 전처리 해놓고, 이를 활용해보자.

 

$g(X, k)$를 $X$ 이하의 수들 중 $k$개의 비트가 켜진 수의 개수로 정의하자. 그러면, 문제의 답은

$$\sum_{f(k) = K-1} g(HI, k) - g(LO-1, k)$$

가 된다. $g(X, k)$를 어떻게 구할까? $X$에서 빼도 음수가 되지 않는 최초의 비트를 $2^a$라 할 때, $g(X) = g(X - 2^a, k-1) + {a \choose k}$의 관계식이 성립함을 쉽게 확인할 수 있다.

 

이를 이용하면, 문제를 해결할... 수 없고, 코너 케이스들을 잘 처리해줘야 한다.

21122. Bank Security Unification

앞에서 부터 순차적으로 보면서, 각 $i$에 대해 $i$를 끝으로 하는 문제의 조건을 만족하는 수열의 수를 $D_i$라 정의하면, $O(n^2)$ 정도에 DP를 계산할 수 있다. 여기에서, 유효한 상태전이의 수를 잘 줄이면 되는데... (추후 추가 예정)

14904. 이동하기 2

MCMF를 이용하여 모델링 할 수 있다. 그런데, 다소 까다로운 점은, 어느 정점에서 $A_{i, j}$개의 사탕을 1번 가져갈 수 있고, 이후 방문에는 0개의 사탕을 가져갈 수 있다는 점이다. 이는 정점을 나누어 해결해줄 수 있다. $(i, j)$ 칸에 대해 $in_{i, j}$와 $out_{i, j}$ 두 개의 정점을 만들어주고, $in_{i, j} \to out_{i, j}$ 간선을 유량 1 / 비용 $-A_{i, j}$인 간선과 유량 $K - 1$ / 비용 0인 간선 두 종류로 만들어줄 수 있다. 이러한 기법을 정점 분할 기법이라 하며, 정점 분할을 하면 문제를 해결할 수 있다.