MathTrauma

문제 링크 : https://www.acmicpc.net/problem/1420 1420번: 학교 가지마! 첫째 줄에 도시의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 100) 둘째 줄부터 N개의 줄에 도시의 모양이 주어진다. 비어있으면 점('.'), 벽은 '#', 도현이의 위치는 K, 학교의 위치는 H이다. www.acmicpc.net 출발 정점(도현이의 위치)이나 도착 정점(학교)의 주변을 벽으로 막으면... 맵 모양에 관계없이 답은 4 이하임을 알 수 있다. 따라서 등교를 막을 수 없는 경우를 체크할 때, 유량이 4를 초과하는 것을 이용할 수 있다. 하여간 4 이하인 값 찾기 위해 '유량 네트워크'를 써야 하다니? 다른 방법이 없을까 생각해 보아야겠다. 문제로 돌아가서 어떻게 ..

모델링만 정리하자. 첫 줄은 사람수 n, 서점 수 m 이 주어진다. 출발 노드는 0, 도착 노드는 n+m+1 으로 둔다. (따라서 노드 개수는 n+m+2 ) (1) 다음 행에 사람에 대한 정보가 주어진다. 1 부터 n 까지는 사람에 해당되는 노드 번호로 정했다. 출발 노드로부터 이 노드들에 '비용' 0 이고 간선 '용량'은 \(a_i\) 인 간선을 연결. (2) 다음 행(3행)에 서점에 대한 정보가 주어진다. n+1 부터 n+m 까지는 서점을 나타낸다. 비용은 0 이고 용량은 \(b_i\) 인 간선을 도착 노드에 연결. (3) 뒤 따르는 m 개의 행에는 서점에서 각 사람(1~n)에게 배송할 때의 비용을 알려준다. 주어지는 정보가 모델링의 순서와 바뀌어서 i 와 j 의 위치에 주의하자. mcmf.link(..

문제 링크 : https://www.acmicpc.net/problem/2316 2316번: 도시 왕복하기 2 N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이때 한 번 방 www.acmicpc.net 정점을 한 번만 사용할 수 있다. 정점을 입력 정점과 출력 정점으로 분리하고 둘 사이의 capacity=1 로 둔다. 정점 u 로 들어온 flow 는 u 의 출력 정점인 u+n 까지 기껏해야 1 의 용량을 가지는 간선을 이용하게 된다. 즉, 최대 한 번 이용할 수 있다는 뜻이다. 문제에서 간선 입력 u, v 는 u+n 에서 v 로 그리고 역간선은 v+n, u 로 연결하면 ..

문제 링크 : https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net 최소 공통 조상을 \(\log(n)\) 시간 이내로 찾을 수 있도록 해주는 것은 이중 배열 prv 이다. 이 배열은 음이 아닌 정수 k 에 대해 \(2^k\) 만큼 앞의 선조에 대한 정보를 기록하고 있다. prv[i][k] 는 i 번 노드의 \(2^k\) 번째 선조로 prv[i][k]=prv[prv[i][k-1]][k-1] 을 만족한다. 도..

문제 링크 : https://www.acmicpc.net/problem/11932 11932번: 트리와 K번째 수 첫째 줄에는 두 개의 양의 정수 N과 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 각 정점의 가중치를 나타내는 N개의 정수가 주어진다. i번째 정수는 i번 정점의 가중치이다. 이 가중치는 모두 www.acmicpc.net persistent segment tree + lca 로 해결했다. (더 나은 방법은 없을까?) lca 를 위한 dfs 를 거치면서 부모 노드가 각 자식노드를 생성하는 segment tree 이다. 최소공통조상(lca)는 아래 글에서 간략히 정리해 두었으니 참조. BOJ 3584 Nearest Common Ancestors BOJ 3584 Nearest..

문제 링크 : https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 주어진 문제는 root 가 주어진 tree 에서 최소(?)의 공통 조상을 찾기를 요구하는데... 노드(정점) 집합의 크기로 보아 lca(least comman ancestor) 와 관련된 기술을 쓰지 않아도 될 것으로 보인다. 하지만 분류상 '최소공통조상'에 들어 있는 문제이니, 하라는 대로 했다. 각 노드가 자신의 부모만 알고 있..

max 를 찾는 문제의 작은 변형. tree 의 각 노드를 pair로 두고 으뜸값과 버금값을 기록하면 된다. func 는 두 개의 pair 의 네 값에서 으뜸과 버금을 찾아 pair 로 돌려준다. tree 의 terminal node 는 입력값이 기록되어야 하므로 버금값은 입력되는 값보다 작은 아무 값이나 정하면 된다. 주어진 문제에서는 입력값이 자연수이므로 tree 의 기본값인 0 을 써도 상관없다. 음수가 허용되면 주석 처리한 부분을 살리면 된다. #include using namespace std; using pii=pair; int arr[100001]; pii tree[300000]; pii func(pii a, pii b){ pii res; int t; if(a.first>=b.first) {..

x 좌표는 오름차순, y 좌표는 내림차순으로 정렬. 정렬된 순으로 진행하면서 이전까지 기록한 y 좌표가 크거나 같은 것의 개수를 센다. 즉, 범위 안의 y 좌표를 효과적으로 세야하니까 segment tree 나 Fenwick tree 를 쓴다. 먼저 Fenwick tree 부터 #include using namespace std; using ll=long long; int sz; pair arr[75000]; int cpy[75000], bits[75001]; void upd(int p){ for(;p0;p&=p-1) ans+=bits[p]; return ans; } void solve(){ int n; scanf("%d", &n); for(int i=1;i