Eau de Cologne
10주차 연습 (2) 본문
P5~D5 정도 난이도 문제를 작성합니다.
https://www.acmicpc.net/problem/23495
23495번: Longest Lyndon Prefix
For each test case, output $n$ integers denoting $l_1, l_2, \dots, l_n$.
www.acmicpc.net
풀이
문자열 $A$와 문자열 $B$의 비교는 뒤에 임의의 문자열 $S$를 붙인 문자열 $AS$와 $BS$의 비교와도 동일합니다. 그렇기 때문에 부분문자열의 suffix를 비교할 때, 전체의 suffix를 비교해도 됩니다.
전체의 suffix array를 구해서 문자열의 rank를 구합니다. 이 이후에는, 모든 rank가 자기 자신보다 큰 부분문자열의 최대 길이를 stack등을 이용해서 구해주면 됩니다.
코드: https://www.acmicpc.net/source/share/24a7dd4429094877afa19efff79b8d99
https://www.acmicpc.net/problem/2311
2311번: 왕복 여행
첫째 줄에 나라의 개수 N과 도로의 개수 M이 주어진다. (3 ≤ N ≤ 1,000, 2 ≤ M ≤ 10,000) 둘째 줄부터 M개의 줄에 걸쳐 각 도로를 나타내는 세 자연수 A, B, C가 주어진다. 이는 A번 나라와 B번 나라가
www.acmicpc.net
풀이
주어진 그래프의 유량을 1, 비용을 간선 가중치로 해서 2만큼 Mincost Maxflow를 돌립니다.
코드: https://www.acmicpc.net/source/share/ed31bff0d5c94699b2502a3491f547f2
https://www.acmicpc.net/problem/5542
5542번: JOI 국가의 행사
예제 1. 3에서 4로 가는 경우는 3-5-4로 이동하면 가장 가까운 축제가 6번이고 거리는 7이다. 이 값이 최대이고, 5에서 2로 가는 경우는 5-3-2, 5-4-2 모두 1번 축제와 거리 5가 되므로 이 값을 출력한다.
www.acmicpc.net
풀이
이후 작성
https://www.acmicpc.net/problem/17670
17670번: 난
난을 공평하게 나누는 방법이 없다면, -1을 첫째 줄에 출력하여라. 공평하게 나눌 수 있다면, 나누는 방법을 나타내는 $N-1$개의 분수 $X_1,\ \cdots,\ X_{N-1}$과 $N$개의 정수 $P_1, \cdots, P_N$을 다음 형식
www.acmicpc.net
풀이
이후 작성
'acmicpc.net' 카테고리의 다른 글
| [08/26] 문제 + 풀이 + 그림 (0) | 2022.08.26 |
|---|---|
| 10주차 연습 (3) (0) | 2022.06.26 |
| 10주차 연습 (1) (0) | 2022.06.26 |
| 9주차 연습 (0) | 2022.06.26 |
| 8주차 연습 (0) | 2022.06.26 |