PS 이야기

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

문제: http://www.ioi2013.org/wp-content/uploads/tasks/day2/robots/robots - KOR (ko).pdf이분검색으로 미리 답을 정해놓은 뒤 그리디를 통해 답이 되는지 확인하는 방법을 사용한다. 이런 테크닉은 파라매트릭 서치(Parametric Search)로 알려져 있다.만약 로봇의 종류가 한 가지라면 매우 쉽게 풀릴 것이다. 하지만, 로봇의 종류가 2 종류 (연약한 로봇, 작은 로봇)이라 생각하기 많이 까다로울 수 있다.답을 $m$ 이라 가정했다는 것은 각 로봇은 최대 $m$ 개의 장난감을 운반할 수 있다는 것이다. 먼저 연약한 로봇들이 연약한 순서대로 자신이 가져갈 수 있는 가장 '크기'가 큰 장난감들을 $m$개 운반한다. 만약 가져갈 수 있는 장난감이..

문제: 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개 산다고 할 때, 소독하는데 최소 비용을 구해야한다. 문제에서는 장난감을 사용한 뒤, 장난감을 소독 회사에 맡긴다고 되어있는데, 우리는 미래의 ..