문제 : http://oj.uz/problem/view/IOI16_molecules바로 100점 풀이.바로 100점으로 넘어가는 이유는 rkm0959의 풀이를 컨닝했기 때문. 일단 주어진 배열의 값들을 정렬한 값의 인덱스를 \(i_1, i_2, \cdots , i_n\)으로 정의한다. 이제 수학이다. \(Pro(k)\)를 다음과 같은 알고리즘으로 정의하자:\(P(k) := w_{i_1} + \cdots + w_{i_k}, \ S(k) := w_{i_n} + \cdots w_{i_{n-k+1}} \) case 1) \(P(k) > u \) : terminate (답이 없다) case 2) \(P(k) or S(k) \in [l,u] \) : terminate (둘 중 [l,u]에 들어 있는 놈이 답이다) ..

그 동안 쉬운 문제만 푸느라 문제 정리를 올리고 싶은 의욕이 없었다. 앞으로는 그냥 의식의 흐름대로 풀리는 문제는 적당히 필터링하겠다. 1052. 물병http://icpc.me/1052 일단 물병을 무한정으로 사올 수 있기 때문에, 항상 답을 찾을 수 있다. 그냥 입력의 \(N\)보다 큰 최소의 \(2^p\)꼴의 숫자를 찾으면 물병을 1개로 만들 수 있기 때문에, 답은 항상 \(2N\)보다 작다는 것도 알 수 있다.그런데 그대로 내면 당연히 4%대에서 틀리게 된다. 아이디어를 조금만 발전시키자. \(X\)개의 물병을 압축할 수 있는 최소 개수는 \(X\)를 이진수로 나타냈을 때 각 자리수의 합, 즉 \(s_2 (X)\)가 됨을 알 수 있다. 즉 물병을 더해 가면서 \(s_2 (X) \le K\)가 성립하..

5485. 평균값 수열 (IOI '05) http://icpc.me/5485 이 문제에서 가장 중요한 아이디어는 \(s_1\)과 \(m_1 \cdots m_{n-1}\)만으로 \(s_2 \cdots s_n\)을 결정할 수 있다는 것이고, 따라서 가능한 수열의 개수는 가능한 \(s_1\)의 개수와 같다는 것이다.수열의 단조 증가 조건으로부터,\(s_2 = 2m_1 - s_1 \ge s_1 \Rightarrow s_1 \le m_1\)\(s_3 = 2m_2 - s_2 \ge s_2 \Rightarrow s_1 \ge 2m_1 - m_2\)\(s_1 \le 2m_1 - 2m_2 + m_3\)\(\vdots\)와 같이 \(s_1\)에 관한 총 \(n-1\)개의 부등식을 얻을 수 있고, 이를 통해 \(s_1\)의..

2820. 자동차 공장 문제 : http://icpc.me/2820 세그먼트 트리의 클래식한 활용 문제. 사실 suhgyuho가 준 문제집에 있던 건데 이제서야 풀었다(...) 이 문제의 아이디어는 트리를 Segment Tree나 Fenwick Tree같은 구간 자료구조와 엮을 때 자주 쓰는 트릭 중 하나인데, 어떤 노드 \(v\)의 서브트리 (\(v\) 포함) 를 DFS-numbering에서 붙은 번호 \([d[v], f[v]]\)의 구간으로 처리하는 것이다. 이 트릭을 적용하고 나면 문제의 쿼리는 이렇게 바뀐다 : p 쿼리 : 구간 \((d[a],f[a])\)의 원소에 \(x\)를 더한다. (range update)u 쿼리 : 구간의 \(d[a]\)번째 원소의 값을 구한다. (point query) ..

3584. 가장 가까운 공통 조상 문제 : http://icpc.me/3584 옛날 ICPC문제여서 그런지 진짜 LCA를 대놓고 묻는 문제. 이 때는 아직 LCA가 고ㅡ급 알고리즘이었나보다. 테스트 케이스마다 배열 초기화에 주의하도록 하자. LCA에 대해서는 더 잘 설명해놓은 글들이 천지빽가리.http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220820773477 Time Complexity : \(O(Tn)\) 8984. 막대기 (KOI '13)문제 : http://icpc.me/8984http://oj.uz/problem/view/KOI13_game BOJ AC 기준으로 게시.문제 조건을 잘못 이해해서 이거 완전 NP 아니냐? 하고 풀이를 깠다. 이해..

2969. 메뚜기 (COCI 08/09 Contest #1 5번) 문제 : http://icpc.me/2969 오래전에 친구가 교내 대회에 냈던 문제인데, 그때 아무생각없이 \(O(n^4)\)이랑 \(O(n^3)\) 생각하고 끝냈던 문제. 일단 \(dp[i][j]\)를 \((i,j)\)에서의 최장 경로라고 하자. 이제 각각 \(n\)개씩의 행/열에 대해서 \(dp\)값과 좌표를 저장해두는 자료구조를 만든다. 높이가 낮아지는 순서대로 탐색하면서, i+1열, i-1열, j-1열, j+1열에 저장된 dp값들 중 조건을 만족하면서 가장 큰 dp값을 \(D\)라고 하면, \(dp[i][j]=D+1\)이 된다. 자료구조를 맨 처음에는 set으로 했는데, set을 허투루 썼더니 메모리 초과가 났다(...) 여윽시 s..