PS 이야기

인접한 도시 사이를 이동하는데 걸리는 시간 1, 한 도시에 있는 관광지를 모두 둘러보는 시간 1이 걸리고 시작점이 주어졌을 때, 가장 관광지를 많이 방문하는 문제다. 물론 같은 관광지를 여러 번 방문해서는 안된다. 답이 될 수 있는 이동 경로는 아래 두 가지 중 하나이다. 1) 시작점에서 왼쪽으로 0칸 이상 가다가 어느 순간 오른쪽으로 이동하여, 시작점 보다 오른쪽으로 간다. 2) 시작점에서 오른쪽으로 0칸 이상 가다가 어느 순간 왼쪽으로 이동하여, 시작점 보다 왼쪽으로 간다. 즉, 쉽게 말하자면 방향을 한 번만 바꾼다는 것이다. 두 번 이상 방향을 바꾸어 왔다갔다 하는 것은 이동하는 시간만 늘리므로 항상 안좋다는 것을 알 수 있다. 2번 경우는 전체를 좌우로 뒤집었을 때 1번 경우와 같아지므로, 1번 ..

이 문제에서 독특한 성질의 그래프가 주어진다. 답으로 어떤 노드 집합을 구해야하는데, 이 노드 집합에 있는 각 노드는 서로 연결되어 있지 않으며, 각 노드별로 주어진 특성값의 합이 최대가 되어야한다. 아직 이 문제의 정해를 찾지 못 했다. 우선 69점 받는 방법을 설명하겠다. 부분 문제1) 노드가 많아야 10개이므로 각 노드에 대해서 집합에 포함되는지 포함되지 않는지 구하는 경우의 수는 노드의 개수가 $n$개라 할 때, $2^n$개이다. $2^n$가지에 대해 모두 가능한 집합인지 확인하고, 최대값을 갱신하면 된다. 부분 문제2) 입력으로 주어지는 그래프에 간선이 존재하지 않는다. 따라서, 모든 노드의 값을 더해주면 된다. 부분 문제3) 입력으로 주어지는 그래프는 완전그래프다. 따라서, 노드의 값들 중 최..

이 문제는 여러 개의 부분 문제(서브태스크)가 하나의 문제를 이루어, 이 문제를 해결하기 위해서 3개의 코드를 짜야한다. 문제의 난이도는 매우 쉬운 편이며, 3개의 방법에 대해서 꼼꼼히 생각해야 되기 때문에 귀찮은 문제라고 생각한다. 1) 곤돌라 수열 확인 우선 곤돌라 수열에서 같은 수가 여러 개 있는 경우 이는 자명히 불가능한 곤돌라 수열이다. 그렇지 않은 경우, 주어진 곤돌라 수열에 있는 1 이상 $n$ 이하의 수에 신경써야한다. 곤돌라 수열에 1 이상 $n$ 이하의 수가 없다면, 이는 항상 가능한 곤돌라 수열이다. 만약 1 이상 $n$ 이하의 수가 하나라도 있다면, 초기 1의 위치를 짐작할 수 있으며, 다른 1 이상 $n$ 이하의 수가 그 1의 위치에 대해 상대적으로 올바른 위치에 있는지 확인하면 ..

오늘 오후 3시 IOI 2014 Contest Day 2가 끝나 모든 학생의 성적이 정해졌다. 대회 중간까지 우리나라 금메달이 한 명일 것 처럼 보였으나, 경기과고 2년 윤지학 군이 끝나기 30분 전에 holiday 문제를 해결하여 금메달 권에 들어왔다. 윤지학 군의 Day 2 성적은 6등으로 굉장히 우수했다. 이번 대회 총 6문제를 종합하여 보면 푼 사람 수를 기준으로 난이도를 따지면 gondola > wall > game > rail > friend > holiday 순이 된다. 개인적으로 wall 보다 game이 쉽다고 생각하며, friend 보다 holiday가 풀만하다고 생각된다. 예년과 다르게 채점 데이터 공개도 늦어지고, 온라인 저지도 없고, 문제 set (grader 등)도 공개가 안되어 ..

