코드포스
-
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..
-
1366-B, *1300코드포스 2021. 7. 24. 23:01
Problem - 1366B - Codeforces codeforces.com 문제 순열 $a_{1}a_{2}...a_{n},\ (1\leq n\leq 10^{9})$에서 $a_{x} = 1$이고 나머지는 0 구간 $[l,\ r]$ 내의 두 index 값을 한번 바꾼다. $a_{i},\ a_{j} = a_{j},\ a_{i}$ ~ operation shuffle shuffle 은 $m(1\leq m \leq 100)$번 수행한다 $O(tm)$ 1이 존재할 수 있는 index 의 왼쪽과 오른쪽 끝을 각각 $lp,\ lp$에 저장하자 구간 $[l,\ r]$이 주어졌을 때, $lp$, 혹은 $rp$가 이 구간에 포함된다면 1을 주어진 구간까지도 옮길 수 있다 1 2 3 4 5 6 7 8 9 10 11 12 1..
-
25-A, *1300코드포스 2021. 7. 24. 22:09
Problem - A - Codeforces codeforces.com 문제 순열 $a_{1}a_{2}...a_{n},\ (3 \leq n \leq 100)$에서 evenness(홀수 인지 짝수인지)가 다른 원소 하나의 index? $O(n)$ 홀수, 짝수 각각 가장 늦게 나오는 값의 index 를 저장한다 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 #include #define endl "\n" using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n; cin >> n; int last_odd..
-
467-B, *1100코드포스 2021. 7. 24. 15:40
Problem - 467B - Codeforces codeforces.com 문제 이진수 집합 $\left \{ x_{1},\ x_{2}, ...\ ,\ x_{m} \right \},\ (1 \leq m \leq 1000,\ 1 \leq n \leq 20,\ 1 \leq x_{i} \leq 2^{n}-1)$ 중 $x_{m+1}$와 각각의 자릿수를 비교했을 때 다른 비트가 $k$이하인 원소의 개수는? $O(mn)$ 정도 알고리즘은 통과할 수 있다 $O(mn)$ 두 이진수 $a$, $b$에서 자리수는 같은 데 다른 비트의 수는 $\text{a^b}$에서 1인 bit 수를 세면 된다 $O(log\ \text{a^b})$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20..
-
1327-A, *1100코드포스 2021. 7. 24. 14:21
Problem - 1327A - Codeforces codeforces.com 문제 $t(1 \leq t \leq 10^{5})$번의 test case 로 구성되어 있다 $n(1 \leq n \leq 10 ^{7})$이 서로다른 $k(1 \leq k \leq 10^{7})$개의 홀수 자연수의 합이 될 수 있나? ~ ! ! 가 $O(log\ n)$ 정도의 알고리즘이면 통과할 수 있다 $O(t)$ $k$가 주어졌을 때 ! 가 가능한 $n$들의 집합을 구하자 서로 다른 $k$개의 홀수 자연수 합의 최소값은 $$\sum_{i=1}^{k}(2i-1) = k^{2} \Rightarrow n \geq k^{2}$$ 또한, $$\mathrm{Sum\ of\ k\ odd\ number} = \left. \begin{ca..
-
1335-C, *1100코드포스 2021. 7. 23. 21:27
Problem - 1335C - Codeforces codeforces.com 문제 $n(1 \leq n \leq 2 \cdot 10^{5})$개의 수 중 일부를 사용하여 크기가 같은 두 개의 집합 $A,\ B$을 구성한다, $\left | A \right | = \left | B \right |$ $A$에는 같은 수가 들어가면 안된다 $B$에는 같은 수만 들어가야 한다 $\left | A \right | = \left | B \right |$를 최대로 구성할 때 집합의 크기는? $O(nlog\ n)$ 정도의 알고리즘은 통과할 수 있다 $O(nlog\ n)$ 수의 개수를 세서 map에 보관하자 $O(nlog\ n)$ 값 3 5 7 8 개수 1 2 3 4 $=\mathrm{maxval}$ i) $\math..
-
368-B, *1100코드포스 2021. 7. 23. 16:24
Problem - 368B - Codeforces codeforces.com 문제 배열 $a = a_{1}a_{2} \cdot \cdot \cdot a_{n},\ (1 \leq n \leq 10^{5})$에 대해 $a_{l}a_{l+1} \cdot \cdot \cdot a_{n}$ 중 서로 다른 수가 몇 개인지 $m(1 \leq m \leq 10^{5})$번 출력 $O(nlog\ n)$ 정도의 알고리즘은 통과할 수 있다 $O(log\ n!)$ 가장 큰 $l$부터 답을 구하여 배열 $arr[l]$에 기록한다 $a_{n}$을 set $s$ 에 삽입한다. 그러면 $O(log\ \mathrm{s.size})$ $$ans[n] = \mathrm{s.size}$$ $a_{n-1}$을 set $s$ 에 삽입한다. 그..