어제 새벽에 열린 구글 코드잼 2라운드..
역시 예상대로 삽질만하다가 뭐하나 제대로 풀지도 못하고 끝나버렸다..
결국 1750 등이라는 굴욕적인 등수로 마감.. -_-

이날은 새벽인데다가 술도 좀 적당히 마시고 온 상태라.. 정신이 몽롱한 상태에서 문제를 풀었다..~
역시.. 상태가 이렇다보니.. 풀수있는문제도 다 놓치고.. 삽질만 열심히 했다..

A번은 매우 쉬운문제인데도 불구하고.. 끝내 greedy 라는 것을 간파를 못했다.. 젠장!!
결국 small input에 대해서만 brute force로 모든 경우를 다 체크하는 방법으로 풀었는데..
large 에 대해선 max flow로 뭐 어떻게 안되나 고민하다 포기.. ㅠ_ㅠ
참가한 사람들은 대부분 풀었는데.. 왜 난 못풀었을까..

B번은 뭔가 BFS로 해야하나.. 고민하다가 상태공간이 너무 큰데다가 코딩도 까다로울것같아서 포기..

C번이 가장 아쉬운 문제였다..
bipartite matching 이란거까지 간파를 했는데.. 그래프 구성을 이상하게하고 왜 샘플이 안나오나 고민하다가..
이렇게 푸는게 아니구나.. 포기하고 graph coloring 을 시도.. TLE 맞고.. 그냥 삽질하다보니 게임 종료.. ㅠ_ㅠ

D번은 상당히 쉽지않아보였는데.. small input은 input 개수가 매우 작아서 그냥 모든경우를 다 시도해봤다..
두 원의 반지름이 각각 r1, r2 이고 중심끼리의 거리 = d 라고 하면
두 원을 커버하는 가장 작은 원의 반지름 r' = (d + r1 + r2) / 2 가 되는가보다..
긴가민가 했는데.. 서밋해보니 맞더군..



이렇게해서 올해 코드잼은 여기서 접게 되었다..~
내년에는 컨디션 조절을 잘 해서 티셔츠를 목표로 다시 도전해야겠다..~


굿바이 코드잼 2009..
굿바이 티셔츠.. ㅠ_ㅠ


http://code.google.com/codejam


to Top