코드포스
-
1301-C, *1700코드포스 2021. 12. 24. 02:34
Problem - C - Codeforces codeforces.com 풀이 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 #include #define endl "\n" #define ooop(i, n) for(int i = 0; i t; while(t--){ int n, m; cin >> n >> m; if((n+1)/2 >= n-m) cout
-
1301-D, *2000코드포스 2021. 12. 24. 02:06
Problem - D - Codeforces codeforces.com 문제 오일러 경로에 관련된 문제다 풀이 ※ m = 1 인 경우 따로 처리해줘야한다 R ~ (m-1) 번 L ~ (m-1) 번 이후에는 다음 문자열이 (n-1) 번 반복된다 D/RUD/RUD/ ... /RUD ~ RUD 가 (m-1)개 LLL ... LLL ~ L 이 (m-1)개 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 58 59 60 61 62 63 64 65 66 67 68 69 70 7..
-
1295-D, *1800코드포스 2021. 11. 10. 16:42
Problem - D - Codeforces codeforces.com 문제 자연수 $a,\ m$이 주어질 때 $(a,m)=(a+x,m)$인 $x(0\leq x < m)$의 개수를 구하라 풀이 let d = (a, m), a = a'd m = m'd then, (a, m) = (a+x, m) d = (da'+x, dm') ... ! division algorithm 에 의해 x = dq + r, 0 ≤ r < d 인 정수 q, r 이 유일하게 존재한다 만약 r ≠ 0 이면 d $\nmid$ (da'+r) 이므로 모순이다(두 정수 a, b의 최대공약수는 a, b 를 모두 나눈다) 따라서 x = dq 꼴이고 0 ≤ x < m 이므로 q = 0, 1, 2, ... , m'-1 ! 을 좀더 정리하면 d = (d..
-
1295-C, *1600코드포스 2021. 11. 10. 16:22
Problem - C - Codeforces codeforces.com 문제 문자열 s, t 가 주어진다 s의 subsequence 를 몇 번을 더해야 t 와 같은 문자열이 될까? $O(|s|log\ |s|)$ s 의 각 알파벳별로 index 를 map loc 에 저장해놓는다 빨간색 포인터의 다음 위치는 loc[알파벳]에서 이진탐색을 이용하여 구한다 빨간색 포인터가 ind |s| 까지 가거나, 찾으려는 알파벳이 없으면 초기값 ps = -1 으로 갱신하고 cnt 값을 하나 증가킨다 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 4..
-
1295-B, *1700코드포스 2021. 11. 10. 15:57
Problem - B - Codeforces codeforces.com 문제 문자열 $s$가 주어질 때 무한길이 문자열 $sss...$을 생각하자 무한길이 문자열에서 $\mathrm{bal(i)}=x$인 $\mathrm{prefix(i)}$의 개수는? $\mathrm{prefix(i)}$는 i번째 문자까지를 포함한 문자열의 prefix 로 정의한다 $\mathrm{bal(i)}$는 $\mathrm{prefix(i)}$에서 (0 의 빈도수)-(1의 빈도수) 로 정의한다 $O(n)$ s의 주기성과 연관하여 bal(i)를 관찰하자 3 10 010 $$\mathrm{bal(i)}=\left \lfloor \frac{i}{n} \right \rfloor \mathrm{bal(n-1)}+\text{bal}(i\te..
-
1284-C, *1600코드포스 2021. 11. 3. 03:13
Problem - C - Codeforces codeforces.com 문제 수열 $\left \{ a \right \}=\left \{ a_{1}a_{2}...a_{n} \right \}$에 대해 [l, r] 은 부분수열 $\left \{ a_{l}a_{l+1}...a_{r} \right \}$을 의미한다 $\mathrm{max[l,\ r]-min[l,\ r]}=l-r$을 만족하는 [l, r]을 framed-segment 라고 한다 길이가 n 인 모든 n-permutation 에 대해 framed-segment 의 개수는? $O(n)$ 순열을 고정하여 framed-segment 를 구하지 말고 l, r 이 고정되어 있을 때 [l, r]이 framed-segment 가 되는 순열의 개수를 생각한다 [l,..
-
1284-B, *1400코드포스 2021. 11. 3. 02:51
Problem - B - Codeforces codeforces.com 문제 $n$개의 수열이 주어진다 $a_{i} < a_{j}$인 $1\leq i < j \leq n$인 순서쌍 (i, j)가 존재하면 수열이 ascent 라고 한다 임의의 두 수열을 합쳐서 ascent 인 수열이 되는 경우의 수는? $O(nlog\ n)$ ascent 인 수열에 임의의 순열을 더해도 ascent 이다 그러므로 먼저 n개의 수열을 ascent 인 것과 아닌 것으로 분류하자 수열 p, q에 대해 p+q 가 ascent 가 되는 경우를 고려하자. ascent 인 수열의 개수를 k 개라고 하면 i) ascent 를 포함한 수열의 합이 ascent 가 되는 경우의 수 가. p가 ascent, q가 non-ascent ~ k(n-..
-
1604-B, *1100코드포스 2021. 11. 1. 01:25
Problem - B - Codeforces codeforces.com 문제 순열 $a_{1}a_{2}...a_{n}$이 주어진다 순열을 subarray 로 분할했을 때 각각의 subarray 에서의 LIS(longest increasing subsequence)를 $h_{i}$라 하자 $h_{1}\oplus h_{2} \oplus ...\oplus h_{t} = 0$이 될 수 있게 순열을 분할할 수 있는가? $O(n)$ i) n = 1 일때 ~ NO ii) n 이 짝수일때 ~ YES 순열을 크기가 1인 subarray로 나누면 1^1^...^1 = 0 (∵1이 짝수개) iii) n 이 홀수일때 가. $a_{i+1}\leq a_{i}$인 항이 존재할 때 ~ YES 그 두 항을 묶어 하나의 subarray..