티스토리 뷰

Codejam

Google CodeJam 2015 Round 2

전명우 2015. 5. 31. 21:02

문제 링크


A. Pegman


$N \times M$ 크기의 직사각형 모양에서 임의의 위치에서 시작해서 움직인다.  본인이 서 있는 위치에 화살표가 있으면 그 방향으로 다음 화살표를 만날 때까지 걸어가고, 만약 서 있는 위치에 화살표가 없으면 움직이지 않는다. 이 때, 놓여있는 화살표의 방향을 최소한으로 바꿔서 어떤 위치에서 시작하는지와 상관 없이 직사각형 밖으로 넘어가지 않게하는 문제다.

아주 당연히, 화살표가 있는 위치들에 대해서만 고려해주면 된다. 화살표가 있는 위치에 대해서 화살표가 가르키면 안되는 방향들을 바로 구할 수 있다. 그 방향에만 놓지 않도록 최소 개수로 화살표를 바꾸면 된다.



B. Kiddie Poole


$N$개의 수도파이프가 있고, $i$번째 수도 파이프에서 단위 시간당 나오는 물의 부피는 $r_i$이며, 물의 온도는 $c_i$이다. 이 때, 총 물의 부피가 $V$이고, 온도가 $X$가 되도록 물을 모으는 최소 시간을 구하는 문제다. 문제 조건에서 각 수도 파이프는 최대 한 번만 껐다킬 수 있다는 조건이 있지만, 이 조건을 고려하지 않고 문제를 풀어도 무방하다.

어떤 시간 $t$ 동안 온도 $X$가 되게 물을 최대 얼만큼 받을 수 있는지 계산을 할 수 있다고 하자. 그러면 이분검색으로 답을 구할 수 있다.

온도가 $X$가 되게 물을 받을 수 있는 방법은 $X$ 보다 온도가 큰 물과 $X$ 보다 온도가 작은 물을 섞어 온도 $X$를 만드는 방식으로 물을 받는다고 생각하면 된다. 다만, 최대한 물을 많이 받아야하니까, $X$에서 가장 가까운 두 온도의 물을 섞어주면 된다.



C. Bilingual


문장은 영어 또는 불어 둘 중 하나이고, 영어 문장에 있는 단어는 모두 영어 단어이며, 불어 문장에 있는 단어는 모두 불어 단어이다. 영어 문장 하나, 불어 문장 하나, 그리고 다수의 어느 나라 문장인지 모르는 문장들이 주어졌을 때, 영어와 불어 모두에 속한 단어의 최소 수를 구하는 문제다.

그래프를 잘 구성하고, minimum cut을 구하면 된다. 등장한 단어가 총 $W$개라고 할 때, 이분매칭 비슷하게 그래프를 만든다. 왼쪽에 노드 $W$개, 오른쪽에 노드 $W$개를 만든다, 영어 문장에 등장한 단어들에 대해 source에서 해당 단어의 왼쪽 노드로 가는 유량 $\infty$ 간선을 이어주고, 불어에 등장한 단어들에 대해 해당 단어의 오른쪽 노드에서 sink로 가는 유량 $\infty$ 간선을 이어준다. 그리고 단어별로 왼쪽 노드에서 오른쪽 노드로 가는 유량 $1$ 간선을 이어주고, 같은 문장에 등장하는 서로 다른 두 단어에 대해 한 단어의 오른쪽 노드를 다른 단어의 왼쪽 노드로 유량 $\infty$ 간선으로 이어주면 된다. 말이 굉장히 복잡하여, 그래프 구성하는 방법은 코드를 보는 것이 편할 수도 있다.

답이 되는 이유는 아래 스케치에 적혀있다.





댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함