분류 전체보기110 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. 2016 ACM ICPC Asia-Manila Regional 후기 12월 14일이 예비소집/등록이고 12월 15일이 본 대회였습니다. 12월 13일 오후에 공항에서 출발했습니다. 출국하는 날까지 기말고사와 텀 프로젝트를 하다가 와서 매우 피곤하였습니다. 마닐라 국제 공항에는 밤 10시 쯤에 도착했습니다. 숙소는 시험장인 Ateneo de Manila University에서 걸어서 5분 거리에 있는 Oracle Hotel & Residence 였습니다. 필리핀은 교통 체증이 매우 심해서 마닐라 국제공항에서 숙소까지의 거리는 차로 30분 거리 정도인데 실제로는 2시간 가까이 걸렸습니다. 마닐라 시 전체가 서울 도심과 같은 교통체증인데, 공항 근처는 특별히 더 심합니다. 기온은 20도 ~ 30도 사이였고, 조금 습하고 덥습니다. 자동차 매연 냄새가 정말 심합니다. 다음 날,.. 2016. 12. 16. BOJ 13551 원과 쿼리 문제 링크 : https://www.acmicpc.net/problem/13551풀이 : 점들이 분포하는 영역을 정사각형 블록들로 나누어 생각해 볼 수 있다. 질문으로 어떤 원이 주어졌을 때에 정사각형 블록과 원의 공통된 부분이 있다면, 해당 블록에 속한 점들이 일일이 원에 속하는 지 확인하는 방법을 시도해 볼 수 있다. 원과 정사각형 블록과의 관계는 다음과 같이 크게 3가지로 나뉜다. 1. 원 내부에 정사각형 전부가 들어가는 경우 : 정사각형의 꼭짓점들이 모두 원에 속하는 것과 동치2. 원 외부에 정사각형 전부가 위치한 경우 : 원의 중심이 정사각형 외부에 있고, 정사각형의 각 변과 원의 중심과의 최소 거리가 반지름보다 모두 큰 것과 동치3. 이 외의 경우 : 해당 블록에 속한 점들과 원의 관계를 살펴.. 2016. 11. 17. 이전 1 ··· 8 9 10 11 12 13 14 ··· 22 다음
