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

한 지점에 대해 올리거나 내리는 경우가 둘 다 일어나는 경우가 없어도 됨을 적당히 관찰할 수 있다. 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/1741

서로 메신저를 모르는 두 학생은 무조건 같은 반에 배정해주어야 한다. 간단하게 생각하면 완전 그래프에서 주어진 M개의 간선들을 빼고 남은 그래프의 간선들로 Union-Find를 돌리고 싶다. 

하지만 Naive하게 돌리기엔 간선 수가 O(n^2-m)이라 무조건 시간초과가 난다. 

이걸 해결하기 위해 잘 생각해 보면, 연결 상황을 만들기 위해서는 이미 같은 Set에 있는 두 정점 간을 체크하지 않는다면 많아봤자 N-1개의 쌍을 체크함을 알 수 있다. 그리고 그 과정에서 문제에서 주어진 간선들은 선형적으로 방문될것이므로 N+M정도로 시간 내에 돌아갈 것이라고 생각할 수 있다. 

그러면 이미 같은 Set에 있는 두 정점을 체크하지 않기 위한 로직을 짜 보자. 같은 컴포넌트의 경우, 그 컴포넌트 내의 하나의 정점에서 시작해 무조건 완전탐색이 가능하고, 여기서 사용되는 트리 형태의 간선만 체크할 것이다.  

방문하지 않은 정점을 아무거나 골라 BFS같은 그래프 탐색을 돌릴텐데, 처음에 모든 정점을 List에 넣어 놓고, 그래프 탐색 과정에서 방문이 가능하면 다른 정점에서 이 정점을 확인할 필요가 없다는 것이므로 List에서 제거한다. 이렇게 하면 탐색 트리 내의 간선만 체크함이 보장되고, 완전탐색이므로 문제에서 요구되는 연결 상태 역시 보장된다. 정점을 확인할 필요가 없다고 체크하는 시간 복잡도를 최소화하기 위해 연결 리스트를 사용하였다. 

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) 이라고 생각해 볼 수 있다.