PS 이야기

A. 새 집 (New Home) $N$개의 상점이 주어진다. $i$번째 상점은 위치 $x_i$에 지어지며, 종류는 $t_i$이고, $a_i$년 초에 생겨, $b_i$년 말에 없어진다. 상점의 종류는 $K$가지이다. $Q$개의 질문이 주어진다. $i$번째 질문은, $y_i$년 중순에 $l_i$위치에 집을 지을 경우, 상점 종류마다 제일 가까운 상점과의 거리를 구해 그 중 최대값을 요구한다. 예를 들어, $K=2$이고 어떤 특정 시점에 1번 종류 상점이 좌표 2, 5, 13에 있고, 2번 종류 상점이 좌표 6, 10, 15에 있다고 했을 때, 아래와 같은 그래프를 그릴 수 있다. 그래프에서 파란색 선은 1번 종류 상점에 대한 거리를 나타내고, 주황색 선은 2번 종류 상점에 대해 거리를 나타낸다. 이 순간 좌..

1. 방 배정하기 (room) 수용인원이 A, B, C인 세 종류의 방이 있다. 이 방들을 적절히 예약하여 정확히 N명의 사람이 묵을 수 있도록 하는 문제다. N이 최대 300으로 굉장히 작기 때문에 아래 DP 배열을 정의하고 값을 채우면 된다. D[i] = 정확히 i명의 사람이 묵을 수 있도록 예약할 수 있는가 (있으면 true, 없으면 false) 점화식은 다음과 같다: D[i] = D[i-A] OR D[i-B] OR D[i-C] #include using namespace std; int A, B, C, N; bool D[350]; int main() { cin >> A >> B >> C >> N; D[0] = 1; for (int i=0;i

1. 물통 (bucket) 크기가 A인 물통과 크기가 B인 물통이 있고, 처음에는 모든 물통이 비어있다. 아래 4가지 동작을 통해 크기가 A인 물통에는 P 만큼, 크기가 B인 물통에는 Q 만큼의 물을 담는 최소 동작 횟수를 구하는 문제다. 1) 크기가 A인 물통을 비우거나 가득 채운다. 2) 크기가 B인 물통을 비우거나 가득 채운다. 3) 크기가 A인 물통에 담긴 물을 크기가 B인 물통에 옮긴다. 이 때, 크기가 B인 물통이 가득 차면 옮기는 것을 멈춘다. 4) 크기가 B인 물통에 담긴 물을 크기가 B인 물통에 옮긴다. 이 때, 크기가 A인 물통이 가득 차면 옮기는 것을 멈춘다. 크기가 A인 물통에 a만큼의 물이, 크기가 B인 물통에 b만큼의 물이 담겨 있는 상태를 (a, b)라고 나타내자. 초기 상태나..

ICC $N$개의 정점으로 이루어진 그래프가 있다. 그래프의 초기 상태에는 간선이 하나만 존재한다. 두 정점 집합 사이에 간선이 있는지 묻는 질문을 통해 간선이 무엇인지 알아낸다. 알아낸 이후에 새로운 간선이 또 추가된다. 항상 싸이클이 생기지 않도록 간선이 주어지며, 이 작업을 총 $N-1$번 수행하고 질문을 가능한 적게해야하는 문제다. 처음 상황, 즉, $N$개의 정점이 있고 그들 사이에 간선이 하나만 있는 상황에서 생각해보자. 우선 간선을 가지고 있는 임의의 두 정점 집합을 최대한 적은 질문안에 찾아야한다. 이는 최대 $\lceil\lg N\rceil - 1$번 질문만에 찾을 수 있다. 바로 각 정점 번호를 0번부터 N-1번까지 나타낼 때, 각 비트에 대해 비트값이 0인 집합과 비트값이 1인 집합 ..

문제: HackerRank 이 문제는 초기 배열 [1, 2, 3, ..., n]에서 구간을 flip 하는 연산과 i번째 위치에 있는 수를 구하는 연산, 수 i의 위치를 구하는 연산에 대해 처리 빠르게 처리해야되는 문제다. Balanced Binary Search Tree라는 것이 있다. 잘 알려진 것으로는 AVL tree, Red-black tree 등등이 있다. 이러한 자료구조로 구현 된 것으로는 STL container의 set과 map이 있다. STL의 응용으로 Balanced BST를 이용해야 풀 수 있는 문제는 거의 존재하지 않는데, 이 문제는 Balanced BST 중 Splay tree라는 자료구조를 이용하면 쉽게 풀린다. Splay tree에 대한 자세한 설명은 여기를 참고한다. 간단히 소..

