냐
공통 부분 수열 확장
서브태스크 구성도 좋고, 재미있게 풀었다.
풀이 및 코드
Subtask #1: $|W|=1$(14점)
자명하다.
왼쪽 확장 경우, 오른쪽 확장 경우로 나눠서 각각 쌍이 존재하는지 확인하면 된다.
하지만 Subtask #2도 충분히 쉬우므로 한번에 긁었다.
Subtask #2: $\sum |X|, \sum |Y| \le 300$(17점)
$W$의 모든 위치에 대해서 문자 $c$를 끼워 넣은 경우에도
여전히 $|X|$와 $|Y|$의 부분 수열이 되는가를 판단하면 된다.
그러면 $\mathcal O(|W|\times |C|\times (|X|+|Y|+|W|))$의 시간이 걸린다.
따라서 대충 $26\times 300^2\approx 2\cdot 10^6$번의 연산으로 통과할 수 있다.
필자의 코드이다.
Subtask #3: $\sum |X|, \sum |Y| \le 2\cdot 10^4$(25점)
아쉽게도 고민해보지 못하고 Fulltask로 넘겼다.
Fulltask: $\sum |X|, \sum |Y| \le 2\cdot 10^5$(44점)
어차피 확장은 문자 단 1개만 추가해도 충분하다.
따라서 누적합으로 선형 시간 전처리 후 구간 속 특정 문자의 개수를 $\mathcal O(1)$에 구할 수 있다.
아이디어는 $W$의 확장되는 위치에 대응되는 $X$와 $Y$에서 최대한 부분 수열을 양쪽으로 벌리는 것이다.
최대한 벌린 상태의 구간에서 특정 문자가 $X$와 $Y$에서 공통으로 존재하는지 여부를 확인하면 문제를 풀 수 있다.
물론, 양쪽으로 벌리는 것은 미리 전처리 해두면 된다.
따라서 시간복잡도는 $\mathcal O(\max \{|X|,|Y|,|W|\times |C|\})$이 되어 통과할 수 있다.
필자의 코드이다.
커플 만들기
좀 어려움
풀이
몇가지 관찰이 필요하다.
일단, 남자 여자를 각각 오름차순으로 정렬한 상태에서 차이의 최소를 만드는 해는 매칭이 꼬이지 않았을 것이다.
왜냐하면 $b_1 < b_2,\ g_1 < g_2$인 상태에서 $|b_1-g_1|+|b_2-g_2| \le |b_1-g_2|+|b_2-g_1|$이기 때문이다. 증명은 약간의 케이스 분류로 쉽게 할 수 있다.
따라서 다음의 점화식으로 계산할 수 있다.
$i=j\to \text{dp}(i,j)=\text{dp}(i-1,j-1)+|b_i-g_j|$
$i>j\to \text{dp}(i,j)=\max \{\text{dp}(i-1,j-1)+|b_i-g_j|, \text{dp}(i-1,j)\}$
$i<j\to \text{dp}(i,j)=\max \{\text{dp}(i-1,j-1)+|b_i-g_j|, \text{dp}(i,j-1)\}$
나누기
이 문제의 대충 비슷한 트리 버전도 있다.
풀이
전체 합을 4로 나눌 수 있다면, 4로 나눈 값을 저장해 그 자리가 나타날 때 잘 DP해주면 된다.
괄호
KOI에서 처음 보는 점수 문제라 기대했지만,
그냥 Fulltask로 풀어서 별 의미가 없었다.
풀이
DP해주면 된다.
string 덧셈이 $\mathcal O(n^2)$번 됐는데 string 길이 상한이 아마 $\mathcal O(\log n)$이라 그런지 돌아간다.
string으로 DP해주는거는 또 처음이라 신기했다.
버스 노선
냐
풀이
2바퀴 펼친 뒤에 직선 스위핑해주면 된다.
개구리 점프
이상한 코드를 내도 맞았다고 뜬다 ㅋㅋ
풀이
사실상 y축과 평행한 방향으로 뚫고 움직일 수 있다고 간주해도 무관하다.
거쳐서 올라가면 똑같기 때문.
이 관찰로 disjoint set 정도 써주면 풀 수 있는데,
없어도 풀린다고 한다.
'PS 기록들' 카테고리의 다른 글
2022.06.05 PS 일지 (0) | 2022.06.06 |
---|---|
2022.06.04 PS 일지 (1) | 2022.06.05 |
2022.05.12 PS 일지 ★ (0) | 2022.05.13 |
2022.05.11 PS 일지 (1) | 2022.05.12 |
2022.05.09 PS 일지 (0) | 2022.05.10 |