14개의 댓글이 있습니다.
-
-
Taeyoon_Lee -
a / b < c / d 가 아닌 a * c < b * d ??? 뭔가 좀 이상한 듯?
13년 전 link
-
-
-
Taeyoon_Lee -
근데 그냥 double로 계산하면 문제가 있나요 'ㅅ'? 물론 0/0 처리는 미리 한다 치고..
13년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
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번이지만 쉽지요.
13년 전