2024년 5월 PS 일지

지금까지는 임의의 주기로 ps 일지를 작성했지만, 아마 이제부터는 꾸준히 ps일지가 올라올 예정이다. 언제까지 가능할지는 모르겠지만, 5월 셋째주부터 다이아 문제로만 스트릭을 잇는 것을 시도해 보고 있다.

2024년 6월 6일 기준

 

푼 문제 중 풀이가 기억이 나는 문제만 작성했다.

 

15773. Touch The Sky

https://www.acmicpc.net/problem/15773

고도 제약 조건을 다음과 같이 바꿀 수 있다.

• 풍선을 사용했을 때 고도가 $L_i+D_i$ 이하이면 풍선을 사용할 수 있다.

그런데 이 문제는 deadline이 있는 스케줄링 문제와 동치이다. 따라서 deadline 오름차순으로 보면서 해당 풍선을 사용하고, 만약 사용으로 인해 해당 풍선이 deadline을 침범한다면 사용한 풍선 리스트에서 가장 $D$가 큰 풍선의 사용을 취소하는 그리디를 반복하면 최적해를 찾을 수 있다.

 

31818. Discount Event

https://www.acmicpc.net/problem/31818

내가 KAIST 알고리즘 동아리 RUN의 봄 대회에 낸 문제이다. 아마 공식 에디토리얼이 공개될 예정이므로, 여기서는 간단한 풀이만 서술한다.

경로를 세 가지로 나눌 수 있다.

• 지름이 할인 행사가 적용된 정점을 지난다
• 지름에서 할인 행사가 적용된 점 중 가장 가까운 점이 할인 행사가 적용된 정점 중 끝점이다
• 위 두 경우 모두 아닌 경우

두 번째 경우는 dp를 사용해 처리할 수 있다. 각 정점에 대하여 그 정점을 루트로 하는 서브트리만 남겼을 때 정점을 구하는 dp를 짜면 된다.

 

첫 번째 경우와 세 번째 경우는 모두 sparse table로 할 수 있다. 구현 디테일이 좀 복잡하다

 

16182. Dumae

https://www.acmicpc.net/problem/16182

카이스트에서 두메를 시켜먹으면서 푼 문제이다

$u$에서 $v$로 가는 간선이 있다면 $L_v := max \{ L_v, L_u + 1\}$을 시행해도 무방하다. 위상정렬 순서대로 저 연산을 시행하여 모든 $u$에서 $v$로 가는 간선에 대해 $L_v \le L_u + 1$을 만족하도록 해 주자. 마찬가지로 $R_v$에 대해서도 똑같이 해 주자.

 

이제 각 $i$에 대해서 $[L_i, R_i]$ 사이에 있는 정수 하나씩을 겹치지 않게 배정해준다. $R_i$를 정렬하고 하면 된다. 만약 이것이 불가능하다면 해가 없다는 것을 증명할 수 있다.

 

16901. XOR MST

https://www.acmicpc.net/problem/16901

우선 mst에 msb가 켜진 간선이 두 개 이상 사용되었다고 가정하자. 그렇다면 두 간선을 중 한 간선을 제거하고 적절한 간선을 추가하는 방식으로 켜진 msb가 하나가 되는 해를 찾을 수 있다. 이렇게 하면 mst의 가중치가 감소하므로, 결국 mst에는 msb가 켜진 간선이 유일하다는 것을 알 수 있다.

 

따라서 msb가 켜진 집합과 꺼진 집합을 잇는 간선 중 가장 작은 가중치를 트라이로 찾고, msb가 켜진, 꺼진 집합 두 개에서 각각 재귀적으로 mst를 구해서 세 개를 합치면 된다.

 

23778. Lucky Shirt

https://www.acmicpc.net/problem/23778

