PS 이야기

링크: https://code.google.com/codejam/korea/ 구글 코드 잼은 다들 잘 알 것이다. 구글 코드잼 한국 대회가 2012년에 딱 한 번 열렸다.2013년도에도 열리길 기대했었지만, 내가 알 수 없는 이유로 열리질 않았다. 우연히 기회가 되어 Google Codejam Korea 2012에 참가했다.1년도 지난 일이라 당시 상황이 잘은 기억이 나질 않는다.예선 라운드는 그럭저럭 코딩이 빨리 되어 2등을 했었고,1차 본선 때는... 말렸었던 것으로 기억한다.여러 문제로 1차 본선은 무효처리 되고, 2차 본선이 열리게 되었다. 2차 본선 때는 그리 컨디션이 좋진 못했지만, C번 문제가 평소 즐겨 풀던 매칭 문제가 나와 무난하게 해결하여 패널티가 낮은 덕분에 결선에 진출할 수 있었다...

문제 설명은 매우 긴 반면에 문제는 매우 간단하게 풀 수 있다. 판도라(로봇)가 가리킬 수 있는 방향은 상,하,좌,우 뿐이다. 처음 시작 방향은 중요하지 않다. 문제 입력에서 R이 세 번 이상 반복하면, X,Y 축 모두에 대해 monotone하지 않게 된다.만약 R이 두 번 반복한 경우가 있다면, 판도라의 방향에 따라 X축이나 Y축 둘 중 하나가 monotone 하지 않게 된다. 이 두 조건을 알면 문제를 해결할 수 있다.한 가지 주의해야 할 점은 입력 Sequence가 R로 시작할 경우 Sequence 끝의 R과 연결이 될 수 있다는 점이다.

문제에 중요한 명제가 있다. 주어진 $N$개의 점들을 모두 덮는 최소 크기의 정사각형으로, $N$개의 점을 모두 덮을 수 있는 최소 두께의 정사각형 액자를 만들 수 있다.문제 설명에 따르면 위 명제는 이미 증명된 사실이며, 이 조건 없이 문제를 해결하기는 매우 힘들다. $w \leq w'$ 일 때, 두께 $w$가 모든 점을 덮으면 두께 $w'$도 모든 점을 덮을 수 있다. 따라서 답을 binary search로 구할 수 있다. 우선, 편의상 $max_x-min_x \leq max_y-min_y$ 라 하자.그러면 액자의 바깥 정사각형의 한 변 길이 $S = max_y-min_y$ 임과 동시에 액자 위의 y좌표와 아래의 y좌표가 결정된다. 이제 두께 $w$가 답이 될 수 있는지 확인해야한다.이 때, 여러가지..

문제 설명에 의해 이벤트 $E_i$와 이벤트 $E_j$가 답이 요구하는 집합에 같이 있을 수 없는 조건은,$s_i + d_i + t_{i,j} \leq s_j$ 또는 $s_j + d_j + t_{j,i} \leq s_i$문제에 있는 조건 $t_{i,j} \leq t_{i,k} + t_{k,j}$ 에 의해서, 다음과 같은 정리가 성립한다.$E_i$와 $E_j$가 같은 집합 안에 있을 수 없고, $E_j$와 $E_k$가 같은 집합 안에 있을 수 없으면, 항상 $E_i$와 $E_k$도 같은 집합 안에 있을 수 없다.위 정리가 성립하므로, 이 문제를 이분 그래프의 Minimum Cut으로 해결할 수 있다. 우선, 이분 그래프의 왼쪽과 오른쪽에 각각 $n$개의 $E_i (1 \leq i \leq n)$ 들을 배치..

대한민국 ICPC 문제들은 데이터와 솔루션이 공개되지 않는다. 때문에 온라인 저지에서 한국 ICPC 문제들을 보기 힘들다. Baekjoon Online Judge 에서 간혹 한국 ICPC 문제들이 보인다. 어둠의 경로(?)로 데이터를 입수하는 방식이 아닌 관리자 혹은 회원이 데이터를 직접 만들어서 등록하는 방식으로 진행되는 것 같다. 그 곳에서 인터넷 예선 공부하기 너무 편했고, 그에 보답하기 위해 이번 인터넷 예선 데이터들을 만들어 보았다. 시간 날 때 마다 만든다고 시작한 것이 하다보니, 상당히 많은 문제들의 데이터를 만들게 되었다. 과거 KOI 준비하면서 내 솔루션이 맞는지 검증하기 위한 프로그램을 C++로 코딩했었는데, 최근 들어서 python으로 하면 굉장히 편하다는 것을 느꼈다. KOI는 이제..

