thisisuser's study

https://www.acmicpc.net/problem/3665solved.ac: Gold I (2024.09.10) 약간의 애드혹 느낌이 있는 문제다. 문제에서 알아야 했던 것은, 상대적인 순위가 바뀐 모든 팀의 쌍을 주었다는 것이다.즉 순위가 바뀌지 않은 팀도 모두 주었다는 것이다. 따라서 완전 그래프를 구성할 수 있고, 이를 위상 정렬하면 된다. 여담으로, 확실한 순위가 주어지지 않았으면 "?"을 출력하라는 것은 페이크다.만약 확실한 순위가 주어지지 않았으면, 다음과 같이 두 정점 간의 우선순위 비교가 불가능한 경우이다.다시 정의하면, 방향 그래프에서 두 정점에 대해 한 정점에서 다른 정점으로 도달하는 것이 불가능하다는 것이다.근데 애초에 완전 그래프이기 때문에, 이러한 경우는 불가능하다. 임의의..

https://www.acmicpc.net/problem/1450solved.ac: Gold I (2024.09.10)깔끔한 구현 연습용으로 풀었습니다.정렬된 배열이 있을 때, v 이하의 수의 개수는 upper_bound(arr, v) - arr.begin()으로 얻을 수 있습니다. N이 어중간하게 크므로, mitm 기법이 바로 떠오릅니다.그냥 구현합시다.#include #include #include using namespace std;typedef long long int LL;/* 정렬된 배열 arr에서 v 이하의 개수 */LL findLower(vector &arr, LL v){ return upper_bound(arr.begin(), arr.end(), v) - arr.begin();}/* a..

13896번: Sky Tax (acmicpc.net)solved.ac: Platinum III (2024.09.10)문제를 요약하면, 루트 노드가 수시로 바뀌는 상황에서 서브트리 크기를 구하는 쿼리를 처리하라는 것이다. 일단 아직 뭐 rerooting technique라던가 배운 적도 없고, ETT는 쓸 생각도 못했다.여기서는 쌩 LCA만 이용한 풀이를 작성한다.처음 볼 때부터 그때그때 서브트리 크기를 직접 구하는 건 미친짓이라고 생각했다.미리 한번 돌려서 크기를 구해놓고, 적절히 끼워맞추는 방식으로 접근했다. 이후 몇 개의 간단한 케이스워크를 통해 규칙을 찾았다.이후의 모든 서술은 처음에 한번 잡고 돌린 트리를 기준으로 한다. Case 1: 현재 루트노드가 쿼리 노드의 조상일 때서브트리라는 것을 다시 ..

최근 PS 재활치료를 하면서 기본기가 많이 부족하다는 것을 느꼈다.당장 플레5 하나 잡고 풀어보려니까 뇌가 많이 아팠다. 이 문제같은 경우 PS할 때 한번은 짚고 넘어가면 좋을 것 같아서 복습 겸 정리를 해본다.2957번: 이진 탐색 트리 (acmicpc.net) solved.ac: Platinum V (2024.09.10)문제는 이거 구현해서 C값 출력하라는 것이다.딱 봐도 그대로 구현하라는 문제는 절대 아니다. 편향 트리 반드시 주긴 할 거다. 먼저 저 카운터 값은 노드의 깊이를 의미한다는 것을 알 수 있다.임의의 노드에 대해 자식이 존재한다면 왼쪽 자식은 반드시 노드보다 작고, 오른쪽 자식은 반드시 노드보다 크다.일단 대충 트리가 있고, X가 삽입되는 상황이라고 가정해 보자. 어떤 노드 P에 대해 ..

이번엔 트리 위에서 분할 정복을 해보려 합니다.신난다 단순 배열 위에서 분할 정복을 했을 때를 생각해 봅시다.대충 가운데를 잡고 반으로 쪼개면, 두 구간 모두 크기가 반이 되면서 두 개의 구간으로 나누어지므로시간 복잡도 $O(NlogN)$이 보장됩니다. 그렇다면 트리 위에서 분할 정복을 하려면 어떻게 해야 할까요?트리에서 대충 배열에서의 가운데와 비슷한 역할을 하는 어떤 노드를 잡고 쪼개면,나누어지는 서브트리 모두 크기가 반 이하가 되면 될 것 같이 생겼습니다. 여기서 센트로이드라는 개념이 등장합니다.센트로이드(Centroid)는 지웠을 때 서브트리의 크기가 모두 원래 트리의 반 이하가 되도록 하는 노드를 의미합니다. 혹시 센트로이드가 없을 경우가 우려된다면, 다행히 모든 트리에는 센트로이드가 반드시 존..

