코드포스
-
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..
-
1526-B, *1400코드포스 2021. 8. 10. 15:05
Problem - 1526B - Codeforces codeforces.com 문제 $x(1\leq x \leq 10^{9})$가 주어질 때 $11,\ 111,\ 1111,\ 11111,\ ...\ $꼴 수의 합으로 표현될 수 있는지 결정하라 $O(1)$ Claim 어떤 수가 $11,\ 111,\ 1111,\ 11111,\ ...\ $꼴 수의 합으로 표현되면 $11$과 $111$의 합 만으로도 표현된다 $\because$ $$\begin{align*} 1111&=11 \times 100+11\\ 11111&=111 \times 100+11\\ 111111&=1111 \times 100+11\ \square \end{align*}$$ Claim $x$가 $11$과 $111$의 합으로 표현될 수 있을 때, ..
-
1557-A, *800코드포스 2021. 8. 10. 14:30
Problem - 1557A - Codeforces codeforces.com 문제 $n(2\leq n \leq 10^{5})$개의 수를 공집합이 아닌 2개의 집합으로 나눈다 각각의 집합 평균의 합을 생각할때 최대는 얼마인가? $O(n)$ let $\mathrm{S_{a}=\sum_{i=1}^{a}arrray [i],\ S_{r} = \sum_{i=a+1}^{n}array[i],\ 1\leq a \leq n-1}$ Note that array arranged arbitrary $$\begin{align*} \text{Want} &= \frac{S_{a}}{a}+\frac{S_r}{n-a}\\ &=\frac{(n-a)S_{a}+aS_{r}}{a(n-a)} \end{align*}$$ n은 상수이므로 구하는 ..
-
1557-B, *1100코드포스 2021. 8. 10. 13:39
Problem - 1557B - Codeforces codeforces.com 문제 중복된 원소가 없는 크기가 $n(1 \leq n \leq 10^{5})$인 배열이 주어진다 이 배열을 $k$개의 조각으로 나누어 오른차순으로 sort 할 수 있는가? $O(nlog\ n)$ 먼저 각 원소의 상대적인 크기 비교하여 $1$부터 $n$으로 indexing 하자 $O(nlog\ n)$ origin 3 -1 6 2 substitute 3 1 4 2 이제 오름차순으로 정렬되기 위한 최소 조각의 개수를 구하자 위와 같이 치환하여 생각할 때, $$\mathrm{array[i] \neq array[i-1]+1}$$ 이면 $\mathrm{array[i]}$와 $\mathrm{array[i-1]}$는 다른조각이어야 한다 $O..