코드는 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) -> ..

트리 / 그래프의 기본기인 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}) + \) (문자열 비교하는 시간) \(..

문제 링크 : http://boj.kr/14869 This section is intentionally left blank. Tag : Dynamic Programming, Sliding window, Deque, Pigeon hole principle(...) \(dp(i,j)\) : 학원 \(i\)에서 \(j\)번째 강좌를 들었을 때의 최소 비용. 즉 우리가 구하고자 하는 답. \(S(i,j)\) : 학원 \(i\)에서 강좌를 \(1\)부터 \(j\)까지 다 들을 때 드는 비용의 총합. 즉, 비용 배열의 부분합.\(B_i\) : 학원 \(i\)의 불허용 학원. 다음과 같은 dp 식이 성립한다. (엄밀히는 예외가 좀 있지만 뒤에서 처리하자)$$ dp(i,j) = \min_{\begin{cases} k\..

Lobelia, RickMcCoy 와 함께 연습한 대회다. (팀명 : Red Lung)나는 C를 잡았는데, 결과는 1 solve로 초라했지만 대회가 끝나고 1시간 가량 더 잡아서 풀어냈다.(애초에 QR을 치려고 했는데 내가 예약을 FR로 잘못한 걸 나중에서야 알았다...) \(n\)장의 서로 다른 카드에 숫자 \(a_1, a_2, \cdots a_n\)이 적혀 있다. (\(1 \le a_i \le 10^{9}\)) 이 카드들을 적당히 한 줄로 길게 이어붙여 만든 큰 숫자가 \(11\)의 배수가 되는 경우의 수를 \(119 \times 2^{23} + 1\)로 나눈 나머지를 구하여라. Tag : Combinatorics, Dynamic Programming, FFT, DP optimization with ..

http://codeforces.com/contest/908 Result : A, B, C(+3), D (4 / 8) Rating Change :1985 -> 2046 (+61, 343rd place) Editorial : This section is intentionally left blank. A. New Year and Counting Cards (04 : 52) Tag : Implementation A 답게 간단한 문제이다. 모든 홀수와 모음의 개수가 답이 된다. 대회에서는 문제 해석 + 코드 세팅하느라 시간을 많이 잡아먹었다. B. New Year and Buggy Bot (20 : 24) Tag : Brute - Force B 답게 간단하...지만 일단 그리드이기 때문에 코딩이 빡친다. 다양한..