robustflame의 블로그

문제 보기출제자 해설문제 요약\(n\)개의 item 목록이 주어지는데, 각 item은 다음과 같은 값들을 가진다.\(t_i\): \(i\)번째 item을 구하는데 소요되는 시간\(d_i\): \(i\)번째 item의 가치가 유효한 시간, 즉 가치를 지켜내기 위해 구해내야만 하는 시간\(p_i\): \(i\)번째 item의 가치item들을 어떤 순서로 어떤 것들을 구하는지에 따라 얻을 수 있는 가치의 총합이 달라진다. 이때 가능한 가장 큰 가치의 합을 구하는 문제다.문제 풀이가장 단순한 방법은 가능한 모든 경우를 따져보는 것이다. 모든 경우를 다 따져볼 경우 각각의 item을 구할지 말지를 정해야 하고, 해당 item들을 어떤 순서로 구해야 하는지 따져봐야 하므로 시간복잡도는 \(O(2^n \times n..

문제링크 - http://codeforces.com/problemset/problem/785/E문제 풀이순열 \(a[ \ ] = \{1, 2, ..., n\} \ (1 \le n \le 200000)\) 에 대하여 특정 위치 \(l_i\) 과 \(r_i\) 의 값을 바꾸는 연산이 \(q \ (1 \le q \le 50000)\) 번 수행될 때, 매 연산 후 순열에 존재하는 역접(inversion)의 수를 세는 문제다. 역접의 수는 크기가 \(a[x] > a[y] \ (x a[r]\) 이면 역접의 수가 1 감소한다. 위의 내용들에서 서로 상쇄되는 것들을 제거하고, 통합하면 아래와 같이 간결하게 역접의 수 변화를 확인할 수 있다. \(a[l] < a[r]\) 이면, \((l 0) { ret += tree[p..

Square Root Decomposition 우리 말로는 평방 분할(Sqrt Decomposition)이라고 불리는 이 기술은 특정 구간에 대한 질문(query)에 빠르게 답하기 위한 최적화 기술(일종의 자료구조)이다. 먼저, 아래와 같은 문제에 대해 고민해보자. 원소의 개수가 \(n\) 개인 배열 arr[]이 있다. 이 배열에 대해서 \(q\) 개의 질문(query)이 하나씩 들어온다. 질문의 내용은 다음 2가지 중 하나이다.특정 구간 [\(l, \ r\)] 의 합을 구하라.특정 위치 \(idx\) 의 값을 \(val\) 로 변경하라. 위와 같은 문제는 단순하게 반복문을 이용하여 \(l\) 부터 \(r\) 까지 순회하면서 값을 더해나가면 구할 수 있다(시간복잡도: \(O(q \times n)\)). ..

Modular Arithmetic 정수 \(a, b, m\)에 대하여, \(m \ | \ (a-b)\) 일때, \(a\)는 법 \(m\)에 대하여 \(b\)와 합동이다(\(a\) is congruent to \(b\) modulo \(m\)). 이때, 기호로 \(a\equiv b\pmod m\)이라고 쓴다. 여기서 \(m\)을 합동의 법(modular)이라고 한다. 수학적인 정의는 이렇고, 간단하게 말하면 '\(a\)와 \(b\)를 \(m\)으로 나누었을 때, 그 둘의 나머지가 같다'라고 생각하면 된다. 모듈라 연산에서의 덧셈, 뺄셈, 곱셈은 다음과 같은 성질들이 성립한다. \((a+b) \pmod m \equiv ((a \pmod m) + (b \pmod m)) \pmod m\) \((a-b) \pmo..