2020/04/30 ~ 2020/05/03

2020/04/30

갑자기 맞이한 연휴의 첫날이다. 이번 연휴에는 IOI 복습 및 풀이 정리, flow 기본 공부, solved.ac 클래스 9 달성, 학교 숙제 정도를 목표로 잡고 하려고 한다. 오늘은 문제만 그냥 계속 풀었다. 다이아 5, 4, 3, 1 문제를 풀어서 어느 정도는 많이 한 것 같다.

 

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

11992번: Circular Barn (Platinum)

기본적인 CHT 문제였다. 원형이니 선형으로 푸는데 $O(N)$, 각 선형 구조에 대해서 $O(NK)$의 DP를 돌리면 되고, 이 과정에서 $O(1)$ CHT를 이용하면 된다.

 

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

16124번: 나는 행복합니다

Lazy Propagation 을 이용하면 된다. 각 숫자마다 이 구간에서 나온 값에 $10^i$를 곱해서 10개짜리 배열을 관리하고, 변환 쿼리가 들어올 때마다 $i->f(i)$의 일대일 함수를 합쳐준다고 생각하면 된다. lazy propagation의 핵심인 구간 업데이트를 여러 번 합치고 그 구간에 적용해 주는 것을 빨리 해야 하니까 이 과정을 10번의 연산으로 잘 생각해주면 된다.

 

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

3408번: Non-boring sequences

이문제도 딱히 많이 고민할 필요 없이 오른쪽부터 하나씩 훑어 가며 POI Necklace 문제와 같이 가능한 왼쪽 구간끝에 대한 segment tree를 관리하면 된다. 문제에서 unique한 수가 하나는 있어야 한다는 조건이 있으니 minimum segment tree가 0인지 아닌지 확인하면 된다.

 

https://oj.uz/problem/view/JOI13_synchronization

문제 보기 - 동기화 (JOI13_synchronization) :: oj.uz

https://arnold518.tistory.com/entry/JOIOC13-Synchronization

 

2020/05/01

오늘은 개인 사정으로 공부할 시간이 없었다. 그래도 플로우 기본 이론, MCMF, 포드 폴커슨, 에드몬드 카프 정도의 이론은 공부했고, 다이아 5 한문제 풀긴 했다.

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

16418번: Inversions

첫번째 관찰은, 내가 채워 넣을 수들은 모두 non-increasing 할 것이라는 것이다. 이는 exchange arguments를 이용하면 쉽게 보일 수 있다. 그 다음에는 이제 이미 정해진 값들을 A, 채울 값들을 B라 하면 A-A 인버전을 답에 더하고, 각 후보에 대하여 A-B 인버전의 값을 기록하고, B-B 인버전은 각 수에 대해 나보다 위치는 작고 수가 큰 애들의 수를 기록하고, 이를 위하여 DP식을 세워 보면 $j(i-j)$항이 들어가, CHT를 이용하면 해결해줄 수 있다.

 

2020/05/02

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

8496번: Godzilla

언젠간 풀려고 벼르고 있었던 Incremental SCC문제이다. Incremental SCC를 공부하고, 약간의 응용으로 해결할 수 있었다. SCC의 간선들이 한 SCC에 포함되는 시간을 DnC로 구해준 후, 그 간선의 삭제 시간을 이용하여 Union-Find를 관리하며 indegree=0인 정점들의 수를 세주면 된다.

 

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

8987번: 수족관 3

이와 같은 꼴의 문제는 위에서부터 Cartesian tree와 비슷한 느낌으로 해석할 수 있다. 이 트릭을 이용하는 문제들도 꽤 많다. 이와 같이 가로로 인접한 칸들을 하나의 노드로 묶어 트리로 나타낸다. 이 과정에서는 구간의 최솟값을 찾고 그 최솟값 기준으로 양쪽으로 분할하면 되기 때문에 세그먼트 트리 하나를 관리하면 된다. 이후, 이제 문제는 노드들 중 몇개를 색칠하고, 색칠된 노드의 조상들은 모두 색칠할 때 색칠한 칸들의 값의 합의 최댓값을 구해야 한다.

여기서 정해는 그리디한 관찰이 있는 것으로 알고 있지만, 나는 다르게 풀었다.

일단 dp로 표현하자면 $dp(u, k)$ = u정점의 서브트리에 k개를 선택할 때의 최댓값 이라고 정의하자. 그러면 정점 u가 자식 v1, v2를 가졌을 때 $dp(u, k1+k2) = dp(v1, k1) + dp(v2, k2) + (A[u] \ if \ k1+k2!=0)$ 의 점화식을 갖는다. 이 형태의 점화식은 만약 $dp(u, k)$가 볼록하다는 조건만 있다면 민코프스키 합으로 표현될 수 있는 대표적인 꼴이다. 실제로, 트리의 각 정점을 in vertex, out vertex 로 쪼개고, 유량은 1, 각 vertex사이에 가중치를 간선의 가중치으로 설정하고, 부모로 올라가는 간선들에 무한대의 용량, 0의 가중치를 주고 소스와 싱크에 무한대 용랑의 간선들로 연결하면 MCMF 문제로 변형된다. 이제 Augmenting Path 의 감소성을 생각하면 볼록성이 증명되고, 이제 위에서 언급한 대로 두 컨벡스 헐의 기울기를 관리하는 priority_queue 2개를 small to large를 이용하여 합쳐 주고, 가장 기울기가 큰 선에 $A[u]$를 더해주면 된다. 따라서 전체 dp값들을 관리해줄 수 있고, 전체 시간복잡도는 $O(Nlog^2N)$이 된다.

 

2020/05/03

오늘은 solved.ac 클래스 9 달성을 목표로 풀었다.

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

17762번: Building 2

 

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

14898번: 서로 다른 수와 쿼리 2

구간 내에 서로 다른 수의 개수를 세는 문제는 꽤 유명한 트릭이 있다. 나와 같은 수들 중 나 바로 전에 등장한 수의 위치를 $P_i$로 저장해 놓는 것이다. 그렇다면 구간 속에서 이러한 포인터들이 어떠한 수에 대해서 가장 왼쪽에 있는 것만이 구간 밖으로 튀어 나갈 것이고, 나머지는 다 구간 내에 있을 것이다. 따라서 $l<=i<=r$에 대해 $P_i<l$인 것들의 수를 세주면 되고, 이는 $(i, P_i)$를 평면상에 플로팅 하면 직사각형 속의 점 세기 쿼리이니, PST를 이용하여 해결할 수 있다.

 

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

16670번: King Kog’s Reception

한가지 관찰만 하면 된다. 내가 어떤 시간 t에 들어왔을 때 내 앞에 대기자들 중 $T_{i}+D_{i}+D_{i+1}+...$값들 중 최댓값을 출력하면 된다. 말로 설명하자면 어떤 사람이 들어오고, 그 이후로 밀리는 꼴이 될 것인데, 가장 마지막으로 자기가 들어온 시간에 상담을 받을 수 있는 사람의 입장에서는 상담을 받고 그 뒤에 사람들이 대기 없이 바로 밀려서 상담을 받을 것이니 D값들을 더해주면 된다는 것이다. 이제 저 관찰을 통하여 T의 범위인 $10^6$ 크기의 세그먼트 트리 하나를 관리하면 레이지 연산에 max 쿼리를 이용하여 해결할 수 있다.