Problem Solving Diary #13

BOJ 10848. 팔렘방의 다리

정말 좋은 문제. 직접 풀지 못해서 풀이를 봤는데 놀라웠다. 풀이는 이곳에 적지 않는다.

 

풀이를 보고 나서 든 생각...

요즘 식 정리 문제에서 많이 말린다는 생각이 든다. IOI 2022 Circuit, Goodbye BOj 2022 F도 식 정리 문제였는데 못 풀었고, 식 정리만 하면 쉬운 유형들이었다. 이 문제도 마찬가지인 것 같은데, 문제를 풀면서 복잡한 식 정리를 피해가려는 문제풀이 스타일이 지속적으로 발목을 잡는 것 같다.

 

BOJ 10066. 팰린드롬

팰린드롬 조건이 없었다면 LCP 배열을 구하고 나서 DnC로 풀 수 있다. 그런데 팰린드롬 조건이 있다 보니 이것만으로는 안 끝나고, 구간 내에서 가장 긴 팰린드롬을 구하는 쿼리까지 처리해야 한다. 대략적인 흐름은

• LCP 배열을 구한다.
• 히스토그램 문제를 DnC로 푸는 과정과 비슷하게, 현재 구간에서 최솟값을 잡고 전체 구간을 본다. 이때 이 구간이 의미하는 문자열은 이 구간 길이 + 1번만큼 등장함이 보장된다. 이제 이 문자열에서 가장 긴 접두사 팰린드롬 길이 쿼리를 날리고 답을 갱신한다. 이 과정을 재귀적으로 반복한다.

문제는 저 쿼리를 어떻게 날리는가이다. 일단 팰린드롬과 관련된 쿼리이니 manacher 알고리즘을 사용해야 할 것으로 보인다. manacher 배열 $M$을 얻었을 때, $i - M_i$의 최솟값을 가지고 이분 탐색하는 식으로 짜면 되는데, 이를 위해서 세그먼트 트리를 하나 짜야 한다.

 

BOJ 20062. Seats

핵심 아이디어는 예전에 봐서 알고 있었지만 다른 부분은 하나도 기억이 안 났다. 그런데 그냥 그 스포일러를 알면 나머지 부분은 너무 쉬워서 풀리는 문제였다...

 

BOJ 20080. Simurgh

3번 서브태스크까지의 대략적인 풀이 라인은 이렇다. BCC별로 그래프를 나눈다. 각 BCC에 대해서 그 안에 있는 간선들 중 어떤 간선을 사용해야 하는지를 확정짓기로 하자. 알고 싶은 BCC 하나를 고른 뒤, 나머지 BCC들에서는 그냥 트리가 적당히 되게끔 아무 간선이나 선택한다. 이들은 당분간 계속 고정하고 다른 간선으로 바꿀 일이 없다.

 

이제 선택한 BCC에 대해서, 적당히 아무 간선이나 잡아 트리릏 하나 만든 다음에 앞에서 고정한 다른 간선들과 합쳐 쿼리를 날린다. 그리고, 현재 BCC에 있는 모든 간선을 다 볼 때까지, 다음 과정을 반복한다: 아직 안 본 간선 하나를 선택하고, 그 간선의 양끝점에 해당하는 (현재 골라져 있는 간선으로 이루어진 트리의) 경로상에서 아무 간선이나 하나 제거한다. 이렇게 하면, 최종적으로 모든 간선이 적어도 한 번 쿼리에 들어갔을 텐데, 이 인접한 쿼리들의 결과 차이를 비교해서 각 간선이 포함되는지의 여부를 알 수 있다.

 

Subtask 3을 풀고 나면, BCC 접근은 Full Task에서도 꽤 실효성 있음을 짐작할 수 있다. 이제 할 일은 하나의 BCC 안에서 어떻게 문제를 효율적으로 해결할지 찾는 일이다. 쿼리 횟수의 Scale이 약 $2N \log N$ 정도이기 때문에 이분 탐색을 생각해볼 법 하다. 이를 위해 먼저 완전그래프 Subtask 4를 먼저 생각해 보도록 하자.

 

이분 탐색에 초점을 두고 문제를 생각해 보면, 변을 하나씩 찾아가는 형식의 풀이로 이어지게 된다. 현재 $S$개 점으로 이루어진 간선 $S-1$개의 트리가 있을 때, 이 트리 내의 정점과 트리 밖의 정점을 잇는 새 간선을 아무거나 하나 찾으면 트리 크기를 1 키울 수 있다. 일단 이를 위해서, 먼저 $S$ 내에서 더 이상 간선이 연결되지 않을 점을 제거해 줄 수 있다. 처음에 모든 스타 그래프에 대해서 쿼리를 날려 각 정점의 차수를 알 수 있고, 이를 토대로 정점 연결이 필요한 점 하나를 알 수 있다.

 

이제 이분 탐색을 해야 한다. $S$ 내에서 간선을 찾을 후보 정점을 $X$라 하고, $S$의 정점 여집합을 $S'$라고 하자. $S'$에 점이 짝수 개라면 두 그룹 $A$, $B$로 나눈 뒤, $A$와 $B$의 점들을 한 개씩 간선으로 잇는다. 그리고 ($S$의 간선들 + $A$와 $B$를 이은 간선들 + $X$를 $A$의 모든 점에 이은 간선들)로 쿼리를 날리고, 다시 ($S$의 간선들 + $A$와 $B$를 이은 간선들 + $X$를 $B$의 모든 점에 이은 간선들)로 쿼리를 날린다. 이 둘의 합을 비교해서 $X$가 $A$와 $B$에 각각 몇 개씩의 간선을 남겨두고 있는지 알 수 있다. $S'$에 점이 홀수 개라면 $A$, $B$로 나눈 뒤 점 $C$가 남는데, 점 $C$를 두 쿼리에서 모두 $A$에 붙여 주면 홀짝성에 의거해 $A$와 $B$에 연결된 간선 수는 물론 $X$가 $C$와 연결되었는지까지 알 수 있다. 위 과정을 반복해 주면 된다. 이때 쿼리 횟수는 약 $2 N \log{N} + N$번 정도로 추측할 수 있고, 실제로 계산해 보면 최대 8460번을 쓰게 된다. (상수 단위의 자잘한 최적화가 가능하지만 무시하자.)

 

여기까지 생각하고 풀테는 전혀 진전이 없어서 풀이를 봤다. 아예 다른 방향으로의 아이디어가 하나 필요했고, 그 아이디어를 떠올리면 위와 비슷한 방식으로 처리할 수 있었다. 문제가 잘 안 풀릴 때는 다른 방식으로 생각을 확장해야 한다는 교훈을 얻었다.