분류 전체보기
-
Codeforces Round 719 (Div. 3)코드포스 2024. 1. 4. 14:03
Dashboard - Codeforces Round 719 (Div. 3) - Codeforces codeforces.com F2 binary search를 이용하여 문제를 해결하면 된다. 다만 한번 날렸던 query는 어딘가에 저장(cache)하여 재활용을 해야하는 문제이다. 방법 1 - cache로 map 이용 이 방법에서는 query의 구간을 항상 위와 같은 형태(binary tree)가 되게 질의하고 질의의 결과를 cache에 저장한다. 위 그림에서 각각의 주황색 박스는 하나의 query를 의미한다. 예를들어 구간 [1, 4] query는 가장 왼쪽 가장 위쪽에 위치한 박스이다. 박스에 적혀있는 숫자는 query의 결과(구간에 속하는 1의 개수)를 의미한다. 방법 2 - cache로 BIT 이용
-
Codeforces Round 918 (Div. 4)코드포스 2024. 1. 3. 14:39
Dashboard - Codeforces Round 918 (Div. 4) - Codeforces codeforces.com A 정수 a, b, c 중 2개가 같고 다른 하나는 다르다고 하자. 그 수는 (a^b^c) 이다. B 방법 1 - 개수 세기 방법 2 - ^ 응용 C F nested interval의 수를 세면 된다. 즉, a[i] b[j] 인 순서쌍 (i, j)의 개수를 세면 된다. 방법 1 - 흑마법 방법 2 - 좌표 압축과 BIT G
-
upper_bound of binomail coefficients아무거나적어~ 2023. 12. 21. 18:15
Proof for the upper bound and lower bound for binomial coefficients. I have seen the bounds $\left(\frac{n}{k}\right)^k \leq {n \choose k} \leq \left( \frac{en}{k}\right)^k$ for integers $n \geq k >0$ for the binomial coefficient. I can prove the upper bound in t... math.stackexchange.com
-
Declare Comparator For Set of Pair in C++아무거나적어~ 2023. 12. 7. 20:36
How to Declare Comparator For Set of Pair in C++? - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions. www.geeksforgeeks.org
-
Static Range Minimum QueriesCSES 2023. 12. 7. 16:08
방법 1 - Segment tree Build a Range minimum query segment tree in O(N) time and answer each query in O(logN). 방법 2 - Sparse Table Sparse Table - Algorithms for Competitive Programming Sparse Table Sparse Table is a data structure, that allows answering range queries. It can answer most range queries in $O(\log n)$, but its true power is answering range minimum queries (or equivalent range maximum ..
-
Codeforces Round 909 (Div. 3)코드포스 2023. 12. 7. 13:07
Dashboard - Codeforces Round 909 (Div. 3) - Codeforces codeforces.com B 방법 1 - backtracking 모든 n 약수 k에 대해 maximum absolute difference를 구한다. 약수의 개수는 대략 $ O(n^{\frac{1}{3}}) $ 이고 각각의 약수에 대해 O(n) 시간에 최대 무게 차이를 계산할 수 있다. (물론 prefix sum으로 전처리해서 더 빨리 구할 수도 있음) 방법 2 - brute force k를 1부터 n까지 증가해가며 최대 무게 차이를 계산하자. 이때 계산은 prefix sum을 이용해야 시간초과가 나지 않는다. 무게 차이를 계산 할 때는 k칸씩 뛰어가며 연산을 하므로 시간 복잡도는 harmonic seri..