상위 99.99%의 PS

https://codeforces.com/contest/1659 Dashboard - Codeforces Round #782 (Div. 2) - Codeforces codeforces.com A (00:05) r/(b+1) 개의 R, 1개의 B를 번갈아 놓되, 남는 R들을 칸?마다 1개씩 뿌려주면 된다. B (00:35) i, j번째를 고르면, A[i]와 A[j]의 비트가 각각 반전된다. 이 점을 이용하여, k가 홀수일 때와 짝수일 때를 나누어 풀면 된다. C (01:37) 식정리를 확실히 하지 않는 실수로 20분정도를 날려먹었다. 바로 전 지점과의 거리를 배열 D에 저장하자. 만약 2번째를 수도로 잡고 3번째 지역을 점령한다면 (빨간 직사각형의 합 * b) 을 빼고 (D[1] + D[2]) * a 값을..

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/20052 20052번: 괄호 문자열 ? 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net L~R까지의 합이 0이면 된다. 누적합과 세그트리를 사용하자 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 import sys input = sys.stdin.readline INF = 10 ** 7 seg = [0 for _ in range(4040..

https://codeforces.com/contest/1665 Dashboard - Codeforces Round #781 (Div. 2) - Codeforces codeforces.com A - GCD vs LCM (00:02) 1 (n - 3) 1 1 B - Array Cloning Technique (00:10) 가장 많은 수의 개수를 k라고 하면, k는 계속 2배가 된다. 그냥 구현하면 된다. B - Tree Infection (01:25) 루트를 기준으로 층을 나누고, 각 자식 노드의 수를 배열 c에 저장한다. 여기서 자식 노드의 수가 큰 정점부터 그리디하게 해결하면 된다. D - Array Cloning Technique (--:--) gcd(x+a, x+b) = gcd(x+a, b-a)임을..

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. 주어진 모..