문제 링크 : 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 답게 간단하...지만 일단 그리드이기 때문에 코딩이 빡친다. 다양한..

https://www.codechef.com/LTIME54 1. Smart Strategy (SMRSTR) Tag : Implementation, Number Theory \(N\)개의 수 \(D_1 , \cdots , D_N \)이 있을 때, \(Q\)개의 정수 \(X_1 , \cdots , X_Q \)에 대해 다음 과정을 수행하는 프로그램 작성하여라. procedure f(X):for i = 1 .. N:X = floor ( X / D[i] )return X \(1 \le \text{TESTCASE} \le 1,000\)\(1 \le N \le 10^5, \ \sum N \le 3 \cdot 10^{5} \)\(1 \le Q \le 10^5, \ \sum Q \le 3 \cdot 10^{5} \)\(..

링크 두 번째 인생...코포. Solved : 4 / 5 Rank : 29 (Official)51 (Including Unofficial) Rating Change : 1738 -> 1895 (파들파들) A. QAQ (00 : 02) Tag : Implementation 어떤 문자열이 주어졌을 때 그 문자열의 'QAQ' subsequence 개수를 묻는 문제. Q가 나올 때마다 개수를 더해 주면서 A가 나오면 (지금까지 나온 Q 수) * (앞으로 나올 Q 수) 를 답에 더해 주면 된다. Complexity : \(O(n)\) B. Ralph and His Magic Field (00 : 34) Tag : Combinatorics, Number Theory 쉬운 수올 문제. 였으나... 알아보지 못하고 백..

문제 : http://codeforces.com/contest/854A. Fraction \(n \le 1000\)이기 때문에 다양한 풀이가 가능하다. 나는 생각을 최대한 안 하는 풀이인 Brute-force로 짰다. Complexity : \(O(n lg n)\) B. Maxim Buys an Apartment ㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷmin : 한 쪽에 아파트를 모두 몰아 놓았을 때이다. \(k=0 \vee k=n\)일 때 0, 아니면 1.max : 그리디하게 2,5,8,....번째 아파트를 inhabited로 설정해 주면 \(min(2k,n-k)\)이 최대가 됨을 쉽게 증명할 수 있는데, 코딩할 때 생각을 너무 안 해서 System Test에서 참교육을 당했다. 으아아아아아아아 Complexit..