Problem Solving102 APIO 2014 SEQUENCE 문제 링크 2017. 1. 19. Rope 튜토리얼 문서 원본 Rope는 scalable string implementation이다: 문자열에 대한 연산들 중 몇 개에 대해서 강력한 성능을 제공한다. 할당(assignment), 연결(concatenation), 그리고 부분문자열(substring)에 해당하는 연산들은 문자열의 길이와 거의 독립적으로 빠르게 수행된다. Rope는 문자들의 Container로 취급되며, 거의 Sequence이다. 각각의 원소를 수정하는 연산은 느리다. vector 또는 string과 비교해 장점과 단점을 비교해보자.장점: 1. Much faster concatenation and substring operations involving long strings. 2. Potentially much better space.. 2017. 1. 19. IOI 2005 Rivers Problem Link주어지는 마을의 관계가 트리 구조임을 알 수 있다.0번 노드가 루트인 트리가 구성되는데, 이 트리에서 0번 노드를 제외하고 추가적으로 K개의 목공소를 지어야한다.단, 목공소를 적절히 배치하여 통나무를 운반하는 비용의 합을 최소화하여야 한다.동적계획법으로 접근을 해보자.부분 문제를 정의하고 그 부분 문제에 영향을 미치는 parameter를 고민해보자.임의의 노드 X이 루트인 부트리에서 K개의 목공소를 배치하는 걸 생각해 볼 수 있겠다.그런데 여기서 끝나면, 그 부트리에서 최종적으로 상위 조상 중에 어느 목공소로 운반해야하는지 알 수가 없다.그래서 다음과 같은 3차원 동적계획법 테이블을 정의할 수 있다.D(L , X , K) : 루트가 X인 부트리에서 K개의 목공소를 배치할 때, 노드 .. 2017. 1. 2. Codeforces Beta Round #87 (Div. 1 Only) A. Party Simple DFS B. Lawnmower Simple DP인데, 문제에서 구하고자 하는 걸 잘 체크해야하고, 업데이트할 때 조건 잘 확인하지 않으면 틀리기 쉬움. C. Plumber 가로와 세로를 독립적으로 생각하는 것까진 좋았는데, 석환이가 준 2^k 힌트는 생각해내지 못했음. 시간이 지나고 꼭 다시 풀어봐야 함. 2016. 12. 23. Codeforces Round #268 (Div. 1) A. 24 Game n 5일 때에 1) 홀수 : n = 5에서 끝의 (n)-(n-1)=1이고, 이걸 매번 24에 곱해주면 된다. 2) 짝수 : n = 4에서 끝의 (n)-(n-1)=1이고, 이걸 매번 24에 곱해주면 된다.B. Two Sets 2-SAT으로 해결할 수 있다. 각 원소에 대해서 A집합에 속할 때, B집합에 속할 때 서로 충돌되는 애들 사이에 간선을 준다. A 집합에만 속해야하는 경우, B 집합에만 속해야하는 경우에 대해서도 간선을 준다. SCC로 확인하고 해를 출력하면 된다.C. Hack it! g(x) : 1~x까지의 모든 f값들의.. 2016. 12. 23. 이전 1 ··· 7 8 9 10 11 12 13 ··· 21 다음
