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

문제 링크
https://dl.dropbox.com/u/5327300/contest.htm

공지글 - http://algospot.com/forum/read/1684/
결과공지글 - http://algospot.com/forum/read/1693/

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

A JEONGLIBE

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를 쓸 수 있습니다.
  • 대칭을 고려해서 적당히 프루닝 합니다.
  • 오랫동안 기다립니다. (제 컴에서 3시간 정도)


J SIDEWALK10

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