코드포스
-
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..
-
1521-B, *1300코드포스 2021. 8. 1. 21:28
Problem - 1521B - Codeforces codeforces.com 문제 크기가 $n(1\leq n \leq 10^{5})$인 수열 $a_{1}a_{2}...a_{n-1}a_{n}$이 주어진다 인접한 항이 서로소가 되게 수열의 값을 변경시켜라 (단, $\mathrm{min(a_{i},\ a_{j})=min(x,\ y)}\ \text{and}\ i\neq j,\ a_{i},\ a_{j}\rightarrow x,\ y$) $O(n)$ $(a,\ a+1)=1$임을 이용한다 준 수열의 최소값이 $m$이라고 하면 준 수열을 다음과 같이 바꾼다 $$...,m+2,\ m+1,\ m,\ m+1,\ m+2,\ ...$$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20..
-
1534-C, *1300코드포스 2021. 8. 1. 18:04
Problem - 1534C - Codeforces codeforces.com 문제 $A \in \mathfrak{Mat_{\text{2, n}}}(\mathbb{N})$ 행렬 A에서 같은 열이나 같은 행에 같은 수가 없는 상태를 solve 라고 한다 solve 상태인 A가 주어졌을때 임의의 열의 두 수의 자리를 바꿔서 만들 수 있는 solve 상태 행렬의 수는? $O(nlog\ n)$ 1 2 3 4 5 2 1 4 5 3 위와 같은 solve 상태의 행렬 A가 주어졌다고 하자 첫번째 열을 바꾸면 첫 행에 2가 두개가 되므로 두번째 열도 바꿔야한다 이런식으로 동시에 바뀌어야 하는 열을 같은 집합으로 나타낸다면 $$S=\left \{ \left \{ A^{1},\ A^{2} \right \},\ \left ..
-
1538-C, *1300코드포스 2021. 8. 1. 16:48
Problem - 1538C - Codeforces codeforces.com 문제 크기가 $n(1\leq n \leq 2 \cdot 10^{5})$인 수열 $a_{1}a_{2}...a_{n-1}a_{n}$이 주어진다 $l\leq a_{i}+a_{j} \leq r$인 $i,\ j(i \neq j)$의 개수를 구하라 $O(nlog\ n)$ 먼저 준 수열을 sort 한다 $O(nlog\ n)$ 이제 모든 원소 각각을 뽑았을 때, 조건을 만족하는 원소의 왼쪽 index와 오른쪽 index를 구해서 개수를 구한다 예를 들어 $[l,\ r] = [5,\ 8]$, 수열을 $[1,\ 2,\ 3,\ 4,\ 5]$ 라고 하자. ( ) 은 조건을 만족하는 수들이고 | 은 수를 뽑을 때 칸막이 오른쪽 수들만을 고려한다는 의..
-
1555-B, *1300코드포스 2021. 7. 31. 15:16
Problem - 1555B - Codeforces codeforces.com 풀이 너비가 $W$, 높이가 $H$인 배치도에 2개의 x-y축에 나란한(axis-aligned) 두 개의 책상을 배치한다 첫번째 책상이 먼저 배치되어 있다 두번째 책상의 너비$w$와 높이$h$가 주어질 때, 첫번째 책상을 이동하여 두 번째 책상을 배치할 수 있나? 있으면 첫번째 책상을 최소 얼만큼 움직여야함? $O(t)$ 책상을 배치하는 경우는 다음과 같이 나눠진다 첫번째 책상을 기준으로 두 번째 책상은 i) 상, 하에만 배치 가능 ii) 좌, 우에만 배치 가능 iii) 상, 하, 좌, 우 배치 가능 iv) 안됨 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..