PS 이야기

이 문제는 말리면 꽤 시간이 많이 걸릴 듯 해보이는 문제다.대회 당시에는 나는 문제도 모른채, 팀원이 막힘 없이 풀어주었다. 대회가 끝나고 글을 쓰기 위해 문제를 생각해보았는데, 생각하는데 오래 걸린 편이었다. 이런 개미 문제 컨셉은 BOI? CEOI? 기출 문제에도 있다. 그 문제에서 중요한 점은 "개미의 충돌이 있어도 개미가 떨어지는 시점(시간)은 변함 없다." 이다. 이 문제에서도 꼭 필요한 아이디어다.추가 설명을 하자면, 개미의 충돌이 있고 두 개미가 서로 방향을 바꿔, 왔던 길을 다시 가더라도 멀리서 봤을 때, 충돌 없이 개미가 서로 지나쳐 가는 것이랑 다를 것이 없다. 하지만 이 문제에서는 떨어지는 개미의 index를 알아야 한다.필자는 이 문제를 쉽게 생각했다가 말려 시간이 오래걸린 케이스다..

두 개의 Priority Queue(heap) 를 이용해서 문제를 해결할 수 있다.하나는 max heap이고 하나는 min heap 이다. heap에 원소의 값과 동시에 index도 같이 pair로 삽입한다.그리고 pop 될 때 해당 index에 visit 체크를 해주고, 최대 최소 값을 구할 때에 이미 visit가 체크된 것은 무시해주면 된다. 이러한 테크닉은 코딩이 편하며, 시간복잡도에 영향이 없다.하지만, 공간 복잡도에는 영향이 있지만 빅오표기법 상으로는 영향이 없다.(Memory sensitive 한 문제에서는 직접 heap를 구현해야할 수도 있다.) 처음에 문제를 각 쿼리마다 최대, 최소 값을 출력해야 되는 문제를 오해하고 생각해 보다 간단한 방법이 존재할 수도 있다. ** 대회 때는 없던 크리..

아직 풀지 못 했다.

한글 문제 부터 순서대로 훑어서 가장 먼저 풀게된 문제다. 처음에 수식으로 문제를 풀려하다가 시간이 오래걸릴 것 같아, $O(N)$에 풀게되었다. 생각은 해보지 않았지만, 분명 더 빠른 방법들도 존재할 것이다. 우선 문제에서 $$ 가 주어진다.이 때 가능한 연도는 $year = k \times N + y \space (0 \le k < M)$ 이다.따라서 k를 0 부터 M-1 까지 돌려보고 $year$ 를 구한 뒤 $x \equiv year (\bmod M)$인 경우가 있으면 그 $year$를 출력하면 되고, 아니면 -1을 출력하면 된다. 자세히 적진 않았지만 modulo 연산을 통해 0이 나오면 M으로 바꿔주는 과정이 필요하다.

입력으로 주어지는 두 점 $(x1,y1)$ $(x2,y2)$를 잇는 선분이 있다.(WLOG 편의상 $x1 \le x2 , y1 \le y2$) 입력으로 주어지는 직선은 수직선이나 수평선이다.따라서 $x = a$ 꼴의 수직선이 이 선분과 교차하기 위해서는 $x1 \le a \le x2$ 이여야 한다.$y = b$ 꼴의 수평선이 이 선분과 교차하기 위해서는 $y1 \le b \le y2$ 이여야 한다. 이 관찰을 통해, 이 문제를 indexed tree로 $O(N \lg N)$ 만에 해결할 수 있다.x좌표의 트리, y좌표의 트리 두 개를 만들어야 하는데, 두 과정이 똑같으므로 x좌표의 트리에 대해서만 설명하겠다. 우선 indexed tree의 각 노드를 stack으로 잡는다.모든 선분에 대해, 선분이 차지하..

