전체 글
-
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..
-
1512-C, *1200코드포스 2021. 8. 8. 16:51
Problem - 1512C - Codeforces codeforces.com 문제 길이가 $n(1\leq n \leq 2 \cdot 10^{5})$이고 0, 1, ? 로만 구성된 문자열 $s$가 주어진다 s의 ? 를 0과 1로 바꿔서 0과 1이 각각 $a,\ b$개인 Palindrome을 만들 수 있는가? $O(n)$ 우선 0과 1이 각각 $a,\ b$개여야 한다는 조건만을 생각하며 문자열을 변형시키자 그 후, 문자열이 Palindrome이고 0과 1이 $a,\ b$개인지 검사한다 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..
-
1511-B, *1100코드포스 2021. 8. 8. 14:59
Problem - 1511B - Codeforces codeforces.com 문제 $\mathrm{gcd(a,\ b)}$가 $c$ 자리수이고 각각의 자리수가 $a,\ b(1\leq a,\ b \leq 9)$인 두 수 A, B를 구하라 $O(1)$ $c$ 자리의 소수를 $\mathrm{gcd(A,\ B)}$라고 두고 A 와 B 를 만든다 $\mathrm{(A,\ B)}$가 변하면 안되므로 $\mathrm{(A,\ B)}$에 서로다른 소수를 곱하여 A 와 B 를 만든다 Claim 각각의 자리수가 $a,\ b(1\leq a,\ b \leq 9)$인 두 수 A, B 에 대해 두 수의 최고자리수가 모두 3 이하면 AB는 a+b-1 자리수이다 $\because$ AB의 자릿수는 A와 B의 최고자릿수의 곱만 보면 ..
-
1454-D, *1300코드포스 2021. 8. 7. 20:37
Problem - 1454D - Codeforces codeforces.com 문제 $n(2\leq n \leq 10^{10})$이 주어질 때 다음을 만족하는 수열 $a_{1},\ a_{2},\ ...,\ a_{k}$의 최대 길이를 구하라 $a_{1} \cdot a_{2} \cdot \cdot \cdot a_{k} = n$ $a_{i}\mid a_{i+1},\ i=1,\ 2,\ ...,\ k-1$ $O(\sqrt n)$ $n=2^{e_{0}}p_{1}^{e_{1}}p_{2}^{e_{2}}\cdot \cdot \cdot p_{t}^{e_{t}}$ $n$의 표준분해가 위와 같다고 할 때, 수열 {a}의 최대길이는 $$\mathrm{max(e_{0},\ e_{1},\ ...,\ e_{t})}$$ 1 2 3 4..
-
11000백준 2021. 8. 3. 21:44
11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제 $n(1 \leq n \leq 2\cdot 10^{5}$개의 수업을 가능하게 하기 위한 최소 강의실의 개수? 강의시간은 $[s,\ e)$ 이다(강의시간에 시각 e 는 포함하지 않는다) $O(nlog\ n)$ 빨리 시작하는 순서로 고려한다 기존 강의실에 배정할 수 있으면 배정하고 못한다면 새로운 강의실을 만든다 위의 알고리즘을 진행하면서 강의실을 가장 많이 사용할 때의 강의실 수가 최적해이다 위 그림에서 실선 t 와 만나는 강의의 개수를 $U(t)$라고 하자 Claim 준 알고리즘의 해는 (수업이 최대로 겹..