History: 제 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 정주경

풀이

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

문제 A JEONGLIBE

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

문제 B NUINJABMK

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

문제 C JAEHACHERRY

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

문제 D-1

  • 주어진 입력 파일을 잘 보시면, 각 단어별로 anagram을 적용한 형태입니다.
  • 이를 파악하고 원문의 형태로 복원한 다음, 구글 검색등을 이용해 입력 파일의 문단이 속한 웹 페이지를 찾을 수 있습니다.

문제 D-2

  • 숫자가 나열된 입력 파일의 숫자들을 3개씩 끊어서 읽고, 해당 숫자에 대응되는 바이트 값으로 변환 시키면 zip파일의 형태임을 알 수 있습니다.
  • zip 파일에 저장된 2개의 파일(암호화된 파일, 사전 파일)을 통해서 원문을 복원 합니다. 이때 사람의 힘을 통해서 복원 가능하지만, 동적 계획법 등을 이용해서 복원이 가능합니다.
  • D-1 과 유사하게 암호화 된 문단은, 인터넷 상에 존재하는 문서입니다. 하지만 D-1대로 답을 입력할 경우 오답 처리가 됩니다.
  • 최종적으로, 암호화된 파일에 적혀있는 ___ 에 들어갈 적절한 3글자의 단어(정확히 말해서는 약어)를 찾아야 합니다.

문제 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

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

더 보기