Cabbage Leaves Cabbage Leaves

분류 전체보기

• 1553-B, *1300

  코드포스 2021. 7. 28. 21:50

  Problem - 1553B - Codeforces codeforces.com 문제 문자열 $s(1 \leq \left | s \right | \leq 500)$와 $t(1 \leq \left | t \right | \leq 2 \cdot \left | s \right |-1)$가 주어진다 스케너가 임의의 $s$ 문자 위에서 오른쪽으로 갔다가 왼쪽으로 차례로 읽을 때 $t$로 읽을 수 있는가? $O(t^{2}s)$ 먼저 스캔했을 때 $t$가 나올 수 있는 문자열을 구하자 --- ! 스케너가 오른쪽으로 갔다가 왼쪽으로 가기 시작하는 문자를 $key$라고 하자 $t$의 각 자리별로 $key$라고 생각하고 ! 을 구한다 $O(t^2log\ t)$ 스케너는 항상 오른쪽을 먼저 가기 때문에 ! 의 제일 오른쪽에는..

• 459-B, *1300

  코드포스 2021. 7. 28. 15:34

  Problem - 459B - Codeforces codeforces.com 문제 $n(2 \leq n \leq 2 \cdot 10^{5})$개의 $b(1 \leq b \leq 10^{9})$가 주어진다 $b_{i},\ b_{j},\ i \neq j$ 차이의 최대값을 구하고 그 값이 나올 수 있는 경우의 수를 구하라 풀이 $b_{i}$의 최대값을 $\mathrm{max}$, 최솟값을 $\mathrm{min}$ 이라고 하자 i) $\mathrm{max=min}$ 차이의 최대값이 나오는 경우의 수는 $b$의 값에 따라 개수를 세서 구한다. $$\mathrm{(max\ value\ b\ number)} \times \mathrm{(min\ value\ b\ number)}$$ ii) $\mathrm{max \..

• 451-B, *1300

  코드포스 2021. 7. 28. 13:18

  Problem - 451B - Codeforces codeforces.com 문제 크기가 $n(1 \leq n \leq 10^{5})$인 배열이 주어진다 오직 한번만 배열의 일정 구간을 뒤집어서 배열을 오름차순으로 정렬할 수 있는가? $O(n)$ 문제의 상황을 감소하는 구간의 개수에 따라 나눠보자 (감소하는 구간 $[l,\ r]$이란 구간 내에서 감소하면서 $\mathrm{arr[l-1] < arr[l]\ and\ arr[r] < arr[r+1]}$을 만족) i) 감소구간이 0개 배열이 오른차순으로 정렬되어 있다는 의미 ii) 감소구간이 1개 감소구간을 뒤집으면 오름차순이 될 수도 있음 iii) 감소구간이 2개 이상 배열이 오름차순이 될 수 없다 1 2 3 4 5 6 7 8 9 10 11 12 13 14..

• 189-A, *1300

  코드포스 2021. 7. 27. 21:20

  Problem - 189A - Codeforces codeforces.com 문제 세 정수 $a,\ b,\ c(1 \leq a,\ b,\ c \leq 4000)$가 주어진다 길이가 $n(1 \leq n \leq 4000)$인 끈을 길이 $a,\ b,\ c$로만 자를 때 나오는 조각의 최대 개수는? $O(n)$ $DP_{i}$를 길이가 $i$인 끈을 길이 $a,\ b,\ c$로만 자를 때 나오는 조각의 최대 개수라고 하자. 그러면 $$\mathrm{DP_{i}=max(DP_{i-a},\ DP_{i-b},\ DP_{i-c})+1},\ \mathrm{Not\ all\ of\ DP_{i-a},\ Dp_{i-b},\ Dp_{i-c}=0}$$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1..

• 230-B, *1300

  코드포스 2021. 7. 27. 16:11

  Problem - 230B - Codeforces codeforces.com 문제 답을 $n(1 \leq n \leq 10^{5})$번 출력한다 $x(1 \leq x \leq 10^{12})$가 주어졌을 때, $x$의 양의 약수가 3개인가? $O(\sqrt{x}+nlog\ x)$ 양의 약수가 3개인 수는 $$p^{2},\ \mathrm{p\ is\ prime}$$ 꼴의 수이다 먼저, 에라토스테네스의 체(sieve of eratosthenes)를 이용하여 소수를 구하고 $O(\sqrt{x}log\ log\ \sqrt{x}) \approx O(\sqrt{x})$ 이 소수를 set 에 저장한다 $O(log\ \pi(\sqrt{x})!) \approx O(\sqrt{x})$ 이제 수들이 주어질 때마다 i) 완전제..

• 4-C, *1300

  코드포스 2021. 7. 25. 15:09

  Problem - 4C - Codeforces codeforces.com 문제 $n(1\leq n \leq 10^{5})$번 32자 이하의 알파벳 소문자로 이루어진 이름이 주어진다 처음보는 이름은 "OK", $k$번 본 이름은 "준_이름$k$" 를 출력한다 $O(nlog\ n)$ 정도의 알고리즘은 통과 가능하다 $O(nlog\ n)$ map을 이용하여 이름을 저장한다 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 #include #define endl "\n" using namespace std; map m; int main() { ios::sync_with_stdio(false); cin.tie(0), cout.ti..

• 1360-C, *1100

  코드포스 2021. 7. 25. 14:51

  Problem - 1360C - Codeforces codeforces.com 문제 두 자연수 $a$, $b$가 닮았다($a\sim b$)는 것을 다음과 같이 정의한다 $a \sim b \Leftrightarrow a\equiv b\ (mod\ 2)\ or \left | a-b \right |=1$ 짝수 $n(2\leq n \leq 50)$개의 원소가 주어졌을 때, 닮은 수끼리 모두 짝지을 수 있는가? --- ! $O(tn)$ $n$이 짝수 이므로 $n$개의 수를 다음 두 가지 경우 중 하나이다. i) 짝수가 짝수개, 홀수가 짝수개 ii) 짝수가 홀수개, 홀수가 홀수개 i) 인 경우 짝수는 짝수끼리, 홀수는 홀수끼리 짝지으면 된다. 즉, ! 가 가능하다 ii) 인 경우 $a\equiv b\ (mod\ 2..

• 82-A, *1100

  코드포스 2021. 7. 25. 12:24

  Problem - 82A - Codeforces codeforces.com 문제 queue에 {"Sheldon", "Leonard", "Penny", "Rajesh", "Howard"} 가 차례로 들어가 있다 queue에서 원소를 뺐을 때 나오는 사람이 콜라를 마시고 그 사람 이름 2개를 다시 queue에 넣는다 --- ! ! 를 $n(1 \leq n \leq 10^{9})$ 수행했을 때 마지막 콜라를 마시는 사람?? $O(log\ n)$ 정도의 알고리즘은 통과할 수 있다 $O(log\ n)$ q 0 1 2 3 4 value Sheldon Leonard Penny Rajesh Howard 배열 $q$가 위와 같다고 하자 Sheldon Sheldon Leonard Leonard Penny Penny Raj..