Cabbage Leaves Cabbage Leaves

전체 글

• 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$ 에 삽입한다. 그..

• 313-B, *1100

  코드포스 2021. 7. 23. 15:44

  Problem - 313B - Codeforces codeforces.com 문제 문자열 $s = s_{1}s_{2}\cdot \cdot \cdot s_{n},\ (2 \leq n \leq 10^{5})$에 대해 $s_{i}=s_{i+1}$인 $i \in [l,\ r)$의 개수를 $m(1 \leq m \leq 10^{5})$번 출력 $O(nlog\ n)$ 알고리즘은 통과할 수 있다 $O(n)$ prefix sum 을 이용한다 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 #include #define endl "\n" using namespace std; string s; int prefix_sum[100001] {}; int mai..

• 456-A, *1100

  코드포스 2021. 7. 23. 14:21

  Problem - 456A - Codeforces codeforces.com 문제 비싼데 더 구린 노트북이 있나? $O(nlog\ n)$ 정도 알고리즘은 통과가능하다 $O(nlog\ n)$ 가격을 기준으로 sort 하고 $O(nlog\ n)$ 낮은 가격부터 2개씩 비교하면서 비싼데 더 구린 노트북이 있는지 본다 $O(n)$ 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 #include #define endl "\n" using namespace std; vector v; int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int ..