History: 제 1회 알고스팟 새싹 콘테스트

개요

알고스팟 운영진 중 이태윤, 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 정주경

풀이

힌트같은 해법을 추가했습니다. (저자 직강!)

문제 A JEONGLIBE

kcm1700 - 적절한 정규식과 대소문자 변환만 신경써서 만든 제목,아티스트 쌍의 결과물들을 정렬한 후 unique한 개수를 세어주는 방법으로도 풀 수 있습니다. 대회 도중에는 shell script를 짰는데 그 때 쓰인 유틸리티는 sed, tr, sort, uniq였습니다.

문제 B NUINJABMK

크기에 따라 해쉬값 저장해서, 저장된 해쉬값 종류 수를 세면 됩니다.

문제 C JAEHACHERRY

기준이 되는 물건을 하나 잡아서(예를 들면 candy) 가치를 계산해보면 됩니다.

문제 D-1

문제 D-2

문제 E SEOULGREUNIV

여러가지 방법이 있는데, 저자가 푼 방법은 이렇습니다.

  • 두 선분 쌍으로 만들어지는 모든 도형 구하기
  • 모든 도형 사이의 교점 구하기
  • 교점의 x좌표들 사이 구간별로 적분하기(심슨룰)

문제 F PROGRAMPAINTER

패턴의 (너비, 높이)가 패턴별로 거의 유일하게 결정됩니다. 아마 (15, 8) 빼곤 전부 유일한 크기일 겁니다. (15, 8) 크기의 패턴은 o개수를 세어보면 구분 가능합니다.

문제 G BODY

DP로 풉니다.

문제 H RECLAMATION

  • 외곽선을 따라 1xH 와 Wx1 크기의 직사각형 모음으로 도형을 분해합니다.
  • 직사각형 모음 끼리 비교하며 몇 년 후 두 도형이 만날 지를 계산해서 그래프를 구성합니다
  • 답을 이분검색해서 최초로 연결그래프가 되는 값을 찾습니다.

문제 I TWONQR

  • 2Nx2N 체스판에 퀸을 먼저 놓습니다.
  • 남은 자리에 룩을 놓는데, 2^N DP를 쓸 수 있습니다.
  • 대칭을 고려해서 적당히 프루닝 합니다.
  • 오랫동안 기다립니다. (최신형 컴퓨터에서 2시간 반 정도)

문제 J SIDEWALK10

  • 답을 이분검색합니다.
  • 구에 해당하는 정점을 만듭니다.
  • 구와 구 사이 간선에 해당하는 정점을 만듭니다.
  • 정해둔 답과 입력으로 주어진 값을 이용해서 네트워크 플로를 돌립니다.

더 보기