상위 99.99%의 PS

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

1 - 야구 시즌 식은(부등식으로) 간단하게 나오는데, 이거를 다시 B에 관한 식으로 바꿀 생각은 못했고 그냥 이분탐색 돌렸다. 아침에 일어나서 명일방주하느라 뇌 과부하돼서 문제 이해하는데 20분은 걸린듯 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 import sys input = sys.stdin.readline t = int(input()) while t: t -= 1 n,m,k,d = map(int, input().split()) lo = 1 hi = d ans = -1 now = 0 mid = lo+hi >> 1 mc = (m*(m-1))//2 nc = (n*(n-1))//2 while lo

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를 통해 구현했고, 말 그대로 작은거를 큰거에..

2교시 3번 하나라도 긁었다면? 2020년 8월 16일쯤인가.. 개학하고 시작한 알고리즘이 여기까지 왔다. nypc에서, 그동안 코드 복붙식으로 해왔던 공부가 안 된다는걸 알고, 문제를 맞추기 위해 푸는 것이 아니라 그저 탐구를 위해 공부했다. 그러니까 늘더라 공부 내팽겨쳐서 국어 영어가 둘다 3등급까지 떨어졌지만, 왜인지 수학은 1등급까지 올랐음

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

이분탐색의 문제가 아닌줄 알았는데..

G는 풀이를 아는데 시간이 부족해서 못풀었다 F2는 에디토리얼 보고도 뭔소린지 모르겠음 codeforces.com/contest/1520 Dashboard - Codeforces Round #719 (Div. 3) - Codeforces codeforces.com A 단순 구현문제 B 1, 11, 111, 1111... 이 수들로 나눈 몫(과 9의 최솟값)을 ans에 더해주면 나온다. C 홀수 나열 후 짝수 나열. 2*2는 불가능하다 (n=4 예시) 1 3 5 7 9 11 13 15 2 4 6 8 10 12 14 16 D \(a_{j} - j = a_{i} - i\)를 만족하는 순서쌍 (i, j)의 개수를 찾는 것이다. 배열의 값에 인덱스를 뺀 수의 개수인 \(x\)를 센 다음, \(_{x}C_{2}\)..

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)\)항까지..