새싹컵 문제 해법 토론해봐요!

  • sven
    sven

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

    A JEONGLIBE
    "모든 파일은 위 4가지 중 한 가지 형식으로만 해석될 수 있습니다." 라고 되있으니까, 적당히 스트링 함수 find_last_of 등을 사용해서 정리한 후 stl set 에 넣고 해결했습니다.

    B NUINJABMK
    주어진 타일이 같은지 다른지는 숫자를 다시 매김으로써 알 수 있을 것 같은데요, N^6은 TLE 가 뜨더군요. (사각형 확정에 N^4, 사각형 순회에 N^2)

    C JAEHACHERRY
    정점 N+1, 간선 N, 연결그래프니까 트리 형태네요.
    정점 값을 double로 주고 순회하면서 계산해서 해결했습니다.
    물건의 갯수가 8개 이하라는 조건이 있어서, 매번 오차가 최대 8 = 2^3, N <= 15 회 반복해도 double 의 오차를 벗어나지 않더군요.

    D-1
    그냥 알파벳 재배열하고 구글링하니까 위키피디아 bootstrapping 문서에 정확히 같은 문구가 있더군요.

    D-2

    E SEOULGREUNIV

    F PROGRAMPAINTER

    G BODY

    H RECLAMATION
    각 섬들을 정점으로, 두 섬이 연결되는데 걸리는 시간을 간선으로 생각하면, 간선의 값은 두 섬의 꼭지점들만 비교함으로써 얻을 수 있습니다. (max(abs(a.x-b.x), abs(a.y-b.y)) 꼴) 이후 MST 풀듯이 하면 될 것 같은데, 아직 해결하지는 못했습니다.

    I TWONQR

    J SIDEWALK10


    11년 전
7개의 댓글이 있습니다.
  • kcm1700
    kcm1700

    A번 문제는 sed랑 tr이랑 sort랑 uniq랑 wc를 써서 해결할 수 있어서 그렇게 했습니다.


    11년 전 link
  • kcm1700
    kcm1700

    http://algospot.com/wiki/read/%EC%A0%9C_1%ED%9A%8C_%EC%95%8C%EA%B3%A0%EC%8A%A4%ED%8C%9F_%EC%83%88%EC%8B%B9_%EC%BD%98%ED%85%8C%EC%8A%A4%ED%8A%B8 위키에 틀 만들어뒀어요.


    11년 전 link
  • Being
    Being

    @kcm1700, [[제 1회 알고스팟 새싹 콘테스트]]라고 쓰시면 제 1회 알고스팟 새싹 콘테스트 처럼 링크가 걸립니다.


    11년 전 link
  • kwangswei
    kwangswei

    저 같은 하수는 힌트를 봐도 감이 딱 안오네요 ㅠ.ㅠ

    저는 C번 같은 경우는 다익스트라 알고리즘 썼습니다. 인접배열 만들어서 각 상품별 상대 가치로 만든 다음에 다익스트라(한 지점에서 다른 지점까지의 최단 경로 알고리즘 = 한 상품을 기준으로 다른 상품과의 상대 가격) 알고리즘 썼습니다~


    11년 전 link
  • silvester
    silvester

    E번 혹시 Convex hull 면적 구하는 것 외에 다른 방법 있을까요? ㅎ_ㅎ;


    11년 전 link
  • Being
    Being

    예제 그림에서 보듯 convex hull로는 전체 면적을 구할 수 없는 것 같습니다.


    11년 전 link
  • silvester
    silvester

    으어 그렇군요 ㅠ;


    11년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.