상위 99.99%의 PS

https://www.acmicpc.net/problem/8462 8462번: 배열의 힘 자연수 \(n\)개로 이루어진 배열 \(a_1,a_2,a_3,\dots ,a_n\)이 있다. \(l\)부터 \(r\)까지 부분 배열은 \(a_l,a_{l+1},\dots , a_r\) 이다. \(K_s\)는 부분 배열 안에 있는 자연수 \(s\)의 개수이다. 부분 배열의 힘이란 www.acmicpc.net [사용한 알고리즘] Mo's Sqrt Decomposition 엄청 신기하고 강력한 기술인 모쓰, 제곱근 분할법 기초문제이다. 모른다면 보고 오자. 진짜 별거 없지만, 오프라인 쿼리 문제에서 잘 써먹을 수 있다. https://justicehui.github.io/hard-algorithm/2019/06/17/Mo..

https://www.acmicpc.net/problem/15520 15520번: Prime-Factor Prime A positive integer is called a "prime-factor prime" when the number of its prime factors is prime. For example, 12 is a prime-factor prime because the number of prime factors of 12 = 2 × 2 × 3 is 3, which is prime. On the other hand, 210 is not a prime-f www.acmicpc.net [사용한 것] 에라토스테네스의 체 1. 나누려는 소수 \(i\)의 범위 정하기 어떤 수가 소수인지 확인하는 방법..

https://www.acmicpc.net/problem/17408 17408번: 수열과 쿼리 24 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오 1 i v: Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 l r: l ≤ i

https://www.acmicpc.net/problem/13544 13544번: 수열과 쿼리 3 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. www.acmicpc.net 정렬된 배열 \(A\)가 있다고 하자. 이 \(A\) 내에서 어떤 수 \(k\)보다 큰 수의 개수를 \(O(N)\)보다 빠른 시간에 구하려면, 이진 탐색을 사용하여 \(O(lgN)\)에 구할 수 있다. 그런데 이 문제는 배열이 정렬되어 있지 않고, 그리고 구간을 나누어 쿼리에 답하라고 한다. 만약, 배열을 잘 잘라서 정렬된 상태로 가지고 있으면, 그 잘려진 배열 ..

https://www.acmicpc.net/problem/11574 11574번: CYK의 너무너무 재밌는 그래프 만들기 놀이 N (1 ≤ N ≤ 100)개의 정점의 개수가 주어지고, K (1 ≤ K ≤ 3)개의 가능한 색깔이 주어진다. 각 정점들을 1 부터 N까지 차례로 번호를 매기고, 그 정점들에 K개의 색깔중 하나를 임의로 부여한다. www.acmicpc.net 간단한 DP k = 1일때 무조건 1가지이다. k = 2일때 맨 뒤에 색 1 추가, 혹은 색 2를 추가하는 경우가 있다. \(dp[n][k] = n번째에서 색 1을 k개 사용하였을 때, 경우의 수\) 라고 하자. 색 1을 붙일 때: 간선을 잇는 경우는 색 2의 개수이고, 잇지 않는 경우는 1가지이므로, \(dp[n - 1][k - 1] * ..

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..