재밌었던 DP 모음 - 3, 심심풀이 문제

 

P4. 두 팀으로 나누기

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

 

A가 팀에 속한 사람의 최솟값이 반영된다.

A[i]에 대해 정렬해보자.

 

어떻게 팀을 나누던 반드시 A[1]을 들고 있는 사람이 속한 팀이 존재한다.

 

A를 고정할 것인데, 이미 하나는 고정되어있고

그럼 상대팀의 A를 A[j]로 정한다면

 

일단 상대팀은 j미만의 A[i]를 지닌 친구들을 절대 가질 수 없다.

 

현재 팀 상황은

A[1] * sum(B[1] ~ B[j-1]) / B[j] * A[j] 가 되게 된다.

 

이제 [j+1 ~ N]의 선수들을 잘 배치해서 최소로 만들어주면 되는데

f(i, k) = [i ~ N]의 선수들로 k라는 값을 만들 수 있는가? 라는 함수를 만들어주고

 

f(j+1, k)가 가능한 경우에 대해서

A[1] * (sum(B[1] ~ B[j-1]) +  sum(B[j+1] ~ B[N]) - k) / (B[j]+k) * A[j]

와 같이 두 팀이 분할된다.

 

계산은 O(1)이고 테이블은 총 O(N^2B)번 수정한다.

 

한줄평

처리하기 어려운 A를 먼저 고정하면 그냥 냅색이 된다.

 

---

 

P1. 고인물의 두번째 리듬게임 (추천)

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

 

피버게이지를 직접 들고다니긴 어렵다.

어차피 피버게이지가 차 있지 않은 경우엔 할 수 있는 연산이 하나뿐이다.

1. 현재 노트를 친다.

 

그렇기에 상태를 따로 정의할 필요가 없다.

어차피 결정론적이니까. 

 

이러한 피버가 차있지 않은 상태는 어디까지 가서 멈출까?

당연히 피버가 차면 멈추게된다.

 

따라서 f(i) = i번 노트를 칠 때 피버를 발동할 수 있는 경우의 최댓값으로 정의하겠다.

 

피버가 차는 경우엔 다음의 연산이 가능하다.

1. 현재 노트를 친다.

2. 현재 노트를 치기 전에 피버를 발동한다.

 

1의 경우에는 f(i) = f(i+1) + A[i]로 전이할 수 있다.

2의 경우에는 피버를 키고 치는 것인데

만약 i에서 길이 Y짜리 피버를 켰다면

마지막으로 피버가 적용된 노트 j를 이분탐색으로 구할 수 있다.

 

그 후 j+1부터 피버를 모았을 경우 피버가 모두 모이게 되는 노트 k를 또 이분탐색으로 구할 수 있다.

그러면 f(k+1)로 전이하고 우왕 끝이 아니다.

 

 

2-1. i와 동시에 피버를 켜는 경우

 

2-2. i와 i-1 사이에서 켜는 경우

 

 

만약 B[j+1]이 음수인 경우엔 피버를 j+1한테 적용되지 않는 것이 좋을 수도 있다.

 

따라서 i에서 피버를 켰을 때 마지막으로 적용되는 T[j]의 구간은

[max(T[i]-Y, T[i-1]+Y), T[i]+Y]가 된다.

 

따라서 구간을 만족하는 j에 대해 문제를 풀어줘야 하고, j가 변하면 k도 변할 수 있기에

다시 계산해줘야한다.

 

이러한 j는 amortized O(N)개라서 괜찮긴 한데

시간이 개빡빡해서 k를 투포인터로 구해줘야한다.

 

총 시복은

O(QNlogN)이요

 

한줄평

A[i]를 음수로 줘서 j를 구간으로 만든게 ㄹㅇ 킥이다.

 

---

 

P3. 식당

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

 

일단 모든 구간을 다짤라버리면 답이 N이 되니까 답의 상한은 N이다.

 

f(i) = i번까지 구간에 확정했을 때의 최솟값 으로 정의하자.

 

f(i) = f(j) + n{A[j+1 ~ i]}^2

으로 전이가 된다.

 

f(i)는 단조증가 함수이다.

만약 n{A[j+1 ~ i]}^2를 고정하였다면

해당하는 가장 작은 j를 사용하면 해당 상태에서 가장 작은 값이겠다.

 

n{A[j+1 ~ i]}^2는 i를 넘으면 의미를 잃어버리므로 -> 어차피 상한이 i이니까

n{A[j+1~i]}는 최대 sqrt(i)까지만 보면 된다.

 

그러한 j는 어떻게 찾을까?

 

set에 idx를 넣는다.

idx큰 순으로 뽑으며 새로운 수를 뽑았을때마다 집합의 크기를 늘려준다.

