분류 전체보기
-
Codeforces Round 905 (Div. 3)코드포스 2024. 2. 29. 18:58
Dashboard - Codeforces Round 905 (Div. 3) - Codeforces codeforces.com C i) k = 2, 3, 5 즉, 소수일 때 배열의 원소가 k의 배수가 되게 하는 최소 연산 횟수를 구하면 된다 ii) k = 4 일때 cnt[i] := 4로 나눴을 때 나머지가 i인 원소의 개수 if cnt[0] > 0 or cnt[2] >= 2 : 배열의 곱이 4의 배수이다. -> 답이 0 elif cnt[3] > 0 : 나머지가 3인 원소에 1을 더해주면 배열 원소의 곱이 4의 배수이다 -> 답이 1 else: cnt[0] = 0 이고 cnt[2] 답은 2-cnt[2] D 이때 주의할 점은 i) multiset이 empty인 경우 예외처리 해야한다 ii) multiset.e..
-
Codeforces Round 828 (Div. 3)코드포스 2024. 2. 27. 20:01
Dashboard - Codeforces Round 828 (Div. 3) - Codeforces codeforces.com C 방법 1 방법 2 - binary search E1 제한이 다음과 같다. 1 ≤ a < x ≤ c ≤ 10⁵ 1 ≤ b < y ≤ d ≤ 10⁵ 10⁵ 이하의 자연수는 1초안에 충분히 순회할 수 있으므로(대략 1초에 10⁷ 연산) x를 brute force로 돌리고 y를 O(1) 만에 찾아도 된다. 변수를 바꿔서도 마찬가지. E2 예제로부터 필요한 내용을 관찰하자. a, b, c, d = 8, 9, 15, 18 라고 하자. 8 < x ≤ 15 9 < y ≤ 18 이므로 x ∈ {9, 10, 11, 12, 13, 14, 15} y ∈ {10, 11, 12, 13, 14, 15, ..
-
Codeforces Round 891 (Div. 3)코드포스 2024. 2. 27. 18:17
Dashboard - Codeforces Round 891 (Div. 3) - Codeforces codeforces.com B greedy 방법으로 낮은 자리수부터 보다가 반올림 할 수 있으면 하고, 그렇지 않으면 안하면 된다. F t² + xt + y = 0의 두 해가 ai, aj 임을 이용하는 문제다. G 되게 흥미로운 문제였다. 결국에는 editorial을 보고 풀었다. 배경지식으로는 크루스칼 알고리즘이 필요하다. 다음 관찰까지는 해냈다. 간선이 존재하지 않는 임의의 edge (u, v) 에 대해 u와 v를 연결하는 경로에서의 간선 가중치의 최대값을 w라고 하자. 그러면 edge (u, v)의 가중치는 0, w+1, w+2, ... , S 의 값을 가질 수 있다. (가중치가 0이면 없는 간선 취급..