씹덕은 특이점의 꿈을 꾸는가?

한 지점에 대해 올리거나 내리는 경우가 둘 다 일어나는 경우가 없어도 됨을 적당히 관찰할 수 있다. 1을 올리는 연산과 -1을 올리는 두 연산이 겹칠 경우, 겹치는 부분의 연산을 지워버리면 둘 이하의 연산으로 재구성할 수 있다. 이걸 관찰하면 적당히 monotone스택을 관리하면서 문제를 해결할 수 있음을 관찰할 수 있다. 

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

문자열을 앞에서부터 볼 때 0에서 1로 바뀌거나 1에서 0으로 바뀌는 경우의 개수를 보자. 중간에서 부분 문자열을 삭제하면 그 개수가 2 감소한다. 

0101->01

0100->00

1101->11 

이런 식이기 때문. 즉, 어떻게 삭제 작업을 수행해도 가운데에서만 수행했다면 주어진 문제를 해결하는 최솟값과 같은 횟수만큼 작업을 수행한다. 문자열을 스택에 쌓으면서 맨 처음을 포함하지 않고 지워야 할 때마다 지워주면 문제가 해결된다. 문자가 바뀌거나, 쌓은 1이나 0이 그 앞의 0이나 1보다 많아지는 지점에서 지우면 된다. 

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

1부터 k까지의 정점들에 대해, 이 정점을 포함하는 사이클이 없도록 그래프를 재구성해야 한다. 

k+1보다 큰 정점들 사이의 간선은 모두 연결해 Union하고, k부터는 사이클이 생기지 않는 간선만 합쳐 준다. (간선에 연결된 두 정점의 분리 집합이 다른 경우) 이보다 많은 간선을 사용하는 방법이 없다는 것은 적당히 생각해 볼 수 있다. 

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

각 지점에서 (A에 의해 방문될 확률)+(B에 의해 방문될 확률)-(두 확률의 곱)의 총합을 구하면 됨을 알 수 있다. (두 사건은 독립이기 때문이다.)

A에 의해 방문될 확률은 A가 이 정점을 방문하는 정점을 고르는 확률이므로, 방문 과정에서 이 정점을 방문하게 되는 정점의 개수를 따져 주면 된다. 이는 자기 자신과 자신의 서브트리 중에서 깊이가 a, 2a, .. 차이나는 정점들이다. 차이가 2a나는 것 부터는 차이가 a나는 것에서 카운트한걸 활용할 수 있으므로 DP를 할 수 있다.

이제 이 DP를 업데이트하는 것은 DFS를 돌면서, 조상 정점들을 저장하는 스택을 관리할 것이다. 자신의 서브트리에 대한 업데이트가 끝나면 a번째 조상에 지금 정점의 값을 업데이트해주면 된다. B에 대해서도 똑같이 하면 된다. 

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

크루스칼과 비슷한 방식으로 스패닝 트리를 따질 것이다. 분리집합을 두 개 생각해 보자. 

먼저 첫번째 유니언 파인드는 빨간 간선을 모두 사용하여 돌린 후 하나의 집합을 만들기 위해 최소 몇개의 파란 간선이 필요한지 확인한다. (아예 스패닝 트리를 만드는게 불가능할수도 있기에 확인해 주자.)

2번째 유니언파인드는 파란 간선만 사용하면서 진행하여 스패닝 트리에 최대 몇개의 파란 간선이 존재할 수 있을지 따져 준다.

푸른 간선의 최소와 최대 사이에 있는 모든 수는 간선을 적절히 선택하여 만들어짐을 생각해볼 수 있기에, k가 범위에 들어오는지만 따져주면 된다. (첫번째 유니언 파인드로 만든 스패닝 트리에 파란 간선을 하나씩 추가하면서 연결성이 유지되게 빨간 간선을 삭제할 수 있다. 이게 불가능할 경우 2번째 유니언파인드에서 체크되기 때문이다)

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

엄밀한 증명은 잘 모르겠고, 루트가 1인 트리를 상상하고 u와 v의 lca 경로를 그린 다음 트리 상에서 r을 여러 개 잡아서 생각해 보았다. r에서 간선을 잘 따라가서 이 경로와 만나는 지점을 찾으면 됨을 알 수 있었다. 다양한 개형을 생각해 본 결과 lca(r, u), lca(r,v), lca(u,v)중 두 값이 같으면 나머지 한 값이 원하는 답이 됨을 확인할 수 있었다. 

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

2197, 2337과 같은 문제. O(n^3)에 푼 것 같다. 

루트를 하나 잡고, 그 지점을 포함하는 트리만을 생각했다. 이게 n^2에 되서, 모든 지점에 대해 반복할 수 있다. 

DP를 하는데, 각 지점에 대해 dp[i][j]를 i번 정점을 루트로 하는 서브트리에서 j개를 잘라내기 위해 필요한 최소 커팅 수로 잡자. 그러면, DFS를 돌면서 dp를 업데이트할 것인데, s라는 정점을 볼 때 그 정점의 서브트리들의 DP값을 알고 있을 것이다. 한번에 합치는 건 힘들고, 각 서브트리의 dp값을 하나하나 보면서 지금까지 본 서브트리로 저장한 dp[s]에서의 dp값과 보고 있는 서브트리 dp[child]에서의 dp값을 잘 조합해서 dp[s]를 업데이트하면 된다.

이렇게 업데이트하면 모순되는 부분 없이 자르는게 가능하다는 걸 생각해 볼 수 있다. 그리고 그 서브트리 전체를 잘라내는 것을 생각해서 dp[i][sz[i]]=1로 두면 된다. 결국 답은 dp[root][n-m]이 된다. 

그리고, 서브트리끼리 DP값을 합쳐나가는 과정의 시간복잡도가 두 서브트리의 크기의 곱으로 나타나기에, O(n^2)이라고 두면 k^2/2 + kl + l^2 이 (k+l)^2이 되어서 귀납적으로 O(n^2) 이라고 생각해 볼 수 있다. 

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

딱봐도 Union-find를 쓰고싶게 생겼다. 

https://justicehui.github.io/usaco/2020/12/04/BOJ6181/

에 나온 것처럼, 45도 돌리면 체비셰프 거리가 된다. x좌표로 스위핑하면서 Set에 y좌표 저장하고, Set 보면서 지금 보고 있는 정점의 Y좌표-D 부터 Y좌표까지 중에서 아무거나와 Union 하고, Y좌표부터 Y좌표+D까지 아무거나와 Union 해주면 된다. 아무거나와 해줘도 되는 이유는 잘 관찰하면 어차피 걔네들끼리 이미 같은 분리 집합에 들어 있다는걸 알 수 있기 때문.