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

5485. 평균값 수열 (IOI '05) http://icpc.me/5485 이 문제에서 가장 중요한 아이디어는 s1s_1s1​과 m1⋯mn−1m_1 \cdots m_{n-1}m1​⋯mn−1​만으로 s2⋯sns_2 \cdots s_ns2​⋯sn​을 결정할 수 있다는 것이고, 따라서 가능한 수열의 개수는 가능한 s1s_1s1​의 개수와 같다는 것이다.수열의 단조 증가 조건으로부터,s2=2m1−s1≥s1⇒s1≤m1s_2 = 2m_1 - s_1 \ge s_1 \Rightarrow s_1 \le m_1s2​=2m1​−s1​≥s1​⇒s1​≤m1​s3=2m2−s2≥s2⇒s1≥2m1−m2s_3 = 2m_2 - s_2 \ge s_2 \Rightarrow s_1 \ge 2m_1 - m_2s3​=2m2​−s2​≥s2​⇒s1​≥2m1​−m2​s1≤2m1−2m2+m3s_1 \le 2m_1 - 2m_2 + m_3s1​≤2m1​−2m2​+m3​⋮\vdots⋮와 같이 s1s_1s1​에 관한 총 n−1n-1n−1개의 부등식을 얻을 수 있고, 이를 통해 s1s_1s1​의..

2820. 자동차 공장 문제 : http://icpc.me/2820 세그먼트 트리의 클래식한 활용 문제. 사실 suhgyuho가 준 문제집에 있던 건데 이제서야 풀었다(...) 이 문제의 아이디어는 트리를 Segment Tree나 Fenwick Tree같은 구간 자료구조와 엮을 때 자주 쓰는 트릭 중 하나인데, 어떤 노드 vvv의 서브트리 (vvv 포함) 를 DFS-numbering에서 붙은 번호 [d[v],f[v]][d[v], f[v]][d[v],f[v]]의 구간으로 처리하는 것이다. 이 트릭을 적용하고 나면 문제의 쿼리는 이렇게 바뀐다 : p 쿼리 : 구간 (d[a],f[a])(d[a],f[a])(d[a],f[a])의 원소에 xxx를 더한다. (range update)u 쿼리 : 구간의 d[a]d[a]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)O(Tn)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(n4)O(n^4)O(n4)이랑 O(n3)O(n^3)O(n3) 생각하고 끝냈던 문제. 일단 dp[i][j]dp[i][j]dp[i][j]를 (i,j)(i,j)(i,j)에서의 최장 경로라고 하자. 이제 각각 nnn개씩의 행/열에 대해서 dpdpdp값과 좌표를 저장해두는 자료구조를 만든다. 높이가 낮아지는 순서대로 탐색하면서, i+1열, i-1열, j-1열, j+1열에 저장된 dp값들 중 조건을 만족하면서 가장 큰 dp값을 DDD라고 하면, dp[i][j]=D+1dp[i][j]=D+1dp[i][j]=D+1이 된다. 자료구조를 맨 처음에는 set으로 했는데, set을 허투루 썼더니 메모리 초과가 났다(...) 여윽시 s..

어제 올리려고 하다가 9시에 자버렸다 ㅁㄴㅇㄹ... 이번에는 MWT 특집.2011. 암호코드문제 : icpc.me/2011 간단한 dp인데, 0인 경우를 생각해주지 않으면 가버릴 수 있다. 입력 문자열을 SSS라고 하고, D[i]D[i]D[i]를 S1⋯Si−1S_1 \cdots S_{i-1} S1​⋯Si−1​를 해석할 수 있는 경우의 수라고 두자. 입력이 0으로 시작하지 않는다는 것이 보장되어 있으므로 D[2]=1D[2]=1D[2]=1이다. 이제 dp를 앞에서 뒤로 뿌려주자.Si≠0S_i \neq 0Si​=0인 경우, SiS_iSi​를 하나의 암호문으로 해석할 수 있으므로 D[i+1]+=D[i]D[i+1]+=D[i]D[i+1]+=D[i].Si≠0∧10Si+Si+1<27S_i \neq 0 \wedge 10S_i + S_{i+1} < 27Si​=0∧10Si​+Si+1​<27인 경우, SiSi+1S_iS_{i+1}Si​Si+1​를 하나의 암호문으로 해석할 수 있으므로 ..