mhy908의 PS 블로그 mhy908의 PS 블로그

마지막 APIO가 끝났습니다~~. 생각보다 못해서 별 기대 안하고 있었지만 상을 받게 되어서 놀랐는데, 점수는 9/37/100으로 다른 참가자들이 많이 받은 B문제의 81점도 못받아서 아쉽게 끝난 감이 있습니다. 또 A의 20점을 '끝나기 직전에 긁어야지~'라는 안일한 생각으로 놓친 것도 반성해야 한다고 생각합니다. 대신 C에서 100점을 획득했는데, 정해로 보이는 Small-to-Large를 쓰지 않고 완전히 다른 방법으로 AC를 맞았습니다. 개인적으로 이 방법이 더 직관적이고 코딩도 간단하다고 생각하여 풀이를 소개해보고자 합니다. 문제 설명 N(N

문제 상황은 다음과 같다 : 1) DAG에서 어떤 source vertex s가 주어진다. 2) 특정 간선 (혹은 정점) 하나를 삭제했을 때 도달 가능한 정점의 개수를 모든 간선(혹은 정점)에 대해 구하시오. Naive한 방법은 직접 그래프에서 해당 간선 혹은 정점을 삭제한 후 그래프탐색을 통해 O(VE)정도 시간에 해결하는 것인데, 이를 O((N+M)lgN)정도 시간복잡도에 해결할 수 있게 해주는 것이 바로 Dominator Tree이다. 일단, source vertex에서 시작하는 그래프탐색을 통해, 삭제가 없어도 도달이 불가능한 정점들을 전부 삭제시켜두고 시작하자. 이제부터 언급할 정점들은 모두 s에서 어떤 경로를 통해 접근이 가능하다. 몇가지 정의를 짚고 넘어가자. 1) Dominator 어떤 정..

https://www.acmicpc.net/problem/13138 13138번: Fairies' Sorcery 첫 번째 줄에는 요정의 수 N과 요정이 마법을 쓰는 횟수 M이 주어진다. (2 ≤ N, M ≤ 100,000) 두 번째 줄부터 M-1개의 줄에는 요정들의 마법이 주어진다. '2 P Q'는 P번 요정과 Q번 요정이 마법을 동시에 www.acmicpc.net 두 명의 요정이 마법을 사용하는 것은 상수시간에 처리가 가능하지만, 한명의 요정이 마법을 쓰는 것은 처리가 까다롭다. 파훼법은, 0번 요정을 임의로 추가하여 현재 있는 요정들을 0번을 기준으로 오른쪽으로 읽어온다고 가정하면 한명의 요정이 마법을 쓰는 것은 그 요정과 0번 요정의 위치를 swap하는 연산이 된다는 것이다. 이 순간에 마법을 써서..

정점이 N개인 트리가 주어질 때, 정점들을 적당히 지워 어떤 임의의 두 점 사이의 거리도 K를 넘지 않도록 하게 지우는 경우의 수를 세는 문제이다. N, K≤300000이다. #1. O(NK^2) Tree DP를 통해 세제곱 시간에 문제를 풀어낼 수가 있다. DP[u][a]를 u의 서브트리에 대해, 움직일 수 있는 정점의 최소 깊이가 a이도록 정점을 제거할 수 있는 경우의 수라 정의하자. 당연히 어떤 두 점 사이의 거리도 K를 넘으면 안된다는 조건을 만족하도록 제거하는 것이다. 편의상 모든 경로가 K이하인 것으로 조건을 바꾸고, 입력에서 주어진 K에 -1을 해주도록 하겠다. 이러한 조건 하에서 상태전이는 꽤 직관적이다. 어떤 임의의 정점에 대해 u의 자식 노드를 v1, v2라 하면, DP[u][max(a..

문제를 요약하자면, 트리가 주어지고 각 정점별로 색깔이 주어졌을 때, 각 정점별로 Unique한 정점에 있는 색의 종류를 출력하라는 문제이다. 여기서 어떤 정점 y가 x에 대해 Unique하다는 것은, 임의의 정점 z≠y에 대해서 d(x, y)≠d(x, z)임과 동치이다. 여기서 d(u, v)는 u와 v 사이의 최단 경로의 길이를 뜻한다. Subtask 1 (4점) N≤2000이므로, 모든 정점에 대해 dfs혹은 bfs를 통해 Naive하게 답을 구할 수 있다. 시간복잡도는 O(N^2). Subtask 2+3 (68점) 본인이 접근한 방법으로는 Subtask 2와 3을 푸는데 풀이상 큰 차이가 없어서 한번에 작성하도록 하겠다. 이 문제를 풀기 위해 핵심적인 lemma를 하나 제시하겠다. Lemma 1. ..

꽃들의 가격이 v[1], v[2], ..., v[N]까지 있을때, 이를 최대 K개의 구간으로 분할하여 각 구간에 대한 (구간에 있는 꽃의 개수)*(꽃들의 가격의 합)의 합을 최소화하라는 문제이다. 각 꽃은 정확히 하나의 구간에 포함되어야 하고, 임의의 1≤i

1. Teleporters 각각의 텔레포터를 정점이라 두고, 적당히 간선을 연결하여 그래프를 형성할 것이다. 편의를 위해 각각의 텔레포터를 텔레포터로 들어가는 정점과, 텔레포터에서 나오는 정점의 2개로 분리하도록 하자. 즉 한 쌍의 텔레포터는 4개의 정점으로 표현된다. 또한 시작점과 끝점에도 정점을 각각 하나씩 만들어 주자. 이제 유향 간선으로 정점들을 이어줄 것인데, 각 정점을 2개로 분할하였기 때문에 각 정점의 indegree와 outdegree는 둘다 1이다. 시작점과 끝점은 각각 outdegree와 indegree가 1이다. 이러한 방법으로 이어준 그래프의 컴포넌트들의 모양을 관찰해보자. (1) 각각의 컴포넌트는 단순 사이클이거나 직선이다. pf) 시작점에서 끝점으로 항상 갈 수 있다는 문제의 조..

1. Type Printer 겨울학교에서 문자열 셋을 돌때 나왔던 문제. 간단히 주어진 문자들로 Trie를 구성한다음 트리 순회를 그리디하게 진행하면 된다. 각 노드별로 서브트리에 있는 노드중 가장 깊은 원소의 깊이(=서브트리의 높이)를 전처리한 뒤 그 값이 작은 자식노드쪽부터 재귀함수를 호출하면 된다. 시간복잡도는 Trie의 노드 개수로 O(NS)이다. (S는 각 문자열의 길이) 2. Fish 물고기의 뱃속에서 나올 수 있는 보석의 쌍의 개수를 구하는 문제이다. 이 문제에서 중요한 것은 중복되지 않게 이러한 쌍들을 잘 세주는 것인데, 그러기 위해 몇가지의 관찰을 하자. (1) 각 보석 종류에 대해 가장 길이가 긴 물고기에 대해서만 쌍을 세줘도 된다. pf) 조금만 생각해도 자명한 사실이다. 그보다 짧은..