문제: HackerRank or hongjun7's blog 이 문제는 $N$개의 정점과 그들 사이를 잇는 $M$개의 간선이 있는 무방향성 그래프에서 $K$번째 간선 상에 임의의 점 $P$를 잡아 $P$에서 각 정점으로 가는 최단 거리들 중 최대를 최소화 시키는 문제다. 우선 직관적으로 답의 소수점은 x.0 혹은 x.5 꼴임을 알 수 있다. 실수 연산을 피하기 위해 각 간선의 길이에 2를 곱해서 처리한다. 답(최단 거리들 중 최대 값)을 정하여, 가능한지 불가능한지 결정 문제로 바꾸어 이분 검색(혹은 Parametric search)를 통해 해결한다. 답을 $d$라 정했다고 가정하고, 각 지점으로 가는 최단 거리가 $d$ 이하가 될 수 있도록 점 $P$를 잡을 수 있는지 결정하는 방법을 설명하겠다. 문제..

해법: http://ace.delos.com/TESTDATA/FEB11.lostcows.htm 이 문제에서 현재 소가 k개의 목장에 위치해있다고 하자. FJ의 다음 sign 명령에 의해 이동 한 뒤에는 k개 이하의 목장에 위치해있다. * 예제 데이터에서 소가 처음에 1,2,3,4목장 (4개 목장)에 위치해있고 Sign 1의 명령을 받으면 소가 1,3,4목장 (3개 목장)에 위치하게 된다. 이는 쉽게 증명 가능하다. 그러면 우리는 항상 특정한 sign 명령 순열을 통해 목장 a에 있고, 목장 b에 있는 소를 목장 1(최종 도착지)에 모이게 할 수 있다. (답은 항상 존재한다고 했으므로) 이 특정한 sign 명령 순열은 bfs를 통해 계산할 수 있다. 방법은 소스 참고.

문제: http://z-trening.com/tasks.php?show_task=5000000691 해법: http://ace.delos.com/TESTDATA/NOV08.toy.htm * 이 문제 20번 데이터 출력 파일이 잘못 되었습니다. 올바른 답은 106110559이 아닌, 105265954 입니다. 해법 페이지에 있는 소스코드로 20번 입력데이터를 돌려보면 알 수 있습니다. 우선, N1 > N2, C1 < C2로 가정하자. 만약 아니라면 소독 회사가 하나만 있다고 볼 수 있기 때문이다. 미리 장난감을 총 t개 산다고 정하자. 그러면 이제 장난감을 총 t개 산다고 할 때, 소독하는데 최소 비용을 구해야한다. 문제에서는 장난감을 사용한 뒤, 장난감을 소독 회사에 맡긴다고 되어있는데, 우리는 미래의 ..

문제: http://z-trening.com/tasks.php?show_task=5000000140 우선 한 점 p에 대해서 d(p) 값을 구하는 과정에 대해서 알아보자. 문제에서 max(|Ax-Bx|,|Ay-By|) 부분 때문에 점 a에 다음과 같이 두 대각선을 귿고 4개의 사분면으로 나누었다. 우선 점 p(빨간점)을 원점으로 보도록 대칭이동 시키자. '+y' 라고 쓴 사분면 안에 있는 점 q에 대해서 답에 qy 가 더해짐을 의미하고 '-x' 라고 쓴 사분면 안에 있는 점 r에 대해서 답에 -rx 가 더해짐을 의미한다. '-y', '+x' 도 마찬가지이다. 그러면 각 사분면에 대해서 +y, +x, -y, -x 의 값만 더하려면 어떻게 해야하나? 영역 a는 '-x', '+y' 사분면을 영역 b는 '+y'..

문제: http://www.csc.kth.se/contest/boi/monument.pdf 해법: http://www.csc.kth.se/contest/boi/monument-spoiler.pdf 재미있는 문제다.. BOI 문제들 다 재미있는 듯... 만만한 문제 하나 없다.. O(N^5) 부터 O(N^3) 까지 다양한 방법이 있지만, O(N^3) 만에 해결해야한다 ^^... 그 방법을 소개하겠다. Dynamic Programming 을 통해 각 점 (x,y,z)마다 xy 평면에서 점 (x,y,z)를 오른쪽-가장자리로 하는 정사각형의 최대 크기를 precompute(선처리) 해놓을 수 있다. 그 값을 D[x][y][z]라 하자. 그러면 이제 (x,y)의 z축에서 값들을 관찰할거다. (x,y)를 정하고 한..