알고리즘 공부방

Biconnected Component는 biconnected (단절점이 없는) maximal subgraph이다. BCC는 그래프를 단절점/단절선을 기준으로 쪼갠 후, 이를 기준으로 정점/간선들을 묶어 트리로 만든다. 크게 2가지의 BCC가 있다. 1. Edge disjoint BCC = 단절점을 기준으로 쪼갠 간선의 집합 2. Vertex disjoint BCC = 단절선을 기준으로 쪼갠 정점의 집합 Vertex disjoint BCC의 경우에는 단절선을 모두 자른 후, 남은 컴포넌트들이 하나의 BCC를 구성하고, 이를 하나의 정점으로 압축한다면 트리가 된다. Edge disjoint BCC의 경우에는 BCC가 간선의 집합으로 구성되어 있기 때문에, 한 정점은 여러 개의 BCC에 포함될 수 있다. 특..

1. 합이 N인 수들 중 서로 다른 수들의 개수는 최대 $O(\sqrt{N})$개 이다. 서로 다른 수들을 최대한 많이 만들기 위해서는, 모든 수들이 서로 다르고, 1, 2, ... 와 같이 1부터 하나씩 채워 나가는 것이다. $1+2+...+x=N$이니, $x=N$이니, $\sqrt{N}$ 이상의 수들은 많아봤자 $O(\sqrt{N})$개가 된다. $\sqrt{N}$ 이상과 이하인 수들로 나누어 $\sqrt{N}$ 이상인 수들은 그 개수가 $\sqrt{N}$개 이하임을 이용하고, $\sqrt{N}$ 이하인 수들은 그 크기가 $\sqrt{N}$이하임을 이용하여 서로 다른 방법으로 해결할 수 있다.

문제 oj.uz/problem/view/JOI18_construction 문제 보기 - Construction of Highway (JOI18_construction) :: oj.uz 문제 보기 - Construction of Highway (JOI18_construction) oj.uz 트리가 주어지고, 처음에는 1번 노드밖에 없다. 한번의 업데이트 때마다, 지금 존재하는 트리에 하나의 간선을 추가하여 새로운 노드를 붙이는데, 이 때 루트에서부터 새로 붙인 노드까지의 경로의 정점들의 가중치를 일렬로 나열했을 때 만들어지는 수열의 inversion을 출력해야 한다. 또한, 업데이트 이후, 루트에서부터 새로 붙인 노드까지의 경로의 모든 정점들의 가중치는 모두 새로 붙인 정점의 가중치로 바뀌게 된다. $N

1. 각 노드에서 light edge를 타고 갈 때마다 서브트리의 크기는 1/2 이하로 감소한다. heavy edge가 가장 서브트리의 크기가 큰 간선이므로, 만약 light edge를 타고 가도 서브트리의 크기가 1/2 초과로 유지된다면, $sz[heavy]>=sz[light]>N/2$, $sz[heavy]+sz[light]>N$으로 모순이다. 2. 각 노드에서 루트 방향으로 부모를 타고 올라갈 때 만나는 light edge의 개수는 $O(logN)$개이다. Property 1에 의해 light edge를 타고 내려가면 서브트리의 크기가 1/2 이하로 감소하니, light edge를 타고 올라가면 서브트리의 크기가 2배 이상으로 증가한다. 전체 트리의 노드의 수가 N개 이니, light edge의 수는..

문제 oj.uz/problem/view/JOI19_cake3 문제 보기 - Cake 3 (JOI19_cake3) :: oj.uz 문제 보기 - Cake 3 (JOI19_cake3) oj.uz N개의 케이크 조각이 있고, 이중 M개를 뽑아 적당히 배열하여 $\sum_{i=1}^{M}V_i-\sum_{i=1}^{M}|C_i-C_{i+1}|$값을 최대화해야 한다. $M1; node->lc=new Node(); node->rc=new Node(); makeTree(node->lc, tl, mid); makeTree(node->rc, mid+1, tr); } Node *addTree(Node *node, int tl, int tr, int pos) { if(poscnt+1; ret->sum=node->sum+co..

문제 oj.uz/problem/view/JOI19_mergers 문제 보기 - Mergers (JOI19_mergers) :: oj.uz 문제 보기 - Mergers (JOI19_mergers) oj.uz 트리 상의 각 노드는 특정한 색으로 칠해져 있을 때, 트리가 "분할 가능하다"는 것은 트리를 연결된 두 개의 컴포넌트로 쪼개서, 모든 색이 정확히 하나의 컴포넌트에만 속하게 할 수 있다는 것이다. 서로 다른 두 색을 합칠 수 있을 때, 합치는 연산의 횟수를 최소로 해서 트리가 분할 가능하지 않도록 해야 한다. $Ndep[v]) swap(u, v); for(int i=20; i>=0; i--) if(dep[par[v][i]]>=dep[u]) v=par[v][i]; if(u==v) return u; for..

문제 www.acmicpc.net/problem/19456 19456번: Cocktails In the first line of input there are four space-separated integers $n$, $k$, $B$, $C$ ($1 \leq k \leq n \leq 500$, $1 \leq B, C \leq 10\,000$) --- the number of jars, the reach of the blender, the time needed to use the blender, and the time needed to swap www.acmicpc.net 길이 $N$의 수열이 주어지고, 할수 있는 연산은 1. $A_i$의 비용으로 i번째 칸을 체크 2. $B$의 비용으로 연속된 $k$개..

문제 oj.uz/problem/view/JOI19_lamps 문제 보기 - Lamps (JOI19_lamps) :: oj.uz 문제 보기 - Lamps (JOI19_lamps) oj.uz N개의 램프가 꺼져 있거나 켜져 있을 때, 1. 구간을 정해 구간의 램프들을 모두 끈다. 2. 구간을 정해 구간의 램프들을 모두 켠다. 3. 구간을 정해 구간의 램프들을 모두 토글(뒤집는다)한다. 의 3가지 연산을 적용하여 A 상태의 램프들을 B 상태로 만들어야 할 때 연산의 최소 횟수를 구해야 한다. $N