셔츠들이 여러번 섞이게 되는데, 섞이는 과정의 최대 깊이가 특정한 고정된 값이라고 가정하면, 특별한 셔츠가 어느 위치에 가있을지에 대한 조건부 확률을 계산할 수 있다. (일단 최대 깊이로 섞이고 나면 그 전에 섞였던 것은 중요하지 않고, 특별한 셔츠가 특정 위치로 갈 확률이 다 같으므로 그 뒤로 섞이는 것도 중요하지 않아진다) 따라서 셔츠가 섞이는 최대 깊이에 따라 확률을 계산해 더해주면 된다.

 

28329. 바보 자물쇠

https://www.acmicpc.net/problem/28329

자물쇠의 상태 $S$에 대해 $i$보다 같거나 사전순으로 빠른 문자를 0으로 만들고, 그렇지 않은 문자를 1로 만든 배열을 $S_i$라 하자. $S$를 정렬하기 위해 필요한 최소 연산의 수는 $S_a, S_b, \cdots, S_z$를 정렬하기 위해 필요한 최소 연산 횟수의 합과 같다(zero-one principle). 변경 쿼리가 주어질 때 각 $S_i$에 대한 답은 흔히 금광세그라 불리는 세그먼트 트리로 처리할 수 있다.

 

17689. Candies

https://www.acmicpc.net/problem/17689

MCMF로 생각하면, 다음 두 가지 연산 중 가중치가 큰 것을 계속 반복하는 것이 최적이라는 것을 알 수 있다.

• 선택된 사탕과 인접하지 않은 사탕을 선택한다. (xxx -> xox)
• 선택되지 않은 사탕과 선택되지 않은 사탕이 반복하여 나타나는 부분을 반전한다. (xxoxoxx -> xoxoxox)

두 번째 연산의 경우, 연산을 시행해서 인접한 두 사탕이 선택될 수 있는 경우를 유의해야 한다.

이 과정을 빠르게 하려면 선택되지 않은 사탕과 선택된 사탕이 반복하여 나타나는 부분과, 그 부분을 반전했을 때 더해지는 가중치를 우선순위 큐 등의 자료구조에 저장해두는 것이다.

 

10717. 성벽

https://www.acmicpc.net/problem/10717

다음 두 dp값을 정의하고 계산한다.

$dp1[i][j]$를 $i$행 $j$열에서 오른쪽으로 뻗어나갈 수 있는 길이, 아래로 뻗어나갈 수 있는 길이의 최솟값이라 하자

$dp2[i][j]$를 $i$행 $j$열에서 왼쪽으로 뻗어나갈 수 있는 길이, 위 뻗어나갈 수 있는 길이의 최솟값이라 하자

 

이렇게 하면 각 $k$에 대해서, $i-j=k$를 만족하는 $i$행 $j$열 칸들에 대해 그 칸을 꼭짓점으로 하는 정사각형의 개수를 세그먼트 트리를 사용해 구할 수 있다. 처리가 좀 귀찮다.

 

16214. N과 M

https://www.acmicpc.net/problem/16214

답을 $X$라 하자. 또한, $X \equiv Y (\mod \phi (M))$라 하자.

오일러 정리에 의해 $N^X \equiv N^Y (\mod M)$이다. 따라서, $Y$만 구하면 $X$를 구할 수 있고, 재귀적으로 구하면 된다.

$N$이 $M$의 배수가 되는 등 약간의 예외처리가 필요하다.

 

17668. 시험

https://www.acmicpc.net/problem/17668

$Z \le X+Y$인 경우는 $X$와 $Y$조건만 만족하면 $Z$조건도 자동으로 만족한다. 이는 세그먼트 트리를 사용한 스위핑으로 풀 수 있다.

그렇지 않은 경우는 포함배제를 이용한다.$ | \{ (a, b, c) | a \le X, b \le Y, c \le Z \} | = | \{ (a, b, c) | b \le Y, c \le Z \} |+ | \{ (a, b, c) | a \le X, c \le Z \} | - | \{ (a, b, c) | c \le Z \} | $ 로 쓸 수 있고, 우변의 세 항들은 모두 변수가 2개 이하이므로 마찬가지로 세그먼트 트리를 사용한 스위핑으로 풀 수 있다.

 

