분류 전체보기
-
16237, bronze 1백준 2021. 8. 16. 16:08
16237번: 이삿짐센터 첫째 줄에 A, B, C, D, E가 주어진다. (0 ≤ A, B, C, D, E ≤ 1,000) www.acmicpc.net 문제 1kg, 2kg, ..., 5kg 인 물건이 각각 $0\leq a,\ b,\ c,\ d,\ e \leq 1000$개 있다 물건들을 모두 옮기는데 최대 5kg 까지 담을 수 있는 바구니를 사용할 때 최소 몇 개가 필요한가? $O(\mathrm{stuff_{max}}log\ \mathrm{stuff_{max}})$ Greedy 가장 무거운 물건을 우선으로 가방에 담는다 무거운 물건을 우선으로, 이미 물건이 담긴 가방에 담을 수 있다면 담고, 없다면 새로운 가방에 물건을 넣는다 Claim 최적 알고리즘을 사용하여 가방에 넣은 물건들의 자리를 사용한 가방의..
-
1553-C, *1200코드포스 2021. 8. 15. 21:32
Problem - 1553C - Codeforces codeforces.com 풀이 두 팀 $odd$와 $even$이 돌아가면서 승부차기를 한다 $1$은 성공, $0$은 실패, $?$은 성공 또는 실패를 의미할 때, 최소 몇번의 킥을하게 되는가? $O(1)$ 승부차기에서 더 이상 킥을 해도 의미가 없는경우는 '지고 있는 팀이 남은 킥을 모두 성공해도 점수를 뒤집을 수 없을 때' 이다 따라서 킥의 횟수를 줄이려면 한쪽 팀이 유리하게 $?$를 바꿔야한다 i) $?$를 $odd$팀이 유리하게 바꿨을 때 최소 킥의 횟수 ii) $?$를 $even$팀이 유리하게 바꿨을 때 최소 킥의 횟수 를 각각 구하며 더 작은 값이 구하려는 값이다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18..
-
1553-D, *1500코드포스 2021. 8. 15. 19:45
Problem - 1553D - Codeforces codeforces.com 문제 문자열 $s$와 $t$가 주어진다 $s$의 왼쪽부터 문자 하나당 시행1 이나 시행2를 한다 시행1. 키보드로 그 문자를 누른다 시행2. 키보드로 그 문자를 누르지 않고 Backspace 를 누른다 ex) abcd 에서 순차적으로 1121 시행했다면 $\mathrm{a\rightarrow ab \rightarrow a\rightarrow ad}$ abdd 에서 순차적으로 2121 시행했다면 $\ \rightarrow b \rightarrow \ \rightarrow d$ $s$로 부터 $t$를 작성할 수 있는가? $O(\left | s \right |)$ $sp,\ tp$ 두개의 포인터를 사용하여 $t$의 뒤쪽부터 앞쪽으로..
-
1554-A, *800코드포스 2021. 8. 15. 16:52
Problem - 1554A - Codeforces codeforces.com 문제 크기가 $n(2\leq n \leq 10^{5})$인 배열 $a_{1}a_{2}...a_{n}(1\leq a_{i} \leq 10^{6})$이 주어질때 $\mathrm{min(a_{l}a_{l+1}...a_{r})\cdot max(a_{l}a_{l+1}...a_{r})},\ (1\leq l < r \leq 10^{5})$의 최대값을 구하라 $O(n)$ Claim 크기가 2인 Optimal interval $[l,\ r=l+1]$가 존재한다 $\because$ 최적구간의 크기가 3이상이라고 가정하자. 구간에서 가장 큰 값을 $b$, 제일 작은 값을 $s$, 그 외의 값을 $m(s < m < b)$이라고 하자. 그러면 i) ..
-
1554-C, *1800코드포스 2021. 8. 14. 11:23
Problem - 1554C - Codeforces codeforces.com 문제 $n,\ m(1\leq n,\ m \leq 10^{9})$이 주어질때 $S=\left \{ n \oplus 0,\ n \oplus 1,\ ...,\ n \oplus m \right \}$에 속하지 않는 음이아닌 최소 정수를 구하라 $O(tlog\ n)$ 음이아닌 정수 $k$가 집합 $S$의 원소라면 $\exists x \in \mathbb{Z},\ 0\leq x \leq m \quad \text{s.t. } n\oplus x = k \Leftrightarrow n\oplus k = x$ 따라서 $n \oplus k \geq m+1$인 최소 $k$가 구하려고 하는 값이다 i) $n \geq m+1 \rightarrow k ..
-
1554-D, *1800코드포스 2021. 8. 13. 14:26
Problem - 1554D - Codeforces codeforces.com 문제 다음 조건을 만족시키는 길이가 $n(1\leq n \leq 10^{5})$인 문자열$s$을 출력하라 $s$의 부분문자열의 개수는 항상 홀수개여야 한다 ~ ! ex) uuuauu ㅇ u -5개 ㅇ uu - 3개 ㅇ uuu - 1개 ㅇ au - 1개 ... $O(n)$ Claim 다음과 같은 형태의 문자열을 생각하자 $$\begin{aligned} \text{uu}&\text{lu}\\ \text{uuu}&\text{luu}\\ \text{uuuu}&\text{luuu}\\ \end{aligned}$$ 이와 같은 규칙을 갖는 문자열은 조건 ! 을 만족한다 $\because$ 오직 한번만 등장하는 문자를 포함하는(l 을 포함하..
-
1513-B, *1400코드포스 2021. 8. 11. 11:29
Problem - 1513B - Codeforces codeforces.com 문제 수열 $a_{1}a_{2}...a_{n}$이 주어질 때, 다음 조건을 만족시키는 수열 $a_{p_{1}}a_{p_{2}}...a_{p_{n}}$의 개수? $a_{p_{1}}\& a_{p_{2}}\&\cdot \cdot \cdot \& a_{p_{i}} = a_{p_{i+1}}\& a_{p_{i+2}}\&\cdot \cdot \cdot \& a_{p_{n}}(1\leq i < n)$ ... ! $O(nlog\ n)$ bitwise operation인 &가 이용되므로 비트의 각 자리수마다 조건 ! 을 만족하는 집합을 각각 구한뒤 그것들의 교집합을 이용하면 되겠다 ex) 01(2), 11(2) 가 주어졌다고 하면 오른쪽부터 1..
-
1547-C, *1100코드포스 2021. 8. 10. 16:14
Problem - 1547C - Codeforces codeforces.com 문제 Monocarp 와 Polycarp가 돌아가며 일을한다 두 명의 업무기록이 각각 주어질때 실현 가능한 업무기록이면 순서를, 불가능하면 -1 을 출력하라 $O(n+m)$ 줄을 추가하는 일을 최우선으로 시뮬레이션해본다 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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 #include #define endl "\n" #define loop(i, n) for(int i = 1; i > t; w..