코드는 Team github에서 압축파일로 받을 수 있습니다.압축 해제 비밀번호는 imeimi2000입니다. A. 소가 길을 건너간 이유 5 b[i]를 i번 신호등이 망가졌는가? 를 묻는 boolean 변수,S[i]를 ([i-K+1, i]의 신호등 중 망가진 것의 개수) = (b[i-K+1] + ... + b[i]) 라고 하면,문제는 min(S[K-1], ... , S[N-1]) 을 구하는 문제로 바뀝니다. S[i+1] = S[i] + b[i] - b[i-K]임을 이용하면 O(N)만에 문제를 해결할 수 있습니다. B. Binary Roads BFS를 정직하게 개조하면 해결할 수 있는 문제입니다. 정점 v를 (v,0)과 (v,1)의 독립된 2개의 정점으로 보고, 에지 u-v의 값이 0이면 (u,0) -> ..

Definition.\(\phi(n)\) : Number of natural numbers in \(1..n\), which are relatively prime to \(n\).\(\sigma(n)\) : Sum of divisors of \(n\), including \(1\) and \(n\) itself.claim.$$n > 1 \Rightarrow \phi(n) > \frac{n}{4\log n}$$This section is intentionally left blank. Special thanks: H. Cho, W. Song. Solution 1. (Official) \(n := p_{1}^{e_1} p_{2}^{e_2} \cdots p_{k}^{e_k}\). $$ \phi(n) = n \p..

트리 / 그래프의 기본기인 DFS technique를 연습하려고 한다.너무 쉬운 건 말고, Div.1 A ~ B 부터 짬짬이 풀어야지. 링크 396C. On Changing Tree 코드 트리에 기본적으로 DFS numbering을 해주자.잘 모르겠다면 코드, 또는 다음 설명을 참조. 노드 \(v\)가 발견되는 시점을 \(dt[v]\), 노드 \(v\)의 탐색이 끝나는 시점을 \(ft[v]\), 노드 \(v\)의 깊이를 \(dep[v]\)라고 한다.합 세그먼트 트리를 2개 관리한다. 각각 \(X, K\)라고 하자. type 1 쿼리 \((v,x,k)\) :\(X\)의 \([dt[v], ft[v]]\)에 \(x + k \cdot dep[v]\)를 더해줌.\(K\)의 \([dt[v], ft[v]]\)에 \(..

말그대로 여기서 태그에 DnC가 붙어 있는 놈들을 풀어보려는 시도입니다. 백준에서 좋은 DnC 찾기가 너무 힘들어서... 559B. Equivalent Strings 559B 문제가 말하는 "동치 관계"가 정말로 equivalent relation의 조건을 만족시킨다는 것이 관찰 포인트이다.그렇다면 한 string \(S\)의 대표원 \(r_{S}\)를 정해줄 수 있고, 편의상 사전 순으로 가장 빠른 string으로 정해주면 된다. 어떤 길이가 짝수인 string \(S = A + B\)에 대해서 \(r_{S} = \text{min}(r_{A} + r_{B}, r_{B} + r_{A})\)로 정해질 것이므로, 시간복잡도는 \(T(n) = 2T(\frac{n}{2}) + \) (문자열 비교하는 시간) \(..

Gamma Function은 여러 가지 정의가 있는데, 그 중 몇 가지 정의들은 서로 동치임이 자명하지만은 않다.여기서는 가장 대표적인 동시에 가장 대립되는 두 가지 정의를 다룬다.

여름방학 때부터 3단원을 정리하려고 했지만 너무 귀찮아서 패스.4단원은 \(\pi (x)\)를 신나게 갖고 노는 1부와, 소수 역수의 합을 가지고 노는 2부로 나뉘어서 업로드됩니다.