Problem Solving Diary #14

최근 몇 달 동안 SciOI 2023 준비 외에는 PS를 거의 안 했는데, 방학을 맞은 김에 재활용으로 문제 몇 개를 풀어보기로 했다. 랜덤 플래티넘 디펜스를 했다. (곧 SciOI 2023 후기가 올라갈 수도 있을 것 같다.)

BOJ 4284. A Walk Through the Forest

간단한 다익스트라 + DP 문제다. 집에서부터 시작해서 다익스트라를 돌리고, 집에서 거리가 멀어지는 순으로 정점들을 정렬한 뒤 가능한 가짓수를 DP로 계산하면 된다. 시간 복잡도는 $\mathcal{O}(N+M \log M)$이다.

BOJ 29769. 음악회

평균의 최댓값은 수열의 최댓값이다. 즉 수열에서 최댓값이 가장 많이 연속한 구간 중 가장 긴 것 중 가장 왼쪽에 있는 구간을 찾으면 된다. 수열 A 이외에 수열 B를 관리하자. $B_i = j$라는 것은 $A_i = A_{i+1} = \cdots = A_{i+j} \neq A_{i+j+1}$이라는 뜻이다. 즉 $A_i$ 뒤로 연속한 같은 값의 개수를 나타낸다. $A_{N+1}$은 어떤 값과도 같지 않다고 생각하자.

이제 문제는 $(A_i, B_i)$ 중 최댓값과 그 위치를 찾으면 해결된다. $A_i$ 값 하나가 바뀜에 따라 $B$ 값은 어떻게 바뀔까? 구간에 덧셈 또는 뺄셈 처리가 됨을 확인할 수 있다. 즉, 아래와 같은 업데이트와 쿼리를 처리하는 것으로 바꿀 수 있다.

• $A_i$ 변경 업데이트
• $B_i$ 구간 덧셈 업데이트
• $(A_i, B_i)$ 의 최댓값과 그 위치 쿼리

위 연산은 단순한 Lazy Propagation Segment Tree로 모두 처리 가능하다. 시간 복잡도는 $\mathcal{O}(Q \log N)$이다.

세그먼트 트리를 안 쓰고 셋만으로 풀 수도 있다고 한다. 이 풀이가 훨씬 더 쉬운 것 같다.

BOJ 15865. Genetics

$N$개 문자열 중 나머지 모든 문자열 모두와 정확히 $K$자리만 다른 문자열이 있을 때, 그 문자열을 찾아야 한다.

직접 비교는 당연히 무리이다. 무작위화를 이용한 방법을 생각해 보자. 각 문자열에 대해 $W_i$의 랜덤한 가중치를 할당한다. 이후, $i$번째 자리의 문자가 $j$ $(0 \le j < 4)$인 문자열의 가중치 합을 $C_{i, j}$로 계산해 두자. 어떤 문자열 $S$에서, $C_{i, S_i}$의 합을 모두 구했을 때, 만약 이 문자열이 빌런의 DNA라면 이 합은 $MW_i + (M-K)\sum_{j \neq i} W_j$이어야 한다. 이 조건을 만족하지 않는 후보는 모두 제거할 수 있다.

이 과정은 한 번 할 때 $\mathcal{O}(NM)$이 걸리고, 을 후보가 하나 남을 때까지 반복하면 문제를 맞을 수 있다.

BOJ 30397. 대구과학고등학교

$N$과목 중 $A$과목에서 이기고, $B$과목에서 비기고, $C$과목에서 졌다고 해 보자. 이때 과목들의 순서를 바꿀 수 있다면, 내 성적 중 가장 점수가 큰 성적 $A+B$개를 이기거나 비기는 데 사용하고, 상대 성적 가장 점수가 작은 성적 $A+B$개를 상대로 할 것이다.

$A+B$를 고정하고, 이 중 $A$를 최대화하는 방법을 생각해 보자. 이 $A+B$개의 성적에는 이때는 상대 점수가 높을수록 내 높은 점수를 배정하는 것이 가장 이득이다. 모든 위치 관계를 고려했을 때 이 방법이 최선임을 보일 수 있다. 이 전략을 취했을 때 패하는 시험이 하나라도 있다면 이 $A+B$값이 불가능하다는 뜻이다.

이렇게 문제를 풀면 $\mathcal{O}(N^2)$에 문제를 해결할 수 있다.

BOJ 3989. 유행성 독감

오래 고민했으나 자력으로 풀지 못해 풀이를 보았다.

BOJ 20686. Comic Binge

$DP[t][a]$를 현재 두 형제가 책을 읽기 시작한지 $t$만큼의 시간이 지났고, 형이 $a$번째 책을 이제 막 다 읽었을 때, 동생의 최대 진척이라고 하자. 이 DP는 $O(10N^2)$ 에 해결할 수 있다.