님 게임(Nim game)은 수학적 전략 게임이다. 여러 개의 돌 무더기가 있다. 두 사람이 서로 차례를 번갈아가면서 게임한다. 자신의 차례에 하나의 돌 무더기를 선택하여 1개이상 원하는 만큼의 돌을 제거할 수 있다. 마지막 남은 돌을 제거하는 사람이 게임에서 승리한다.님 게임에 대한 이해를 돕기 위한 플래시 게임이 있다. http://www.gamedesign.jp/flash/nim/nim.html님 게임에는 수학적 필승 전략이 있다. 중,고등학교 수준의 KOI, IOI에서는 님 게임 관련 문제가 안나온다. 그렇다고해서 이해하기 어려운건 전혀 아니다. 그 전략은 간단하며, 아래와 같다.자기 차례에 각 돌 무더기에 있는 돌의 개수를 XOR($\oplus$) 연산 했을 때 값을 0으로 만들어주면 이긴다. ..

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/parrots.pdf서브태스크1 (17 점) 배열에 저장되어 있는 변수가 0 또는 1이다. 따라서 값이 1인 것의 위치들을 넘겨주면 된다. 위치는 0부터 7 사이의 정수이므로 넘겨주는데 별다른 무리는 없다. 이 때 호출 회수는 최대 N이 된다. 서브태스크2 (17 점) 이제, 배열에 저장되어 있는 변수는 0 이상 255 이하이고, N은 16이하다. 변환된 수는 0 이상 65536 이하이다. 변환된 수는 총 16비트를 가질 수 있다. 위치를 나타내는 4비트, 값을 나타내는 8비트, 총 12비트를 사용하여 각 위치에 어떤 값을 가지고 있는지 변환할 수 있다. 이 때 호출 회수는 N이 된다. 서브태스크3 (18 점) 수의 비트 수는 ..

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/elephants.pdf대회 당시 이 문제에 상당히 많은 시간을 투자했다. 시간제한이 9초라는 것을 간과하고 단지 N 제한이 크다는 이유 만으로 해법이 $O(N lg N)$ 꼴로 나올 것이라 확신했었다. 부분 점수를 받기 위해 $O(N\sqrt{N})$ 꼴의 방법도 생각해보았지만, 실패했었다.대회 끝나고 나오자마자 당시 조교로 있었던 권순일 형의 짧은 말로 이 문제의 해법을 깨닫게되었다. 2년이 지난 지금까지도 기억에 남는다. 시간복잡도는 $O(N\sqrt{N})$ 이 맞다. 안된다고 생각할 수 있지만, $\sqrt{N}$ 번의 update 마다 새로 그룹들을 $O(N)$만에 구성해주면된다. 그러면 총 시간복잡도를 $O(N\sq..

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/crocodile.pdf우선, 0번 방에서 탈출 방에서 가는 것이 아닌, 탈출방에서 각 방으로 가는 방향으로 뒤집어 생각해야한다. $$D[i] = 악어문지기가\ 최선을\ 다\ 할때,\ 임의의\ 탈출방에서\ i번\ 방으로\ 오는\ 최소\ 시간$$D[i] 를 위와 같이 정의하자. D[i]는 i번 방으로 올 수 있는 방들 중에 D[j]+(j번 방에서 i번 방으로 이동하는 시간)이 2번째로 작은 값을 취해야한다. 이를 해결하기 위해서는 $O(N^2)$ 방법과 $O(N lg N)$ 방법이 존재한다.$O(N lg N)$ 방법은 힙(heap)을 이용해 다잌스트라(Dijkstra's Algorithm)를 돌리듯이 하면 된다.코드: http:/..

초등학교 3학년 때 간단하게 html 코딩하면서 홈페이지 만드는 것을 좋아했었다. 그 때 부모님을 겨우겨우 설득해 myungwoo.net 으로 도메인을 만든적이 있었다. 당시에 물론 나 혼자 좋아하고 놀기 위해 만들었었지만, 도메인이 어떻게 구성되어 있는지 이론은 아무것도 모른채, http://myungwoo.net 에 접속했을 때 내 홈페이지가 뜨는 것에 마냥 신기해 했다.정확히 10년이 지난 지금, 10년 전과는 많이 발전한 목적으로 도메인을 구매했다. 항상 나만의 도메인을 가지고 싶다고 생각했었고, 성인이 된 지금 2만원가량의 결제를 망설일 이유가 있을까... 어렸을 때 도메인을 구매했을 때 처럼 마냥 신난다.예전에 쓰던 .net 이 아닌 10년 전에는 존재하지 않았던 .kr 을 쓰기로 했다. 그리..