제 1회 알고스팟 새싹 콘테스트
개요
알고스팟 운영진 중 [[Taeyoon_Lee]], [[LIBe]], [[JongMan]] 이 준비한 IPSC 스타일의 대회이다.
- 대회 일시:
문제
https://dl.dropbox.com/u/5327300/contest.htm
결과
| 순위 | 팀명 | 팀원 |
|---|---|---|
| 우승 | ReddishN00b | [[김찬민 |
| 준우승 | 팀원이음슴 | 김재홍 |
| 3위 | 번인텐스 마셔야됨 | 김경근, 박연수, 한준희 |
| 4위 | 박재성 | 박재성 |
| 5위 | 내펜은길다 | 박재훈, 이종혁 |
| 6위 | 스트로베리익스트림 | 이준성 |
| 7위 | 구로디지털단지 | 권순일 |
| 8위 | D-76 | 김진호 |
| 9위 | ------ Cut Here ------ | 유현종 |
| 10위 | Apple_Cplus | 정주경 |
- 전체 순위표: https://dl.dropbox.com/u/5327300/bud2013/final.htm
- 대회 통계: https://dl.dropbox.com/u/5327300/bud2013/stat.htm
풀이
힌트같은 해법을 추가했습니다. (저자 직강!)
문제 A [[problem:JEONGLIBE]]
[[kcm1700]] - 적절한 정규식과 대소문자 변환만 신경써서 만든 제목,아티스트 쌍의 결과물들을 정렬한 후 unique한 개수를 세어주는 방법으로도 풀 수 있습니다. 대회 도중에는 shell script를 짰는데 그 때 쓰인 유틸리티는 sed, tr, sort, uniq, wc였습니다.
문제 B [[problem:NUINJABMK]]
크기에 따라 해쉬값 저장해서, 저장된 해쉬값 종류 수를 세면 됩니다.
문제 C [[problem:JAEHACHERRY]]
기준이 되는 물건을 하나 잡아서(예를 들면 candy) 나머지 물건들의 상대적 가치를 계산해보면 됩니다.
문제 D-1
* 주어진 입력 파일을 잘 보시면, 각 단어별로 anagram을 적용한 형태입니다.
* 이를 파악하고 원문의 형태로 복원한 다음, 구글 검색등을 이용해 입력 파일의 문단이 속한 웹 페이지를 찾을 수 있습니다.
문제 D-2
* 숫자가 나열된 입력 파일의 숫자들을 3개씩 끊어서 읽고, 해당 숫자에 대응되는 바이트 값으로 변환 시키면 zip파일의 형태임을 알 수 있습니다.
* zip 파일에 저장된 2개의 파일(암호화된 파일, 사전 파일)을 통해서 원문을 복원 합니다. 이때 사람의 힘을 통해서 복원 가능하지만, 동적 계획법 등을 이용해서 복원이 가능합니다.
* D-1 과 유사하게 암호화 된 문단은, 인터넷 상에 존재하는 문서입니다. 하지만 D-1대로 답을 입력할 경우 오답 처리가 됩니다.
* 최종적으로, 암호화된 파일에 적혀있는 ___ 에 들어갈 적절한 3글자의 단어(정확히 말해서는 약어)를 찾아야 합니다.
문제 E [[problem:SEOULGREUNIV]]
여러가지 방법이 있는데, 저자가 푼 방법은 이렇습니다.
- 두 선분 쌍으로 만들어지는 모든 도형 구하기
- 모든 도형 사이의 교점 구하기
- 교점의 x좌표들 사이 구간별로 적분하기(심슨룰)
문제 F [[problem:PROGRAMPAINTER]]
패턴의 (너비, 높이)가 패턴별로 거의 유일하게 결정됩니다. 아마 (15, 8) 빼곤 전부 유일한 크기일 겁니다. (15, 8) 크기의 패턴은 o개수를 세어보면 구분 가능합니다.
문제 G [[problem:BODY]]
DP로 풉니다.
문제 H [[problem:RECLAMATION]]
* 외곽선을 따라 1xH 와 Wx1 크기의 직사각형 모음으로 도형을 분해합니다.
* 직사각형 모음 끼리 비교하며 몇 년 후 두 도형이 만날 지를 계산해서 그래프를 구성합니다
* 답을 이분검색해서 최초로 연결그래프가 되는 값을 찾습니다.
문제 I [[problem:TWONQR]]
* 2Nx2N 체스판에 퀸을 먼저 놓습니다.
* 남은 자리에 룩을 놓는데, 2N DP를 쓸 수 있습니다.
* 대칭을 고려해서 적당히 프루닝 합니다.
* 오랫동안 기다립니다. (최신형 컴퓨터에서 2시간 반 정도)
문제 J [[problem:SIDEWALK10]]
* 답을 이분검색합니다.
* 구에 해당하는 정점을 만듭니다.
* 구와 구 사이 간선에 해당하는 정점을 만듭니다.
* 정해둔 답과 입력으로 주어진 값을 이용해서 네트워크 플로를 돌립니다.