상위 99.99%의 PS

https://www.acmicpc.net/problem/25213 25213번: 조각 케이크 (Hard) 조각 케이크들을 골랐을 때, 고른 조각 케이크를 모두 합쳐서 케이크 한 판으로 만들 수 있는 경우의 수를 출력한다. 답이 매우 커질 수 있으므로, \(10^9+7\)로 나눈 나머지를 출력한다. www.acmicpc.net [알고리즘 분류] Meet in the Middle Combinatorics Prefix Sum Meet in the Middle을 공부하고 풀어본 문제다. 몇 가지 관찰이 필요하다. 1. lcm(2~25)는 그렇게 크지 않으므로, 분모를 통일할 수 있다. (계산이 편해진다.) 2. 모든 크기의 조각들이 무한히 존재할 때, 이들을 잘 모아 케이크 한 판으로 만들기 위해서는 많아봤자..

https://www.acmicpc.net/problem/16404 16404번: 주식회사 승범이네 첫 번째 줄에 승범이를 포함한 판매원들의 수 N(1 ≤ N ≤ 100,000), 명령의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 판매원들은 1번부터 N번까지 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 판 www.acmicpc.net [알고리즘 분류] Segment Tree (with lazy propagation) Euler Tour Technique 오일러 경로 테크닉이라는걸 배우고, 기초문제를 풀어보았다. 오일러 경로 테크닉은 루트가 있는 트리에서 어떤 정점의 서브트리에 속하는 정점들을 연속된 수로 renumbering할 수 있는 기술이다. 일단 나는 이렇게 이해했고, 이 문제는..

https://www.acmicpc.net/problem/10227 10227번: 삶의 질 첫째 줄에 4개의 정수 R, C, H, W 가 주어진다. R과 C는 각각 도시의 행과 열의 크기를 나타내고, H와 W는 각각 홍준이가 정한 영역에서의 행과 열의 크기이다. 그 다음 R개의 줄에 각각 C개의 quality ran www.acmicpc.net [알고리즘 분류] 이분 탐색, 누적 합 정답을 \(x\)라고 가정하자. 주어진 배열에서 \(x\)보다 큰 수는 1, 작은 수는 -1로 바꾼다면, 합이 0인 \(H\) x \(W\) 직사각형이 배열 내에 존재할 것이다. 이 아이디어를 이용하여 이분 탐색으로 적절한 \(x\)를 찾을 수 있고, 시간복잡도 \(O(RC(lg(RC)))\)에 문제를 풀 수 있다. 75줄부..

https://www.acmicpc.net/problem/16993 16993번: 연속합과 쿼리 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j : Ai, Ai+1, ..., Aj에서 가장 큰 연속합을 출력한다. (1 ≤ i ≤ j ≤ N) 수열의 인덱스는 1부터 시작 www.acmicpc.net 세그먼트 트리를 사용해서 풀면 된다. 왼쪽 끝점을 포함할 때의 구간합 최대 \(Seg_{ls}\) 오른쪽 끝점을 포함할 때의 구간합 최대 \(Seg_{rs}\) 어떤 구간에서의 구간합 최대 \(Seg_{ms}\) 구간의 합 \(Seg_{s}\) 자식 노드를 각각 \(L, R\)로 두면, \(Seg_{ls} = max(L_{ls}, L_{s} ..

https://www.acmicpc.net/problem/10848 10848번: 팔렘방의 다리 입력의 첫 줄에는 K와 N이 주어진다. 이후 N개의 줄에는 4개의 값 Pi, Si, Qi, Ti가 각각 주어진다. Pi와 Qi는 한글자 'A' 혹은 'B'이다. 0 ≤ Si, Ti ≤ 1, 000, 000, 000 사는 곳이나 사무실이 서로 다른 시민에 www.acmicpc.net 정말정말 좋은 문제이다. 일단, 한 도시에 집과 사무실이 모두 있는 경우는 없다고 가정하고, 다리의 길이를 무시해보자. \(k = 1\)일 때는, S와 T를 합쳐 정렬한 후, 중앙값이 다리의 좌표가 된다. \(k = 2\)일 때... \(f_i(x)\) 를 i번째 사람이 다리 x를 통해서 출근할 때의 거리라고 하면, \(f_i(x)..

https://www.acmicpc.net/problem/21908 21908번: Disk Sort The first line of the input contains a positive integer $n$ ($1 \le n \le 1\,000$). The next $3$ lines of the input contain $n$ positive integers $c_{i,j}$ each ($1 \le i \le 3$, $1 \le j \le n$, $1 \le c_{i,j} \le n$), the color each of the disks initiall www.acmicpc.net Ad-Hoc, Constructive, Case Work 어떤 종류의 디스크를 빈 막대에 모으기 위해서, 각 디스크마다 6번..

https://www.acmicpc.net/problem/13512 13512번: 트리와 쿼리 3 N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 가장 처음에 모든 정점의 www.acmicpc.net Heavy-Light Decomposition 일단 트쿼 3을 풀기 전에, LCA 2를 HLD를 이용해서 풀어보자. 1. dfs를 통하여 한 노드를 루트로 하는 서브트리의 크기를 저장해둔다. 1 2 3 4 5 6 7 def dfs(x, p): par[x] = p sz[x] = 1 for i in g[x]: if i != p: sz[i] += dfs(i, x) return sz[x] cs..

https://www.acmicpc.net/problem/3056 3056번: 007 비밀 요원 007은 제임스 본드로 유명한 비밀 요원이다. 최근 알려진 정보에 의하면 제임스본드는 대다수 미션을 자신이 직접 수행하지 않는다고 한다. 본드는 미션을 자신과 비슷하게 생긴 사촌 www.acmicpc.net DP Using Bitfield dp[bit] = (상태 bit에서의 최대 확률) 이라고 정의하자. dp[bit] = max(dp[bit], f(x + 1, bit | (1 =1 return ret def getInv(x): return getPow(x, MOD-2) Colored by Color Scripter cs 1 2 3 4 5 6 7 8 9 10 11 12 13 14 dp = [-1 for _ i..

https://www.acmicpc.net/problem/1311 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net DP Using Bitfield dp[n][bit] = (n번째에서 상태가 bit일 때 최소 비용) 이라고 정의하자. dp[n][bit] = min(dp[n][bit], f(n + 1, bit | (1 =1 return ret def getInv(x): return getPow(x, MOD-2) Colored by Color Scripter cs 1 2 3 4 5 6 7 8 9 10..

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net Union-Find 기초문제이다. 두 점을 선분으로 잇기 전에, 이 두 점이 다른 경로로 이미 연결되어있다면 사이클을 형성할 것이다. 다른 경로로 이미 연결되어있는지에 대한 여부는 Union-FInd를 이용하면 된다. 0. 입력이 들어온다. 1. 두 점의 그룹이 같은지 확인한다. 2-1. 같다면 답을 출력하고 바로 종료한다. 2-2. 다르다면 두 점의 그룹을 하나로 합쳐준다. 3. 주어진 모..