7/1 ~ 7/8 PS

백준 문제풀이

Vermeil 2022. 7. 8. 17:59

백준을 요즘 대충하는 관계로 문제가 느리게 쌓였다. 게임을 줄여야 하는데...

"()))((()" 같은 대칭 여부, 올바른 괄호 문자열 여부를 확인하면 된다. 무지성 N^2.

각 단색광은 독립적이기 때문에, 빨파초 3개를 각각 처리해주어 2-sat을 하면 된다.

정렬 후를 B라고 하면, A_i * B_i가 제곱수여야 정렬 가능한 형태가 된다.

r의 범위가 작으므로, 가능한 모든 순서쌍 \((r_i, r_{i+1})\)에 대해 전처리가 가능하다. 이를 통해 i번째의 약물을 언제 넣어야 할 지를 빠르게 알 수 있다.

MITM 기초문제.

아무 정점에서 가장 먼 거리에 있는 정점 k를 찾는다. 그리고 이 정점에서 가장 먼 거리에 있는 정점을 x라고 하면, k~x의 거리가 트리의 지름이 된다.