$O(N^2)$ Dynamic Programming 으로 풀린다.BOI 2009 beetle 문제와 매우 비슷한 문제이다. beetle 문제가 더 어렵고 이 문제는 더 간단하며, 다양한 풀이가 있을 것으로 예상된다. 우선 다이나믹 배열의 정의는 아래와 같다.L[i][j] = $p_i$ 부터 $p_j$까지 모두 방문했고 마지막 방문 지점이 $p_i$일 때 ($i

이 문제는 전형적인 '가중치가 있는 이분매칭' 이다.이러한 이분 매칭을 푸는데는 크게 두 가지 방법이 있다.MCMF(Minimum cost & Maximum flow)와 헝가리안 메소드(Hungarian method) 가 있다. 필자는 헝가리안 메소드를 푼지 오래되어 이 문제를 MCMF로 해결했다. 이 문제에서는 두 매치 사이에 간선이 없는 경우가 있어서 헝가리안 메소드로 풀릴 수 있는지 헷갈릴 정도로 헝가리안 메소드에 대해 모른다. MCMF가 다루는 그래프는 일반 maximum flow 문제에서 다루는 그래프와 사뭇 다르다.maximum flow 에서 다루는 문제에서 그래프의 간선은 하나의 특성 값, 유량을 갖는다.하지만 MCMF에서 다루는 그래프에서 간선은 두 개의 특성 값, 유량과 비용을 갖는다.유..

전형적인 이분매칭 문제다. 대회 끝나고, 단순히 '매칭'이라고만 들었을 때는 전혀 와닿지 않았고 해법이 떠오르질 않았다. 그래프를 어떻게 구성해야되는 것이며 그래프를 어떻게 구성해야되는 것이며... 머리 속이 복잡했다. 우선 이분 그래프의 양쪽에 0번 부터 $N-1$번까지 노드들을 총 $2N$개 만든다. i번 노드에서 j번 노드로 가는 방향성 에지가 있으면 이분그래프에서 왼쪽 i번 노드에서 오른쪽 j번 노드로 뻗는 간선을 그어준다.그 뒤 최대 매치수가 곧 답이다. 이 방법으로 답이 나오는 이유에 대한 자세한 설명은 생략한다. 포트퍼거슨으로 짜도 시간안에 나올 수 있다. 하지만, Hopcroft-karp 알고리즘을 통해 최악에 $O(M \sqrt{N})$의 시간복잡도로 풀 수 있으며, 평균 시간복잡도 $O..

문제에서 주어진 식을 그래프 DAG(Directed Acyclic Graph)로 잘 만들어주면, 비교적 쉽게 풀리는 문제다. 한 마디로, 이 문제를 노가다성 문제라고 생각한다. DAG를 구성하는 방법은 구체적으로 설명하지 않겠다. 까다로울 수 있지만 특별한 알고리즘이 필요한 것도 아니고 사람마다 저마다의 방법이 있을 것이라 생각하기 때문이다. 필자는 A(B|CD(E|_)G)E 가 입력으로 들어오면 아래와 같이 그래프를 구성했다. 그래프를 구성 한 뒤에는 DP(Dynamic Programming)을 통해 해결하면 된다.그래프를 구성하는 노드의 개수를 $N$이라 하고, 입력으로 주어지는 두 번째 문자열의 길이를 $L$이라 하자.우선 그래프에서 위상정렬를 통해 각 노드의 순서를 구한 뒤 그 순서대로 처리한다...

따로 설명할 것 없이, 문제에서 주어진 조건대로 해결 하면 된다.한 사람의 등수를 계산하는 것이기 때문에 따로 정렬해줄 필요도 없다. 문제 설명에 따라, 같은 시간에 이뤄진 제출이 없으므로, 같은 등수를 갖는 두 팀은 나올 수 가 없다. 문제 이름은 KCPC지만, 등수를 배정하는 기준은 2013년도부터 시행된 KOI 기준과 동일하다.