1616. 드럼통 메세지

https://www.acmicpc.net/problem/1616

내가 열심히 쓴 설명보다 코드가 더 가독성이 좋다는 것을 발견해서 코드를 대신 올린다.

https://www.acmicpc.net/source/share/bae256814eb34e738037faca9d0cfe87

 

그런데 오일러서킷을 찾아서 푸는 다른 풀이도 있다고 한다. 사실상 동치인 것 같다.

 

19060. Secret Permutation

https://www.acmicpc.net/problem/19060

0, 1, 다른 모든 수 순서로 찾는다.

0: $(i, b, i)$ 쿼리를 넣어 결과가 $a$나 $b$가 아니라면 두 수 모두 0이 아니다. 인접한 수들끼리 쿼리를 넣어 걸러지지 않은 것만 모으자. 이후 모아진 수들에 대해서는 랜덤한 $a, b$를 골라서 $(x, a, b)$가 $b$가 나오는지 확인하여 아니라면 제거하는 방식을 반복해 한 수만 남기면 된다. $p_z =0$이라 하자.

1: $(a, b, z)$를 쿼리로 날려 $a$나 $b$가 아니라면 두 수 모두 1이 아니다. 이후 과정은 0을 찾는 것과 비슷하다. $p_o=1$이라 하자.

 

$(p^{-1}_{i-1}, o, o)$를 쿼리로 날리면 $p^{-1}_{i}$가 결과로 나온다.

 

15977. 조화로운 행렬

https://www.acmicpc.net/problem/15977

행렬의 column정렬해 첫 row를 $1, 2, \cdots , N$으로 맞추어도 좋다. 이렇게 하면 2차원 lis를 푸는 문제가 된다.

이후 lis처럼 dp를 정의하자. $dp[i]$는 $i$로 끝나는 최대길이 체인의 길이이다.

집합 $S_i$를 $dp[x] = i$인 $x$의 점들을 저장하는 집합으로 정의하자. std::set 등의 자료구조를 사용하여, $x$좌표가 증가하면 $y$좌표가 감소하는 점들만 남겨 관리해 주자.

이러면 각 $dp[i]$를 구할 때 이분탐색으로 풀 수 있다. $dp[i] \le x$라면 집합 $S_{x-1}$에 $i$번째 점 왼쪽 아래에 위치하는 점이 있을 것이다.

 

14866. 산만한 고양이

https://www.acmicpc.net/problem/14866

정점을 제거했을 때 몇 개의 컴포넌트로 나뉘는지만 알면 $v-e+f=c$공식을 써서 풀 수 있다. dfs트리에서 한 정점을 제거했을 때 제거된 정점의 자식 서브트리들에 대해 부모 서브트리와 연결되어 있는지 여부를 바탕으로 컴포넌트 개수를 구할 수 있다.

 

19619. 자매 도시

https://www.acmicpc.net/problem/19619

쿼리가 오프라인이라면 답에 대한 이분탐색을 할 수 있다. 한 $x$에 대해 $x$ 이하의 가중치를 갖는 간선만 생각하자.

두 정점이 연결되어 있고 차수가 3인 정점이 있거나 두 정점을 포함하는 컴포넌트가 트리가 아니면 된다.

세 가지 모두 union-find로 할 수 있는데, 쿼리가 온라인이므로 이를 persistent하게 관리하면 된다.

 

16907. 서로 다른 부분 문자열 쿼리

https://www.acmicpc.net/problem/16907

(설명은 아직 작성 중이다)

완성된 문자열을 뒤집은 문자열을 $S$라 하자. 그러면 해야 하는 것은 $S$의 각 suffix들에 대해 suffix에 포함되는 서로 다른 부분 문자열 개수를 구해야 한다.

 

일단 SA와 LCP array를 구해주자. 그러면 $i$번째 suffix에 대한 답을 알고 있을 때 $i-1$번째 suffix에 대한 답을 구할 수 있다.