[editorial] 3주년 기념 대회 풀이 3줄 요약

  • Being
    Being

    운영진이 지쳐서 에디토리얼 준비에 조금 시간이 걸릴 듯 하니 -.-;; 간이라도 보시라는 의미에서 3줄 요약 나갑니다.

    A. Lecture Note - altertain / lewha0

    두글자씩 잘라서 정렬해도 OK

    두글자씩 잘라서 26*26 배열에 counting sort 해도 OK

    문자열 입력정도는 해주셔야..

    B. 2010 프로야구 - LIBe

    각 경기에 대해서 모든 경우를 따지면 3^R이 되므로 적절하지 않습니다.

    생각해보면 무승부는 양팀 모두에게 패이므로 응원팀은 전승하고 나머지는 무승부하면 전패와 같은 효과를 얻습니다.

    이후 정렬하면 되는데, 계산시 a / b < c / d 가 아닌 a * d < b * c 로 비교하는것을 권합니다.

    C. Microwaving Lunch Boxes - Being

    먹는 시간이 큰 것부터 먹으면 됩니다.

    만약 그렇게 하지 않는 최적해가 존재한다고 치면,

    순서에 어긋나는 두 개 순서를 바꾸면 답이 항상 같거나 좋아집니다.

    D. Unordered Subsequence - Astein

    어떤 문제에서 묻는 수열이 존재하면 첫 원소를 포함하는 길이 3인 수열이 존재합니다.

    따라서 뒤에서부터 전처리하며 이보다 작은/큰 원소가 자신 뒤에 존재하는지 표시하고 가장 앞선 것을 선택합니다.

    물론 답이 0인 경우는 일단 예외처리해야 하고, 입력에 음수도 주어질 수 있습니다.

    E. Sutag-Craft - 그래요

    온갖 다양한 방법으로 풀린 문제입니다.

    의도한 풀이는 Row[a] ^ Col[b] = Row[c] ^ Col[d] 의 양변을 조작해

    Row[a] ^ Row[c] = Col[b] ^ Col[d] 이므로 행끼리/열끼리 O(N^2) 번 계산해 배열에 저장하는 것입니다.

    F. reCAPTCHA - JongMan

    각 구간마다 항상 유사도가 가장 높은 글자를 사용하는 것이 현명하기 때문에,

    결국 N개의 구간을 파티션하는 문제가 됩니다.

    O(n^2) 의 동적 계획법으로 쉽게 풀 수 있습니다.

    G. Camel Cricket - Astein

    2p1 <= p2 인 경우 한 칸 짜리만 사서 쓰는게 이득이므로 별도로 처리합니다.

    이외의 경우는 p2짜리 블럭을 최대한 많이 쓰면 되는데,

    격자판은 이분그래프이므로 이분매칭한 만큼 사용하면 됩니다.

    H. Bacteria - gw

    단순히 시뮬레이션을 하면 시간 복잡도가 O(WHT)가 되어 TLE가 납니다.

    잘 생각해 보면 시작한 지 1초가 지난 후에는 path 혹은 loop만 남으니까......

    자세한 설명은 생략한다.

    I. Space Kite - altertain

    아래 두 그림을 보십시다.

    http://bit.ly/bmFFmK

    http://bit.ly/b7xeEK

    J. Binary Search Tree - altertain

    이진 검색 트리의 루트의 서브트리도 이진 검색 트리입니다.

    단, 왼쪽 서브트리는 전부 루트보다 작아야 하며 오른쪽 서브트리는 전부 커야 합니다.

    재귀적으로 이진 검색 트리인지 확인하면 됩니다. J번이지만 쉽지요.


    8년 전
14개의 댓글이 있습니다.
  • VOCList
    VOCList

    그림이 안떠요 ㅠ


    8년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    a / b < c / d 가 아닌 a * c < b * d ??? 뭔가 좀 이상한 듯?


    8년 전 link
  • A.I
    A.I

    모두 양수이므로, 양변에 a*c 를 곱한 것 아닌가요 'ㅁ'


    8년 전 link
  • Kureyo
    Kureyo

    오타인듯하네욤 ~_~ a / b < c / d <=> a * d < b * c 가 맞겠지요? ㅎㅎ


    8년 전 link
  • hyunhwan
    hyunhwan

    넵 오타가 맞아염. 수정했어요.


    8년 전 link
  • Being
    Being

    매눈들이시군요 ㅠㅠ


    8년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    근데 그냥 double로 계산하면 문제가 있나요 'ㅅ'? 물론 0/0 처리는 미리 한다 치고..


    8년 전 link
  • VOCList
    VOCList

    이문제는 별 문제 없을거같긴 한뎅...


    8년 전 link
  • Pekaz
    Pekaz

    J 번은 걍 Inorder 로 탐색해서 탐색순서가 정렬된순선지 보는 방법도 있는데.. 뭐 둘다 쉬우니 ㅋㅋ..


    8년 전 link
  • Chul
    Chul

    H 문제에서 입력의 모든셀이 '.'인경우는 0이고, '*'이 하나만있는경우는 2인가요? 그리고 답이 1이나 3이상은 나올수 없나요?


    8년 전 link
  • astein
    astein

    B번 나눠서 비교하기 전에 분모가 0인 경우 1로 바꿔주는 트릭을 사용하면 happy한 세상이 옵니다. :D double 써도 아무 문제 없음 'ㅅ'


    8년 전 link
  • 쌀자루
    쌀자루

    Chul// '*'이 하나만 있으면 한 단계 뒤에 모두 죽으니 1이 답입니다. 3 이상의 답도 가능합니다.


    8년 전 link
  • Chul
    Chul

    쌀자루// AC받았습니다 감사합니다 ^^


    8년 전 link
  • Kimchi
    Kimchi

    우오오


    3년 전 link
  • 댓글을 남기시려면 로그인하세요.