새로운 수인지는 어떻게 아는가?

prv라는 set을 만들어 폐기해야하는 idx들을 넣어준다.

 

현재 set에서 뽑은 idx가 prv에 존재한다면 새로운 수가 아니므로 set에서 삭제해준다.

 

이렇게하면 set에는 항상 최대 M개의 원소만 존재하게 되고,

우리는 M개를 다 보는것도 아니고 sqrt(N)개만 보고 종료시킬거다.

 

따라서 O(Nsqrt(N)logN)으로 문제를 풀 수 있다.

 

한줄평

n{A[j+1 ~ i]}^2를 고정하였을때 j의 단조성으로 전이하는 것이 재밌었다.

 

---

 

D5. 식당

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

 

그냥 하라는 대로 풀어서 내가 어떤 생각으로 풀었는지는 잘 기억이 안난다.

 

아무튼 주요하게 작용하는 것은

나와 같은 언어를 사용하는 사람의 위치에 +1 그렇지 않은 경우에 -1을 한다면

sum([l, x])가 0이되는 가장 큰 l을 찾는 것이 주요하다.

근데 sum([l, x])는 단조성이 없으므로 머지함수를 잘 조작하여 단조성을 만들어준다.

seg[i].mn = i번 구간은 [s, e]를 보고있는데, e를 반드시포함한 구간합에서 최솟값

이는 그냥 세그랑 이분탐색으로 l을 O(log^2(N))으로 찾아낼 수 있다.

 

그러한 l을 찾았다면, x번 위치에 있는 친구는 구간 [l, x]에 있는 애들이 모두 집에 가야 집에 갈수있다.

해당 구간에서 가장 늦게 집에 가는 친구가 바로 x일것이다.

그러면 구간 [l, x]에서 x를 포함한 구간합 중 가장 큰 값이 x가 집에 가는 시간이다.

 

이도 머지함수를 잘 짜면 된다.

 

한줄평

아이보리가 매일 말하는 산을 그리면 쉽게 풀린다.

 

---

 

P2. Count BFS Graph (추천)

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

 

진짜 처음 보는 느낌이라 신선했다.

 

i번 친구의 위치를 배정해줄건데

얘는 i-1번 친구보다는 늦게 방문되어야한다.

 

늦게 방문된다는 것은 무엇인가?

i-1의 부모보다 i의 부모가 늦게 등장해야한다는 것이다.

부모라고 하는 것은 해당 간선이 없어진 경우 순서가 바뀌는 것으로 정의하겠다.

 

부모가 같으면 A[i-1] < A[i]여야 하는거고

 

그러면

f(i, j) = 정점 i의 부모의 등장순서가 j이다.

i의 부모 j가 정해져있을때

i-1의 부모가 j보다 작으면 가능하다.

 

그럼 일단 

부모의 경우는 sum{k < j}(f(i-1, k)) 로 전이가 되고

자식의 경우는 이미 j와의 연결을 확정지었기때문에

2^(i-j-1)개의 자유연결이 가능하다.

 

그 두가지 경우를 곱해주면 전이를 할 수 있고

f(n, *)가 답이 된다.

 

한줄평

진짜 문제 개신박하다. 

 

---

 

P2. LR

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

 

희대의 악마 문제

 

f(d, t) = 구간 [l, l+d]에서 t라는 문자를 사용한다면 사전적으로 몇번째인가?

f(d, 'a') + ... + f(d, t)가 k를 넘는 최소 t를 찾으면 ㄱㅊㄱㅊ

 

그렇게 찾았다면 현재 위치에 t가 박히는거고

그 t보다 작은 걸 사용한친구들한테 내가 째껴지는거니까

용인할수 있는 k값에서 빼준다.

 

그 후에는 구간을 전이해줄건데

내가 이번에 t를 사용한거니

f(l, r)에 대하여

A[l]이 t인경우에 f(l+1, r)로 전이

A[r]이 t인경우에 f(l, r+1)로 전이해주면 된다.

 

그냥 개어려워서 울었음

 

한줄평

생각해보면 짝수싫어수도 같은바이브인데 왜이렇게 못풀었는지진짜모름

 

---

 

P3. Merge Not Sort

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

 

관찰하면

i < j, A[i] > A[j]인 i는

j와 같은 배열에 들어가야할 의무가 있다.

 

내 뒤에 나보다 작은 애가 나온다면 무조건 데려가야함.

그 외에는 다른 조건이 없다.

 

저렇게 분할되는 구간의 개수는 최대 2N개이며

저 구간의 길이의 합을 N으로 만드는 행위만 하면 된다.

 

냅색으로 진행하고 역추적한 뒤 출력하면 끝

 

한줄평

잘못된 신념이 사람을 망친다.