상위 99.99%의 PS

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

https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 간선의 개수를 최소로 해서 모든 정점을 잇는 그래프는 트리이고, 이때 간선의 개수는 N - 1 개이다. 간선의 정보는 사용할 필요가 없다. 템플릿 코드 더보기 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 38 39 40 41..

https://www.acmicpc.net/problem/13925 13925번: 수열과 쿼리 13 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 x y v: Ai = (Ai + v) % MOD를 수행한다. (x ≤ i ≤ y) 2 x y v: Ai = (Ai × v) % MOD를 수행한다. (x ≤ i ≤ y www.acmicpc.net Lazy Propagation in Segment Tree 1번 쿼리는 (ax + b) * 1 + v = ax + b + v 2번 쿼리는 (ax + b) * v + 0= (v * a)x + v * b 3번 쿼리는 (ax + b) * 0 + v = v 꼴로 갱신할 수 있다. 곱하는 값, 더하는 값에 대해..

https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net Lazy Propagation 기초 문제이다. 모른다면 읽고 오자. https://m.blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=kks227&logNo=220824350353 기존 세그먼트 트리의 방식으로라면 갱신 하나에 O(NlgN)이라는 시간이 걸려 총 O(MNlgN)이라..

https://www.acmicpc.net/problem/18937 18937번: 왕들의 외나무다리 돌게임 길이 6짜리의 외나무다리에 흰 돌이 3번 칸에 있고, 검은 돌이 5번 칸에 있으면, 흰 돌은 1, 2, 4번 칸 중 하나로 이동할 수 있으며, 검은 돌은 4, 6번 칸 중 하나로 이동할 수 있다. 돌을 상대 돌로 www.acmicpc.net 외나무다리의 길이가 n이면, 그런디 수는 n - 2이다. 여기서 뒤로 가는 것은 승패에 영향을 끼치지 않으므로, 그냥 xor해주면 끝이다. 코드 bo 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def ip(): return int(input()) def sp(): return str(input().rstrip()) def m..

https://www.acmicpc.net/problem/11871 11871번: 님 게임 홀짝 koosaga와 cubelover가 님 게임 홀짝 버젼을 하고 있다. 님 게임은 돌을 차곡 차곡 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가 www.acmicpc.net 노트에 8정도까지만 써보면 규칙이 보인다. 홀수면 (i + 1) / 2, 짝수면 (i - 2) / 2이다. 모두 xor해서 승자를 찾으면 끝이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def ip(): return int(input()) def sp(): return str(input().rstrip()) def mip(): return ..