상위 99.99%의 PS

https://www.acmicpc.net/problem/5822 5822번: 악어의 지하 도시 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개 줄에는 R[i][0], R[i][1], L[i]가 주어진다. 다음 K개 줄에는 P[i]가 주어진다. (3 ≤ N ≤ 100,000, 2 ≤ M ≤ 1,000,000) www.acmicpc.net - 다익스트라? 문지기의 입장에서 생각해보자. 철수가 갈 수 있는 정점들 중, 가장 가까운 정점으로 가는 간선을 막는 것이 이득이다. 그러므로, 철수는 항상 두번째로 빠른 길로 가게 될 것이다. 다익스트라 비슷한 거를 탈출방부터 진행하면 된다. 답은 정점 0에 저장된 두 번째로 먼 길이가 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16..

https://www.acmicpc.net/problem/5821 5821번: 쌀 창고 첫째 줄에 R, L, B가 주어진다. 둘째 줄부터 R개 줄에는 X[i]가 주어진다. (1 ≤ R ≤ 100,000, 1 ≤ L ≤ 1,000,000,000, 0 ≤ B ≤ 2,000,000,000,000,000) www.acmicpc.net - 이분 탐색 - 누적 합 논의 개수가 홀수일 때, 가운데에 있는 논에 창고를 세울 때 최소비용이 된다. 논의 개수가 짝수일 때는, 가운데 두 논의 좌표 a, b에 대해 a

https://www.acmicpc.net/problem/2575 2575번: 수열 첫째 줄에 정수 M이 주어진다. 1 ≤ M ≤ 1,000,000 이다. www.acmicpc.net 긴 수열은 3으로 쪼개고, 짧은 수열은 2 대신 4로 먼저 나누고 소인수분해 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 m = int(input()) x2 = 0 if m == 1: print(1, 1) exit() t = m x1 = (t + 2) // 3 while m % 4 == 0: m //= 4 x2 += 1 for i in range(2, 1000001): while m % i == 0: m //= i x2 += 1 print(x1, x2) cs

https://www.acmicpc.net/problem/14700 14700번: 넴모넴모 (Hard) 첫 번째 줄에 주어진 격자판에서 나올 수 있는, “넴모”들이 올라간 칸이 2 × 2 사각형을 이루지 않는 모든 배치의 가짓수를 1, 000, 000, 007로 나눈 나머지를 출력한다. www.acmicpc.net 파이썬으로 시간 터져서 못했음 파란색 칸을 채우기 위해서는 \((M + 1)\) 개 칸의 상태 정보가 필요하다. 파란색 칸을 채우지 않는 경우: => 항상 채우지 않는 선택을 할 수 있다. 채우는 경우: - 가장 왼쪽 칸일 경우: => 항상 채울 수 있다. - 가장 왼쪽 칸이 아닐 경우: => 왼쪽, 왼쪽 위, 위의 3개의 칸이 모두 색칠되지 않았다면 채울 수 있다. 1 2 3 4 5 6 7 ..

https://www.acmicpc.net/problem/10909 10909번: Quaternion inverse 각 \(A\)가 주어질 때마다, \(AB = 1\)을 만족하는 \(B = a + bi + cj + dk\)들 중 하나를 나타내는 네 개의 정수 \(a\), \(b\), \(c\), \(d\)를 공백으로 구분하여 \(T\) 줄에 걸쳐 출력하면 된다. 만약 이런 \(B\)가 www.acmicpc.net 사원수 \(a+bi+cj+dj\) 의 역원은 \(\frac{a-bi-cj-dj}{a^2+b^2+c^2+d^2}\) 이다. 이거에 mod 달면 그냥 답이 나오는데... 분모의 역원이 존재하지 않을 경우를 체크하지 않고 삽질함 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1..

https://www.acmicpc.net/problem/21735 21735번: 눈덩이 굴리기 눈송이들이 많은 동네인 숙명여대 앞마당에서 눈사람 만들기 대회를 연다. 앞마당의 길이는 $N$이고 위치 $1$부터 위치 $N$ 까지만 눈이 쌓여있다. 위치 $i$에 눈이 $a_i$만큼 쌓여있다. 대회 규칙은 www.acmicpc.net 비트마스킹 0이면 2칸, 1이면 1칸 이동 Python 코드 1 2 3 4 5 6 7 8 9 10 11 n,m=map(int,input().split()) a=list(map(int,input().split())) s=0 for i in range(1> n >> m; for (int i=0;i> a[i]; } int bit = 1

https://www.acmicpc.net/problem/17469 17469번: 트리의 색깔과 쿼리 N개의 정점으로 구성된 트리가 있다. 각 정점은 1번부터 N번까지 번호가 매겨져있고, 1 이상 10만 이하의 자연수로 표현되는 색깔을 하나 갖고 있다. 루트는 1번 정점이고, 트리이기 때문에 임의 www.acmicpc.net [사용한 알고리즘] Smaller to Larger Technique https://justicehui.github.io/medium-algorithm/2019/09/23/small-to-large/ 이 글을 통해 공부했습니다 1. 쿼리를 뒤집는다. 2. 그러면 간선 제거를 간선 연결로 볼 수 있다. 그럼 엄청 쉬워진다 Union-Find를 통해 구현했고, 말 그대로 작은거를 큰거에..

www.acmicpc.net/problem/14180 14180번: 배열의 특징 첫째 줄에 N (2 ≤ N ≤ 200,000)이 주어진다. 둘째 줄에는 Ai (|Ai| ≤ 1,000,000)가 주어진다. www.acmicpc.net 배열 t에서, \(A_{i} = t_{1} 부터 t_{i} 의 합\) B = 배열 t의 특징 이라고 하면, 배열 t의 n번째 수를 옮길 떄의 최댓값을 dp[n]이라고 하면, 이 n번째 수를 옮기는 방향에 따라 두가지로 나누어 풀면 된다. 왼쪽으로 옮길 때는, \(i= getX(k[-3], k[-2]): k.pop(-2) def bs(x): lo = 0 hi = len(k) - 2 while lo

www.acmicpc.net/problem/2315 2315번: 가로등 끄기 첫째 줄에는 2개의 정수 N(1 ≤ N ≤ 1,000), M 이 있다. 첫 번째 정수 N은 가로등의 개수를 나타내는 정수이고, 두 번째 정수 M은 마징가 처음에 위치하는 가로등 번호이다. 다음 N 개의 줄에는 각 가 www.acmicpc.net dp 진짜 개재밌게 풀었다. 이동은 바로 옆의 켜진 가로등으로만 하는 것이 이득이다. dp테이블은 구간 \([l,r]\)에서, 내 위치가 \(x\)일때 최솟값으로 나타내면 된다. 공간은 1000*1000*2를 사용한다. 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 impor..

www.acmicpc.net/problem/11693 11693번: n^m의 약수의 합 nm의 모든 약수의 합을 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 등비수열의 합 이용 예를 들어 \(2^2 \times 3^3\) 으로 소인수분해가 되는 수가 있다고 할때, 이 수의 약수의 합은 \((1+2^1+2^2) \times (1+3^1+3^2+3^3)\) 이다. 어떤 수 \(N\)과 소수 \(p\)에 대해, \(N = p^x\times C\) (\(C\)는 자연수) 로 나타낼 수 있다고 해보자. 이때, \(N^M = p^{xM} \times C^M\) 이므로, 소수 \(p\)에 대해 첫째항이 1이고, 공비가 \(p\)인 등비수열의 제 1항부터 제 \((xM+1)\)항까지..