PS 이야기

문제: 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$를 잡을 수 있는지 결정하는 방법을 설명하겠다. 문제..

포함-배제의 원리(Inclusion-Exclusion Principle)란 유한 집합들의 합집합의 크기를 계산하는 기법 중 하나이다. Topcoder나 Codeforces에서 문제들을 풀다보면 포함-배제의 원리를 이용해야 시간안에 해결할 수 있는 문제들이 존재한다. 이 외에도 여러 수학적 지식을 요구하는 문제들이 종종 출제된다. 포함-배제의 원리는 원리 자체로는 중학교 수학에서 공부하여 잘 알려져 있는 편인데, 벤 다이어그램에서가 아닌 실제 문제에서 이를 응용하는 것은 꽤 까다롭게 느껴질 수 있다. 1) 집합이 두 개인 경우$|A|$를 유한 집합 $A$의 크기라고 하면, 두 유한 집합 $A$, $B$의 합집합의 크기 $|A \cup B|$는 아래와 같다. 2) 집합이 세 개인 경우세 개의 유한 집합 $A..

이 문제에서 독특한 성질의 그래프가 주어진다. 답으로 어떤 노드 집합을 구해야하는데, 이 노드 집합에 있는 각 노드는 서로 연결되어 있지 않으며, 각 노드별로 주어진 특성값의 합이 최대가 되어야한다. 아직 이 문제의 정해를 찾지 못 했다. 우선 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개의 문제로 ..