우선, 이 문제에 대해 본격적으로 설명하기에 앞서 이 문제에서 특성을 몇 가지 설명하겠다. $d(i,j)$를 정류장 $i$와 정류장 $j$ 사이의 거리라고 할 때, $d(i,j) = d(j,i)$ 이다.맨 왼쪽 정류장은 C type 이다.맨 오른쪽 정류장은 D type 이다. $i > 0$인 $i$에 대하여 $d(0,i)$ 를 모두 구한다. 이 때 $d(0,i)$가 최소가 되는 $i$를 $x$라 하자. 이 때 정류장 $x$는 정류장 $0$ 보다 오른쪽에 있으면서 가장 가까운 D type 정류장이다. 만약 $d(0,i) = d(0,x)+d(x,i)$ 라면 정류장 $i$는 정류장 $x$ 보다 왼쪽에 있다. 이 문제를 해결하기 위해, 정류장 $x$를 기준으로 왼쪽에 있는 것과 오른쪽에 있는 것들을 나눠 따로 ..

여러 가지 다양한 해법이 있다고 생각한다. $0$번 도시 부터 $N-1$번 도시까지 총 $N$개의 도시가 있다. 이 $N$개의 도시들을 단말 노드로 갖는 이진 트리를 만든다. 이 이진트리의 단말 노드의 개수는 정확히 $N$개이다. 이제 모든 $(i,j)$ 쌍 ($0 \leq i < j \leq N-1$)에 대하여 단말 노드 $i$와 단말 노드 $j$의 LCA(Lowest Common Ancestor, 최저 공통 조상)를 $k$라 했을 때, left[k]에 1을 더한다. 쿼리(질문)가 $(u,v)$으로 주어졌을 때, 단말 노드 $u$와 단말 노드 $v$의 LCA를 $w$라 했을 때, left[w] 값을 1 감소 시키고, 그 값이 0 이면, 값을 1 반환하고 감소한 뒤 그 값이 여전히 0 보다 크다면 0을 ..

Segment Tree를 이용하여 해결하는 문제다. Segment Tree의 각 노드별로 구간 내에서 최소값과 최대값을 가지고 있는다. add 연산은 lower boundary(최소값)을 변화시키고, remove 연산은 upper boundary(최대값)을 변화시킨다. Segment Tree를 순회할 때 자신(현재 탐색 중인 노드)의 조상에 대한 값을 자신한테 반영할 수 있도록 신경쓴다. 각 노드의 값 갱신에 대해 자세한 설명은 생략한다. 첨부된 소스를 참고하길 바란다. $K$개의 쿼리마다 계산하는 시간복잡도는 $O(lg N)$이며, 최종적으로 각 위치에 대한 높이를 계산하는 시간복잡도는 $O(N)$이다. 그러므로 총 문제를 해결하는 시간복잡도는 $O(K lg N + N)$이다. #include #inc..

지금 IOI2014 대회가 한창 진행 중이다. Contest Day 1은 어제 진행 되었으며, Contest Day 2는 내일 진행된다. 개최국은 대만이며, 우리나라와 시차가 1시간 밖에 안된다. 시험은 내일 우리나라 시간으로 아침 10시부터 오후 3시까지 5시간 동안 진행된다. 문제는 아직 공식적으로 공개된바 없으며, 구글링을 해본 결과 http://math.mit.edu/~rpeng/IOI2014/ 에서 영문판, 중국어판 문제를 볼 수 있다. Live Scoreboard는 http://live.ioi2014.org/Ranking.html 에서 볼 수 있다. 한국 대표 최석환, 조승현, 윤지학, 이창수 군 모두 좋은 성적 받고 기쁜 마음으로 귀국할 수 있길 바란다. Day 1 문제 셋은 3개의 문제로 ..