Coders high 2013
Coder's High 2013
개요
http://algospot.com/forum/read/1833/
Coder's High 2013 ~ Come And Make Programs ~ 라는 제목으로 2013년 여름에 열린 여름 알고리즘 캠프. xhaecamp라고도 불리고 있다. 더 줄이면 째캠(...). 7월 27일~28일 양일간 명동 서울유스호스텔에서 진행.
VOCList(a.k.a xhae, 태)가 전국 각지의 PS러들간의 친목을 도모하고자 소집해제 기념으로 기획하면서 열렸다. 공개 후 사전 신청 결과 인당 2만원의 참가비에도 불구하고 총 22팀 50여명이 신청하면서 신청이 조기 마감되는 등 폭발적인 기대를 받았고, 대회 당일에도 많은 팀들이 온라인을 통해 대회에 번외에 참가하였다. 알고스팟 캠프 이후 한 동안 열리지 않았던 오프라인 PS 캠프에 PS러들이 얼마나 목말랐는지를 알 수 있는 대목. 더불어 많은 알고스팟 운영진이 캠프 준비와 문제 출제에 각출되었다 카더라. 덕분에 8월 17일 전국 대학생 프로그래밍 대회 준비 동아리 연합대회 출제는 안드로메다로...
스폰서는 NGINE studios, SK Planet, 스마트스터디 공동 후원. 행사 티셔츠 오른 팔에 3사 로고가 박혀 있다. 티셔츠 뒷면 문구가 가히 압권(..)
AI Competition
- 다운로드
- 게임 설명: 그리드의 셀마다 -9 ~ 9 사이의 정수 점수를 가지고, 매 턴마다 현재 점령하고 있는 셀들의 점수 합이 내 총 점수에 더해진다. 1 vs 1 게임으로 맵마다 주어진 턴 수를 가지고 진행되며 플레이어는 매 턴마다 현재 위치를 중심으로 일정 범위를 점령하거나 이동을 할 수 있다. 주어진 턴 동안 높은 점수를 차지하는 팀이 이기는 게임.
- Postech의 Diplomatics 팀이 우승. 알고리즘의 요는 적당히 돌아다니며 꿀지역만 쏙쏙 빼먹고 도망가는거로... 상품은 국민보드게임 삼종신기. Poscat 동방에 가져다 놓을 거리가 생겼다고 좋아했다.
- 8강경기를 치르기 앞서 알고스팟 경마(...)를 진행하였으며 1, 2, 3위를 정확히 맞추는 사람에게 각각 3, 2, 1 포인트를 부여하였다. 16강때에 이미 압도적인 퍼포먼스를 보여줬던 Diplomatics가 가장 많은 투표를 받으며 우승하였으나, 두번째로 많은 투표를 받은 Pandaria가 8강에서 탈락하며 경마의 행방은 안드로로... 아무도(본인들조차) 신경쓰지 않았던 않았던 YonSEX팀이 2등을 하며 경마 1위는 1, 2위를 맞춘 zzapcoder님에게 돌아갔다. 부상으로 모든 행사 종료 후 행사 내내 소스코드만 몇백장은 뽑은 바로 그 프린터를 가져갔다고.
ICPC-Style Competition
1위 상품이 아이패드 미니, 2위 상품이 삼성 SSD 840 series, 3위 상품이 USB 메모리로, 팀원 숫자만큼 증정 이라는 조건이 달려 있었다. 그래서 "1인팀 우승을 적극적으로 기원해야겠군요..." 같은 이야기가 나오기도...
그런데 그것이 실제로 일어났습니다. (...) 최연소 참가자가, 그것도 혼자 출전해서 아이패드 미니를 가져갔다! 주인공은 중학생 다행히 고등학생으로 밝혀진 PS러로 그 전부터 종종 존재감을 나타내던 ainta(kaizero, 조승현) 군. 이번 대회를 통해 "김치 투어리스트"라는 별명도 간간히 나오는 상황. IOI 우승 세 번은 더 하고 오셔야... 그나저나 페널티 9분 차이로 아이패드 미니를 놓친 오리연못 팀은 그저 안습....
수상
| 종목 | 상품 | 입상자 |
|---|---|---|
| ICPC style competition 1위 | 아이패드 미니 | Kaizero (ainta) |
| ICPC style competition 2위 | 삼성 840 Series 120GB | 오리연못 (etaehyun4, mjy0503, suckzoo) |
| ICPC style competition 3위 | 잘만 16GB USB memory | Pandaria (hodduc, hankook) |
| AI-Competition 우승 | Clue, Bang, Halli Galli | Diplomatics (akdal, breakun, yougatup) |
| 경마 우승 | 행사에 사용해서 중고가 되어버린 프린터 | zzapcoder |
문제 목록
으앙 PC2가 어디갔는지 모르겠어요 통계따위 행방불명인가보다...
| 문제 | 출제자 | 최초로 해결한 팀 | 정답률 |
|---|---|---|---|
| A. 째능 교육 | LIBe | ||
| B. 사신도 | Kureyo, LIBe, xhae | ||
| C. Jump! Jump! | Astein | ||
| D. 우주 개발의 길은 멀고도 멀다 | altertain | ||
| E. Travel in xhaeland | Astein | ||
| F. 단짝 문자열 | altertain | ||
| G. 미금이의 수학과제 | xhae | ||
| H. Weekly Calendar | Kureyo | ||
| I. 백년 전쟁 | Kureyo | ||
| J. 책도둑 | Kureyo | ||
| K. 어떤 과학의 인공지능 청소기 | kcm1700 | ||
| L. k번째 사전순 숫자 | Kureyo |
Brief Solution 스포일러가 포함되어 있으니 문제를 풀 생각이라면 열지 말 것.
상세한 솔루션
J. 책도둑
평범한 0-1냅색이라고 가정하면 다음과 같은 DP식을 세울수있다:
- D[N, V] := N종류의 아이템에 대해 고려해서, V칸을 채웠을때의 최대 값어치
- D[N, V] = max\{ D[N-1, V], D[N-1, V-\text{(volume of item)}] + \text{(value of item)} \}
v_{i} = \text{(volume of item)}, c_{i} = \text{(value of item)}이라고 하고, 아이템의 갯수를 k_{i}라 하자.
위의 식에서 0-1을 0-k로 확장시킨다는 느낌으로 식을 바꿔 써보면:
묶어서 쓰면 다음처럼 쓸수있다.
x에 대한 식만 남기고 V에 대한 부분은 밖으로 뺄 수있다.
f(x) = D[N-1,x]-x/v_{i}*c_{i} 라고 하자.
그렇다면 D[N, V]를 다음과 같이 구할수 있다.
- f(V)값을 PQ에 넣는다.
- PQ의 top인 x값이 V와 v_{i} * k_{i}를 넘게 차이나면 top을 제거한다
- PQ의 top인 f(x)값에 대해 D[N,V] = f(x) + V/v_{i}*c_{i}이다.
최대 PQ의 크기는 O(V)이므로, 시간 복잡도는 O(NV lg V)이다.
이렇게 작성해도 AC를 받기엔 충분한 속도지만, 조금 더 속도 향상을 할 수 있다.
PQ안에 있는 2개의 t1 < t2에 대해 생각해보자.
만약 f(t1) < f(t2)라면 t1은 PQ의 top이 영원히 될수 없다.
그러므로 이러한 t1은 전부 배제되었다고 가정하면,
- PQ안 원소들의 x값들을 순서대로 x1<x2<x3..라 하면
- f(x1)≥f(x2)≥f(x3)≥...을 만족한다.
또한 위의 조건을 만족하도록 PQ를 관리하여야 한다.
이러한 구조는 선형 deque로도 관리할수있으며, 매 원소는 최대 한 번 삽입과 삭제가 발생하게 되므로 이때의 시간 복잡도는 amortized O(NV)이다.
