분류 전체보기
-
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..
-
1604-C, *1300코드포스 2021. 11. 1. 00:20
Problem - C - Codeforces codeforces.com 문제 순열 $a_{1} a_{2}...a_{n}$ 가 주어질 때 다음과 같은 시행을 통해 순열이 모두 지워질 수 있는가? $(i+1)\nmid a_{i}$인 항은 지울 수 있다. 이 때 지운 후에는 바뀐 index 에 대해 이 시행을 적용한다 풀이 다음을 관찰하자 중간에 있는 항을 지우면 앞 항들은 erasability(지울 수 있음)가 유지되고 뒤 항들은 변한다 따라서 뒤 항부터 보면서 지우는게 중간이나 앞에서부터 지우는것보다 지울 수 있는 항을 유지하는 더 좋은 선택이다 다음과 같은 greedy 방식으로 푼다 1. 뒤에서부터 지울 수 있는건 지운다 2. 지우다가 막히면 앞에꺼 중 가장 가까이 있는 지울 수 있는 index를 찾아 ..
-
1604-D, *1600코드포스 2021. 10. 31. 21:30
Problem - D - Codeforces codeforces.com 문제 두 양의 짝수 $x,\ y(2 \leq x,\ y \leq 10^{9})$가 주어진다 $n \text{ mod } x = y \text{ mod } n$을 만족하는 $n(1\leq n \leq 2\cdot 10^{18})$을 출력하라 $O(1)$ 제약이 더 많이 생기면 조건이 더 명확해지므로 x, y 의 크기로 경우를 나누어 풀었다 i) x = y 인 경우 n = x 이면 성립한다 ii) x > y 인 경우 잘 모르겠어서 작은 입력에 대한 결과를 출력해봤다 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 #include #define endl ..
-
ICPC, IUPC 후기아무거나적어~ 2021. 10. 8. 23:46
오늘부로 나의 ICPC, IUPC 가 끝이 났다. 이 글에서 대회의 준비부터 종료까지를 회고하며 생각을 정리해보고자 한다. 이 글이 같은 시행착오를 겪지 않는데 도움이 되길 바란다 IUPC 를 준비하며 ~ 잡담 우리팀, '인하원숭이' 는 사실 급조된 팀이다. 대회 접수 마감 직전, 알고리즘 동아리 CTP 에서 동아리원은 대회 참가를 원칙으로 한다는 사실을 전해들었다. 원래 동아리 내에서 '대회 준비반'으로 활동중이기는 하였으나, 올해는 군 전역후 전공공부로 정신이 없었기 때문에 대회준비기간 정도로 생각하고 있던터였다. 무엇보다 꼭 그렇게 해야겠다고 다짐한 이유는 첫째, 미분이 기억이 안나서였다. 그게 어떻게 이유가 되냐? 라고 물어보실 수 있겠지만 수학과로써, 수학이 정체성이라고 생각하는 사람으로서 충격..
-
10999, Platinum 4백준 2021. 10. 8. 01:13
10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 빈번하게 변하는 배열의 구간합을 구하시오(변할 때 하나의 값이 아닌 구간으로 변한다) $O((m+k)log\ n)$ lazy propagation in segment tree which constrctive recursive function lazy propagation 의 핵심 아이디어는 갱신을 미리하지 말고 모았다가 (변화량은 lazy 배열에 저장해놓는다) 필요할 때 한꺼번에 하는것이다. ..