분류 전체보기
-
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
-
이분탐색에서 구간 [lo, hi]에 답이 없는 경우는 예외처리할 것실수모음 2024. 1. 29. 17:59
lo와 hi 범위 안에 avail이 true인게 반드시 존재해야 함. 그렇지 않으면 예외처리 할 것. // binary search sudo code lo, hi ← (답이 될 수 있는 가장 작은 값), (답이 될 수 있는 가장 큰 값) ans ← (답이 될 수 없는 값) while lo ≤ hi: mid = (lo+hi)/2 if avail(mid): ans = mid hi = mid - 1 // 경우에 따라 lo = mid + 1 else: lo = mid + 1 // 경우에 따라 hi = mid - 1 Problem - E - Codeforces codeforces.com 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..
-
-
-
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만큼이 부족하다. 따..