코드포스
-
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
-
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..
-
Codeforces Round 797 (Div. 3)코드포스 2023. 12. 5. 10:04
Dashboard - Codeforces Round 797 (Div. 3) - Codeforces codeforces.com E $ \left[ \dfrac{b}{a}\right] =\left[ \dfrac{aq+r}{a}\right] =a+\left[ \dfrac{r}{a}\right] $ 으로부터 주어진 정수들을 K로 나눈 나머지만을 생각하여도 좋다. 합이 K를 넘게 쌍을 짓는 방법은 two pointer를 이용하면 된다. F permutation을 이용하여 문자열을 변환하다보면 독립된 사이클을 발견할 수 있다. 한편, 사이클 2개가 있고, 각각의 주기가 a, b라고 하자. 두 사이클은 모두 [a, b]번 이동하면 제자리로 돌아온다. 이는 n개의 사이클에 대해서도 n개의 LCM을 구하는 것으로 일반화..
-
Codeforces Round 640 (Div. 4)코드포스 2023. 11. 30. 16:22
Dashboard - Codeforces Round 640 (Div. 4) - Codeforces codeforces.com B 방법 1 - binary search 방법 2 - 관찰 N = 7이라고 가정하자. (1 2 3 4 5 6 7) (8 9 10 11 12 13 14) (15 16 17 18 19 20 21) ... 자연수 1부터 N개씩 하나의 블럭으로 생각하자. 그러면 하나의 블럭에는 N으로 나누어떨어지지 않는 수가 (N-1)개 존재한다. 따라서 K개의 나누어떨어지지 않는 수를 위해서는 적어도 K/(N-1)개의 블럭이 필요하다. G i) N부터 1까지 홀수들을 나열한다. ii) 4 2를 출력한다 iii) 6부터 N까지 짝수들을 나열한다. N = 10이면 다음과 같다. 9 7 5 3 1 4 2 6..
-
Codeforces Round 898 (Div. 4)코드포스 2023. 11. 27. 17:50
Dashboard - Codeforces Round 898 (Div. 4) - Codeforces codeforces.com B 가장 작은 값에 1을 더하는 것이 결과값(어떤 수에 1을 더하고 모든 수를 곱한 값)을 최대로 만드는데 최적이다 pf) basis step) 1개의 수에 대해서는 자명하다 2개의 수 a ≤ b에 대해, a(b+1) = ab + a ≤ ab + b = (a+1)b 이므로 작은 수에 1을 더하는 것이 최적이다. 2개 이상의 수들에 대해 생각하자. i) 0이 2개 이상이면 어떤 수에 1을 더하든 상관 없이 결과값은 0이다. 따라서 가장 작은 값에 1을 더하는 것이 최적이다. ii) 0이 1개이면 쉽게 생각할 수 있다. iii) 0이 존재하지 않는 n(≥ 2)개의 양의 정수에 대해 a..
-
Codeforces Round 898 (Div. 4)코드포스 2023. 11. 27. 17:47
Dashboard - Codeforces Round 898 (Div. 4) - Codeforces codeforces.com B 가장 작은 값에 1을 더하는 것이 결과값(어떤 수에 1을 더하고 모든 수를 곱한 값)을 최대로 만드는데 최적이다 pf) basis step) 1개의 수에 대해서는 자명하다 2개의 수 a ≤ b에 대해, a(b+1) = ab + a ≤ ab + b = (a+1)b 이므로 작은 수에 1을 더하는 것이 최적이다. 2개 이상의 수들에 대해 생각하자. i) 0이 2개 이상이면 어떤 수에 1을 더하든 상관 없이 결과값은 0이다. 따라서 가장 작은 값에 1을 더하는 것이 최적이다. ii) 0이 1개이면 쉽게 생각할 수 있다. iii) 0이 존재하지 않는 n(≥ 2)개의 양의 정수에 대해 a..
-
Codeforces Round 886 (Div. 4)코드포스 2023. 11. 27. 14:47
Dashboard - Codeforces Round 886 (Div. 4) - Codeforces codeforces.com D An arrangement that always minimizes the absolute difference between adjacent pairs is the array in sorted order. G 평면상의 직선 위에 있는 서로 다른 점의 개수를 세는 방법 H 병사들을 노드로, 병사간의 거리를 directed edge의 weight로 모델링한다. 이때 핵심은 양방향 간선을 모두 포함하여 임의의 노드에서 시작하여도 상관 없게 만드는 것! 그 후 dfs를 이용하여 모든 병사간의 거리를 결정한다. 마지막으로 모든 조건이 충족되는지 확인하면 된다. 6 5 1 2 2 2 3 4..