코드포스
-
313-B, *1100코드포스 2021. 7. 23. 15:44
Problem - 313B - Codeforces codeforces.com 문제 문자열 $s = s_{1}s_{2}\cdot \cdot \cdot s_{n},\ (2 \leq n \leq 10^{5})$에 대해 $s_{i}=s_{i+1}$인 $i \in [l,\ r)$의 개수를 $m(1 \leq m \leq 10^{5})$번 출력 $O(nlog\ n)$ 알고리즘은 통과할 수 있다 $O(n)$ prefix sum 을 이용한다 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 #include #define endl "\n" using namespace std; string s; int prefix_sum[100001] {}; int mai..
-
456-A, *1100코드포스 2021. 7. 23. 14:21
Problem - 456A - Codeforces codeforces.com 문제 비싼데 더 구린 노트북이 있나? $O(nlog\ n)$ 정도 알고리즘은 통과가능하다 $O(nlog\ n)$ 가격을 기준으로 sort 하고 $O(nlog\ n)$ 낮은 가격부터 2개씩 비교하면서 비싼데 더 구린 노트북이 있는지 본다 $O(n)$ 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 28 29 30 31 32 #include #define endl "\n" using namespace std; vector v; int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int ..
-
519-B, *1100코드포스 2021. 7. 23. 13:46
Problem - 519B - Codeforces codeforces.com 문제 크기가 $n(3 \leq n \leq 10^{5})$배열에서 원소가 2번 빠진다. 빠진 원소는? $O(nlog\ n)$ 알고리즘은 통과할 수 있다 $O(nlog n)$ 배열 $a$에서 원소 하나를 빼면 배열 $b$가 된다고 하자 $a$ 와 $b$를 sort하고 $O(nlog\ n)$ 앞부분부터 차례로 비교한다 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 28 29 30 31 32 33 34 35 36 37 38 39 #include #define endl "\n" using namespace std; int n; int a[100001] {..
-
363-B, *1100코드포스 2021. 7. 22. 21:27
Problem - 363B - Codeforces codeforces.com 문제 $n(1 \leq n \leq 1.5\cdot 10^{5})$개의 수가 나열되어 있다 연속된 $k$개의 수의 합이 가장 작은부분은 어디인가? $O(nlog \ n)$ 정도 알고즘은 통과할 수 있다 $O(n)$ 누적합을 저장하는 배열($acc$)을 만들면 $O(n)$ $$acc[i] - acc[i-k]$$ 을 이용하여 $i-k+1$부터 $i$까지 원소의 합을 구할 수 있다 이제 모든 경우에 대해 값을 비교하여 최솟값을 구한다 $O(n-k)$ 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 28 29 30 31 32 33 34 35 #include..
-
706-B, *1100코드포스 2021. 7. 22. 20:36
Problem - 706B - Codeforces codeforces.com 문제 $n(1 \leq n \leq 10^{5})$개의 가게에서 어떤 음료수를 판다 $q(1 \leq q \leq 10^{5})$번, $m_{i}$원이 있을 때 최대 몇 개의 가게에서 그 음료를 살 수 있는지(!) 출력한다 ! 은 $O(log \ n)$으로 동작해야 한다. 그러면 알고리즘이 $O(qlog \ n)$으로 동작하게 된다 $O(nlog\ n)$ 각 가게에서의 음료 가격을 오름차순으로 정렬하여 $O(nlog\ n)$ $q$번 이진탐색으로 $m_{i}$가 몇 번째에 위치하는지 구한다 $O(qlog\ n)$ 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..
-
158-B, *1100코드포스 2021. 7. 21. 14:33
Problem - 158B - Codeforces codeforces.com 문제 $ n $개의 그룹이 있고, 각 그룹에는 $ s_{i}(1\leq s_{i} \leq4) $ 명의 사람이 있다 모든 사람이 최대 4명이 탈 수 있는 택시로 이동을 한다. 같은 그룹에 있는 사람들은 같은 택시를 타야한다 필요한 택시의 최소 수? O(1) Greedy let 편의상 $s_{i}=k$인 그룹을 $s_{k}$이라 부르자 $s_{4}$은 여석없이 하나의 택시를 탄다($s_{4}$가 없어질때까지 반복) $s_{3}$이 먼저 택시에 타고 $s_{1}$인 그룹이 있다면 여석에 채워넣는다($s_{3}$이 없어질때까지 반복) $s_{2}$가 먼저 택시에 타고 $s_{2}$가 남아 있다면 여석에 채워넣는다($s_{2}$가 없어..