PS 이야기

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://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)를 정하고 한..

문제: http://www.csc.kth.se/contest/boi/subway.pdf 해법: http://www.csc.kth.se/contest/boi/subway-spoiler.pdf 이 문제에 대한 증명을 하지는 못 하겠다... 그냥 느낌으로 올 뿐이지 증명이 가능한지는... 잘 모르겠다... ㅠㅠ 예제 2번 데이터를 통하여, 방법을 설명하겠다. 1. 우선 처음에 입력 받을 때 방향에 상관없이 입력받고, 오름차순 정렬을 한다. 9 15 33 33 41 81 97 100 2. 홀수번째와 짝수번째의 방향을 다르게 한다. 9R 15L 33R 33L 41R 81L 97R 100L 3. 다음에 subway의 rail을 일직선에 나타내고 그에 따라 x좌표를 대입한뒤 정렬하면, 9 (200-15) 33 (20..

문제: http://www.csc.kth.se/contest/boi/candy.pdf 해법: http://www.csc.kth.se/contest/boi/candy-spoiler.pdf 현재 로봇이 사탕 A(p1,t1) 에서 사탕 B(p2,t2) 로 가는 경우를 고려해보자. (t1 p2) (i) p1