티스토리에 서식이 있는 걸 발견했다. 개꿀
2/5
이 글에 있는 문제 위주로 풀었다.
트리의 색깔과 쿼리를 온라인으로 처리하는 문제이다.
solved.ac 티어
20240205 기준 : Diamond IV (μ = D4 - 0.23, σ = 0.44)
알고리즘 분류
solved.ac : smaller_to_larger, hash_set, tree_set, graph_traversal
작성자 풀이 : smaller_to_larger, tree_set, graph_traversal
풀이
말 그대로 간선을 직접 끊을 것이다. 이를 위해 인접 리스트는 std::set으로 관리한다.
간선을 끊으면 2개의 컴포넌트로 나뉘어질 것인데, 이 중 크기가 더 작은 컴포넌트만 새로 넘버링해주는 방식으로 구현하면 시간복잡도가 보장된다. 끊을 때 걸리는 시간복잡도가 현재 끊을 컴포넌트의 크기의 절반 이하이기 때문이다.
근데 이를 구현하기 위해서는 크기가 더 작은 컴포넌트를 찾아야 하는데, 이를 위해서 2개의 컴포넌트를 모두 검사하면 의미가 없어진다. 그래서 bfs든 dfs든 동시에 수행하면 되는데, 이것도 잘못 구현하면 TLE가 나서 골치 아프다. 진짜 큐에 하나 빼고 하나 넣고를 동시에 해야 되기 때문에 일반적인 dfs/bfs보다 구현이 좀 복잡해진다. 열심히 구현하면 AC를 받는다. 필자는 18트에 맞았다.
참고로 여기서 넘버링 과정만 수행하면 BOJ 13309를 풀 수 있다.
solved.ac 티어
20240205 기준 : Gold II (μ = G2 - 0.04, σ = 0.68)
알고리즘 분류
solved.ac : disjoint_set, graph_traversal
작성자 풀이 : disjoint_set
풀이
팀이 최대가 되려면 필수적으로 묶여야 되는 관계를 빼고는 다 묶지 말아야 한다. 따라서 그러한 관계만 다 찾아주면 된다. 친구-친구는 그냥 union find 상에서 merge와 같다. 한 정점을 기준으로 원수-원수 관계는 아무 원수나 잡고 나머지를 다 merge하면 된다.
아이디어도 그렇고 쩌는 문제이다.
solved.ac 티어
20240205 기준 : Platinum IV (μ = P4 - 0.09, σ = 0.29)
알고리즘 분류
solved.ac : disjoint_set, ad_hoc
작성자 풀이 : disjoint_set, ad_hoc
풀이
한 컴포넌트에서 정점이 2개 이상일 때 서로 계속 왔다갔다할 수 있으므로, t번 이동할 수 있다면 t+2번 이동할 수 있다. 게다가 문제에서 t>=10^6인 경우만 고려하므로 홀수/짝수 길이의 사이클이 존재하는 지 묻는 문제이다. 이때 짝수는 위에서 설명한 이유 때문에 자동으로 성립한다. 즉 이 문제는 간선이 추가될 때마다 각 컴포넌트 당 홀수 사이클이 있는지 찾으면 된다.
이걸 처리하는 법은 여러가지가 있을 수 있는데, 유니온 파인드를 이용하는 방법은 홀수/짝수 정점을 분할하고 a-b를 a_홀수 - b_짝수, a_짝수-b_홀수로 생각해서 merge한 다음 a_홀수와 a_짝수가 유니온 파인드 상에서 같은 집합인지 확인하면 된다. 아무리 생각해도 정말 쩌는 아이디어다.
solved.ac 티어
20240205 기준 : Platinum V (μ = P5 - 0.36, σ = 0.81)
알고리즘 분류
solved.ac : smaller_to_larger, tree_set
작성자 풀이 : smaller_to_larger, tree_set
풀이
Small to Large 기초 문제이다. 각 집합을 set으로 관리하고 합칠 때 작은 쪽을 큰 쪽으로 옮기면 이동 횟수가 O(NlogN)이 보장되서 O(Nlog^2N)에 풀린다.
solved.ac 티어
20240205 기준 : Platinum I (μ = P1 - 0.15, σ = 0.56)
알고리즘 분류
solved.ac : smaller_to_larger, priority_queue
작성자 풀이 : smaller_to_larger, priority_queue
풀이
트리dp 하듯이 dfs하면서 그리디하게 자기 자식들의 pq를 합치고 거기서 m 초과일 동안 월급이 큰 닌자부터 빼주면 된다. 이 때 pq를 Small to Large로 관리하면 된다.
2022 POSTECH Programming Contest - 트리의 MEX
닌자배치랑 별 차이가 없는 것 같은데 티어 차이가 꽤 있다.
solved.ac 티어
20240205 기준 : Platinum III (μ = P3 - 0.12, σ = 0.33)
알고리즘 분류
solved.ac : smaller_to_larger, tree_set
작성자 풀이 : smaller_to_larger, tree_set
풀이
트리dp 하듯이 dfs하면서 그리디하게 자기 자식들의 set과 mex 결과를 합치고 mex를 update해주면 된다.
2/6
XOR MST를 풀기 위해 XOR Trie를 또 복습했다. (날먹 문제를 찾았다는 표현이 더 맞는 것 같다.)
solved.ac 티어
20240206 기준 : Platinum III (μ = P3 + 0.24, σ = 0.45)
알고리즘 분류
solved.ac : trie
작성자 풀이 : dynamic segment tree/std::set
풀이
침대에서 발상이 떠올랐다.
solved.ac 티어
20240206 기준 : Diamond IV (μ = D4 - 0.47, σ = 0.50)
알고리즘 분류
solved.ac : divide_and_conquer, mst, trie
작성자 풀이 : union_find, mst, trie
풀이
2/7
전에 어렵다고 안 푼 아리스 hard를 풀었다. 그리고 지금까지 센트로이드를 비효율적으로 짜고 있었다는 사실을 깨닫고 복습한 후 문제를 몇 개 풀었다.
BOJ 31399 - 아리스, 청소합니다! (Hard)
생각보다? 구현이 깔끔한 문제이다.
solved.ac 티어
20240208 기준 : Platinum II (μ = P2 + 0.17, σ = 0.39)
알고리즘 분류
solved.ac : union_find, simulation
작성자 풀이 : union_find, simulation
풀이
일단 상태를 (x,y,d)로 표현할 수 있다는 사실을 Easy에서 알았다. 그리고 그 상태와 완전히 동일한 상태(x,y,d도 같고 먼지 상태도 같음)가 한 번 더 나오면 cycle이 생길 것이다.
이러한 사실을 이용해서, 방문했을 때 union find로 다음 위치랑 merge하면서 계속 이동했을 때 처음으로 먼지가 없는 위치랑 그때까지 드는 이동 수를 관리할 수 있다. 이거랑 맵뚫하는 경우랑 처리해주면 문제를 풀 수 있다.
전에 푼 문제이다.
solved.ac 티어
20240206 기준 : Diamond IV (μ = D4 - 0.29, σ = 0.46)
알고리즘 분류
solved.ac : centroid_decomposition, divide_and_conquer
작성자 풀이 : centroid_decomposition, divide_and_conquer
풀이
너무 유명한 문제이다. 센트로이드 분할을 하면서 각 센트로이드에서 내려가는 길이 x인 경로의 간선 개수의 최솟값을 관리하면서 잘 합쳐주면 된다.
USACO'13 US Open Contest - Yin and Yang
전에 푼 문제이다.
solved.ac 티어
20240129 기준 : Diamond IV (μ = D4 + 0.00, σ = 0.00)
알고리즘 분류
solved.ac : centroid_decomposition, divide_and_conquer
작성자 풀이 : centroid_decomposition, divide_and_conquer
풀이
바로 윗 문제인 경주와 비슷하게, 길이가 x이면서 그동안 가중치 합이 0인적이 있었는가를 함께 관리하면 해결할 수 있다.
solved.ac 티어
20240207 기준 : Diamond V (μ = D5 - 0.18, σ = 0.55)
알고리즘 분류
solved.ac : centroid_decomposition, divide_and_conquer, smaller_to_larger, tree_set
작성자 풀이 : centroid_decomposition, divide_and_conquer
풀이
역시 윗 문제들과 비슷하게, {U 개수, C 개수, P 개수}를 관리하면서 열심히 합쳐주면 풀 수 있다. 구현이 가장 귀찮았다.
2/8
어제에 이어서 센트로이드를 더 팠고 드디어 센트로이드 트리를 이해했다. 그리고 트리와 쿼리 4를 풀다가 실패하고 골랜디를 했다.
solved.ac 티어
20240208 기준 : Diamond IV (μ = D4 + 0.00, σ = 0.00)
알고리즘 분류
solved.ac : centroid_decomposition, divide_and_conquer
작성자 풀이 : centroid_decomposition, divide_and_conquer
풀이
센트로이드 트리의 높이가 O(logN)이라는 것과 센트로이드 트리에서 u와 v의 lca는 원본 트리의 u-v 경로를 분할한다는 성질을 이용해야 한다. (참고)
정점마다 거리 set을 관리하는데 정점의 색을 바꿀 때마다 센트로이드 트리에서의 조상들을 업데이트해주면 된다.
골랜디는 양이 너무 많아서 생략. 절대 쓰기 귀찮은게 아니다.
2/9
옛날부터 봤던 문제인 두 번째로 작은 스패닝 트리를 풀었다. 얘는 풀이가 시골에서 마당을 돌다가 생각났다. 역시 생각은 책상 빼고 다 잘나는 것 같다. 그 뒤에 골랜디를 또 했다.
solved.ac 티어
20240209 기준 : Diamond IV (μ = D4 - 0.33, σ = 0.63)
알고리즘 분류
solved.ac : lca, mst, sparse_table
작성자 풀이 : lca, mst, sparse_table
풀이
일단 mst를 하나 뽑자. 그럼 mst에 포함되지 않은 간선들이 있을 것이다. 그러한 간선이 포함되는 mst의 가중치를 간선마다 구해줄 것이다. 이를 위해서 일단 포함되지 않은 u-v 간선을 추가하자. 그럼 정점 n개, 간선 n개인 그래프가 되는데 여기서 중요한 점은 이 때 사이클이 딱 하나 생성된다는 것이다. 또한 그 사이클을 이루는 간선은 mst에서 u<->v 경로 간선 + u-v 간선 이라는 사실을 알 수 있다. 이 사이클에서 u-v 간선이 아닌 하나를 없애줘야 하므로 결국 u<->v 경로에서 하나를 없애줘야 한다. 이 때 최대한 최댓값을 없애줘야 이득이므로 u-v 경로에서 간선의 최댓값을 알면 된다. 이건 sparse table로 할 수 있음이 잘 알려져 있다. 이 때 고려할 점은 u-v 경로의 최댓값 = u-v의 가중치일 수 있으므로 최댓값과 2번째 최댓값까지 관리해주면 된다. 여러가지 케이스 때문에 시도 횟수가 상당히 많은 문제인데, 본인은 운이 좋았는지 배열 크기 외에는 딱히 WA를 받지 않았다.
골랜디는 역시나 생략.
2/10
센트로이드2트 + 골랜디3트(3연속 생략)
트리와 쿼리 4를 드디어 풀었다.
solved.ac 티어
20240210 기준 : Diamond III (μ = D3 - 0.13, σ = 0.34)
알고리즘 분류
solved.ac : centroid_decomposition, divide_and_conquer
작성자 풀이 : centroid_decomposition, divide_and_conquer, tree_set
풀이
트리와 쿼리 5번과 비슷하지만 좀 다르게 서브트리마다의 답을 잘 관리해주면 된다. 사실 정확한 풀이가 기억이 안난다. 구현에서 모든 시간이 날아갔기 때문에..
구현이 하도 짜증나서 서브트리마다 정답을 관리하는 배열 이름이 tlqkf이었다(!).
별로 좋은 풀이는 아니라고 생각해 자세한 설명은 생략.
void upd(ll i){
color[i] = !color[i];
if(color[i]){
ll I = i;
st[i].insert(0);
if(tlqkf[i]>=-1e9)ans.erase(ans.find(tlqkf[i]));
tlqkf[i] = max(tlqkf[i],(st[i].size() > 1 ? (*st[i].rbegin()) + *(--(--st[i].end())) : *st[i].rbegin()));
ans.insert(tlqkf[i]);
for(int anc = cent_par[i] ; anc > 0 ; anc = cent_par[anc], i = cent_par[i]){
ll w = dist(I,anc);
while(E[i].size() and child[i].top()==E[i].top())child[i].pop(), E[i].pop();
if(child[i].size() and st[anc].contains(child[i].top()))st[anc].erase(st[anc].find(child[i].top()));
child[i].push(w);
st[anc].insert(child[i].top());
if(tlqkf[anc]>=-1e9)ans.erase(ans.find(tlqkf[anc]));
tlqkf[anc] = max(tlqkf[anc],(st[anc].size() > 1 ? (*st[anc].rbegin()) + *(--(--st[anc].end())) : *st[anc].rbegin()));
ans.insert(tlqkf[anc]);
}
}
else{
ll I = i;
ans.erase(ans.find(tlqkf[i]));
st[i].erase(st[i].find(0));
if(st[i].empty() or (st[i].size()==1 and !color[i]))tlqkf[i] = -2e9;
else tlqkf[i] = (st[i].size() > 1 ? (*st[i].rbegin()) + *(--(--st[i].end())) : *st[i].rbegin()), ans.insert(tlqkf[i]);
for(int anc = cent_par[i] ; anc > 0 ; anc = cent_par[anc], i = cent_par[i]){
ll w = dist(I,anc);
while(E[i].size() and child[i].top()==E[i].top())child[i].pop(), E[i].pop();
st[anc].erase(st[anc].find(child[i].top()));
E[i].push(w);
while(E[i].size() and child[i].top()==E[i].top())child[i].pop(), E[i].pop();
if(child[i].size())st[anc].insert(child[i].top());
if(tlqkf[anc]>=-1e9)ans.erase(ans.find(tlqkf[anc])), tlqkf[anc] = -2e9;
if(st[anc].empty() or (st[anc].size()==1 and !color[anc]))tlqkf[anc] = -2e9;
else tlqkf[anc] = (st[anc].size() > 1 ? (*st[anc].rbegin()) + *(--(--st[anc].end())) : *st[anc].rbegin()), ans.insert(tlqkf[anc]);
}
}
}
2/11
플랜디의 필요성을 느껴서 현재 실력으로 적당히 풀기 어려운 난이도인 /olympiad *p2..d5로 랜디를 하나 했다.
그 뒤에 코포를 쳤다.(링크)
USACO'20 US Open Contest - Exercise
소요시간 : 1시간 7분
solved.ac 티어
20240211 기준 : Platinum II (μ = P2 - 0.14, σ = 0.37)
알고리즘 분류
solved.ac : dp, number_theory, primality_test, permutation_cycle_decomposition
작성자 풀이 : dp, number_theory, primality_test, permutation_cycle_decomposition
풀이
일단 주기가 1~N은 무조건 된다. 순열 사이클의 주기는 각 사이클 크기의 lcm이라는 사실을 이용하자. 이러면 여러가지 관찰을 할 수 있다.
1. 결국은 N을 여러 수로 분할하는 문제임을 알 수 있다.(N의 분할은 N을 몇몇 자연수의 합으로 나타내는 것이다) 이때 사이클의 주기는 분할한 값들의 lcm이다.
2. (N에서의 답) = (1~N에서의 답)이므로 (1~N-1의 답)에서 N의 답을 합친다고 생각하자. 그러면 lcm(a,a)이므로 N을 분할할 때 같은 수를 2번 사용할 필요가 없다. a가 2번 분할에 사용되었다면 a를 한번만 사용한 경우가 이미 (N-a에서의 답)에서 구해졌을 것이기 때문이다. 마찬가지로 3번 이상 사용할 필요가 없다.
3. 2번과 비슷한 논리로, p^k 꼴의 수로만 분할하면 된다. (p는 소수) a + b <= a * b이기 때문에 p^k꼴이 아닌 수는 소인수분해 하여 p^k꼴의 합으로 나타냈을 때 더 이득(더 작은 N에서 등장)임을 알 수 있다.
결국, 이 문제는 다음과 같다.
"k를 소인수분해 했을 때 k = p1^e1 * p2^e2 * ... * px^ex 라고 하자. p1^e1 + p2^e2 + ... + px^ex <= n를 만족하는 모든 k의 합은?"
n <= 10^4이고 n = 10^4일때 소수의 개수 < 1234이므로 다음과 같은 dp를 이용해 문제를 풀 수 있다.
dp[i][j] := 현재 합이 i(i <= n)이고, j번째 소수를 보고 있을 때 합
p^k <= n인 k가 2,3 정도를 제외하면 굉장히 작기 때문에 충분히 시간 제한 안에 풀 수 있다.
원래 이런 유형을 잘 못 푸는데 간만에 깔끔하게 푼 것 같다.
