코드포스
-
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이면 없는 간선 취급..
-
Codeforces Round 479 (Div. 3)코드포스 2024. 2. 14. 22:17
Dashboard - Codeforces Round 479 (Div. 3) - Codeforces codeforces.com B 방법 1 - 메모리 절약 방법 2 - 메모리 좀 씀 C 방법 1 - binary serarch O(lg max(ai) x lg(N) ) 방법 2 - index의 의미 이용 O(n lg N) 0-based index에서 index i의 앞에는 i개의 수가 있다. D 방법 1 - 위상정렬 O(N² + V + E) 이때 |V| ≤ N, |E| ≤ N² 방법 2 - 소인수의 개수 관찰 O(N lg max(ai) + N lg N) 올바른 순서의 순열은 각 원소의 (소인수 3의 개수)는 줄어들고 (소인수 2의 개수)는 늘어난다 F 방법 1 - binary serarch 배열 v의 작은 원..
-
Codeforces Round 481 (Div. 3)코드포스 2024. 2. 14. 20:59
Dashboard - Codeforces Round 481 (Div. 3) - Codeforces codeforces.com C 방법 1 증가량에 주목하여 코딩. b[i] := B[i] - B[i-1] 이때, B는 입력으로 주어진 배열 B q에 배열 B의 변화량 b를 쌓아가며, p index 방의 수용 인원수를 넘어가면(p > a[p]) 다음 방을 고려(p+=1) 한다. 방법 2 p := x번째 방이 있을 수 있는 최소 index sum := 지금까지 본 방들의 호실 수의 합 D
-
Codeforces Round 702 (Div. 3)코드포스 2024. 1. 5. 05:21
Dashboard - Codeforces Round 702 (Div. 3) - Codeforces codeforces.com E 방법 1 - greedy 두 사람에 대해 [token이 많은 경우를 강하다, 적은 경우를 약하다]라고 표현하도록 하자. 어떤 사람 a가 우승하는 경우를 생각해보자. a가 참가하지 않은 경기가 일어나는 것은 a에게 불리하다. 왜냐하면 결국에 만나야하는 상대의 능력치가 증가하기 때문이다. 따라서 어떤 사람 a가 우승할 수 있는지는 다음과 같은 greedy 방식으로 확인이 가능하다. a가 능력치가 낮은 순으로 모든 상대와 대결했을 때 우승할 수 있으면 우승 가능하고 그렇지 않으면 우승 가능하지 않다. index 1 2 3 4 5 a[i](token value) 2 3 5 9 20 r..
-
Codeforces Round 713 (Div. 3)코드포스 2024. 1. 4. 14:52
Dashboard - Codeforces Round 713 (Div. 3) - Codeforces codeforces.com A 배열을 정렬하면 구하려는 수는 처음이나 끝에 위치하게 된다. C 아래 코드의 주석 순서로 greedy 알고리즘을 진행하면 된다. E 1부터 n까지의 자연수 중, 서로 다른 수 k개의 합의 범위를 생각해보자. 하한은 1 + 2 + ... + k 이고 상한은 n+ (n-1) + ... + (n-k+1) 이다. 이제 1부터 5까지의 자연수 중 합이 10인 서로 다른 수 3개의 수를 만들어보자. 10이 하한(1+2+3=6)과 상한(3+4+5=12) 사이의 수 이므로 가능하다. 하한이 되는 경우에서 부족한 값을 더해서 만들자. 1 2 3 합이 10이 되기 위해서는 4만큼이 부족하다. 따..