알고리즘 공부도 할 겸, 대회 때 접했던 문제를 다시 풀어보려 합니다.1. 반품 회수 (Silver 1)그냥 끝까지 쭉 가서 돌아오는 길에 아직 안 오면 대기타다가 갖고 가면 될 것 같이 생겼습니다.바로 구현해서 100점을 맞고 시작했습니다.#include using namespace std;typedef long long int LL;LL d[3001], t[3001];int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for(int i=1;i> d[i]; for(int i=1;i> t[i]; LL res = 2 * d[n]; for(int i=1;i 2. 이진 트리 (Platinum 5)일단 문제만 한 3번은 읽은..

https://www.acmicpc.net/problem/2634solved.ac: Platinum III (2024.09.10) 문제를 요약하면 다음과 같습니다.리프 노드끼리 이어 경로를 구성한다. 이때 모든 간선은 정확히 한 번씩만 사용해야 한다.예제의 경우를 예로 들면, 다음과 같이 구성하면 됩니다. 일단 트리라기엔 모양이 너무 예쁘지 않습니다. 한번 다음과 같이 다시 그려 봅시다. 먼저 리프 노드가 아닌 경우, 해당 그림에서는 색칠되지 않은 그림의 경우 항상 노드의 차수가 짝수가 되어야 합니다. 이유는 문제에서 리프 노드끼리만 경로를 이어야 하기 때문입니다.만약 해당 노드가 어떠한 경로에 포함된다면, 리프 노드가 아니므로 반드시 해당 간선은 어떠한 경로 중간에 있게 됩니다.따라서 항상 두 개의 간..

https://www.acmicpc.net/problem/3295solved.ac: Platinum II (2024.09.10)관찰과 아이디어를 요구하는 문제입니다. 먼저 분해의 가치는 곧 간선의 개수를 의미하게 된다는 점을 파악할 수 있어야 합니다.또한, 각 노드마다 진입 차수와 진출 차수는 0, 또는 1이 되어야 합니다. 네, 신나게 이분 매칭을 때려주면 됩니다. 답안 코드더보기#include #include #include using namespace std;int n, m;vector node[1001];int a[1001];bool visited[1001];bool dfs(int cur){ for(auto nxt: node[cur]) { if(visited[nxt]) contin..

Heavy-Light Decomposition이란 트리를 여러 개의 선형 구조로 분해하여 접근할 수 있게 해주는 기법입니다.먼저 트리 위에서 다음과 같은 쿼리가 주어지는 문제를 생각해 봅시다.정점 i의 가중치를 v로 변경한다.두 정점 간의 경로 상의 정점의 가중치 합을 구한다.당연히? $N \le 100000$ 정도입니다.배열 위에서였다면 바로 신나게 세그먼트 트리를 짰겠지만, 트리 위이다 보니 바로 적용하기는 어렵습니다. 배열에서는 되고, 트리에서는 안 되는 이유는 무엇일까요?당연한 소리지만, 트리는 배열과 달리 비선형구조이기 때문입니다. 그렇다면 이렇게, 트리를 여러 개의 선형 구조로 쪼갠다면 어떨까요?이 경우에는 부분 부분에 대해서는 세그먼트 트리로 관리해줄 수 있겠다는 생각이 듭니다.문제는 이걸 ..

solved.ac: Platinum I (2024.09.06) KOI 2023 본선 2번으로 출제된 문제입니다.https://www.acmicpc.net/problem/28327 문제를 요약하면,길이 $N$의 1부터 $N$까지의 자연수를 모두 원소로 가지는 수열이 주어진다.각각의 수 $x$에 대하여, 서로 다른 모든 구간에 대하여 지그재그 수열의 최대 길이의 합을 구하여라.이 되겠습니다.$O(N^{3})$ 풀이개인적으로 이 문제를 보자마자 $O(N^{2})$를 짜는 건 사실상 천재의 영역이라 생각됩니다.따라서, 핵심 아이디어를 뽑아내고 이를 먼저 나이브하게 구현해 보겠습니다. 지그재그 수열을 더 길게 만들고 싶다면, 바로 앞의 두 수와 이번에 추가할 수에 대하여계속 증가하거나 계속 감소하는, 단조성을 띄..