잡글 가득 블로그
article thumbnail
Published 2022. 5. 14. 06:00
2022.05.13 PS 일지 ★ PS 기록들

공통 부분 수열 확장

문제 링크

서브태스크 구성도 좋고, 재미있게 풀었다.

풀이 및 코드

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
profile

잡글 가득 블로그

@도훈.

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!

profile on loading

Loading...