티스토리 뷰

공부

RUN@KAIST 7/26 방학 연습 풀이

구사과 2017.07.28 01:50

1. 평균값 수열

수열의 초항 S1을 결정했다 하면, S2 ... SN까지 모든 숫자들이 도미노처럼 결정된다. S_{i+1} = 2 * m_i - S_i 이기 때문이다. 고로, S1을 결정하면 모든 수열의 원소를 알 수 있고, 이들이 단조 증가 하는지만 체크해 주면 된다. 

모든 S1을 다 해 볼 수 없으니, 대신 S1 = x라고 두고 부등식을 계속 쓰는 식으로 x가 답이 될 필요 충분 조건을 찾아보자. 이렇게 했을 때, 수열은 {x, 2m1 - x, 2m2 - 2m1 + x, 2m3 - 2m2 + 2m1 - x ... } 과 같은 형태로 구해진다. 단조 증가한다는 것은 인접한 항들이 모두 <= 관계라는 것이다. 고로, 입력을 통해서 단조 증가하는 수열을 만들기 위한 x의 범위를 구할 수 있다. 최종적으로, 이 범위 안에 들어가는 정수의 개수를 출력하면 된다. 

한편, 문제 제한 상 O(1) 메모리에 답을 찾아야 한다는 점에 유의하라.


2. 민코프스키 합

오해를 막기 위해 적자면 IOI 2004에는 이런 문제 없었다. 대신에 원래 이상한 output only 문제가 있었는데, BOJ에는 이 output only 문제의 체커를 짜는 문제 (...) 가 올라와 있을 뿐이다.

다각형 1에 속하는 모든 각각의 점 (x, y)에 대해서, 다각형 2를 (x, y)만큼 평행이동 한 것을 그렸다고 하자. 이것들의 합이 우리가 구하는 민코프스키 합이 될 것이다. 문제는 다각형 1에 속하는 점들이 무한하다는 것인데, 이 경우에는 민코프스키 합을 어떻게 구할까? 모든 각각의 점이 아니라, 다각형 1의 꼭짓점에 대해서만 평행이동을 시키고, N개의 평행이동된 다각형들에 대해서 컨벡스 헐을 구하면, 그 안에 속하는 모든 점들을 다른 다각형으로 덮을 수 있기 때문에 답이 된다. N개의 평행이동된 다각형들에 대해서 컨벡스 헐을 구하는 것은 사실 거기 속하는 모든 점들을 상대로 컨벡스 헐을 구하는 것과 똑같으므로, 결론적으로 다각형 1의 점이 (x_a, y_a), 다각형 2의 점이 (x_b, y_b) 라고 하면, 모든 NM개의 점 쌍에 대해서 (x_a + x_b, y_a + y_b) 를 가지고 컨벡스 헐을 구해서 답을 출력하면 된다.

사실은 컨벡스 헐을 구하지 않아도, 각 다각형의 둘레를 이루는 방향 벡터를 따서 머지 소트와 유사하게 합쳐주는 방식으로도 풀 수 있다. 이 역시도 벡터를 각도정렬하면 간단하게 풀 수 있다. 다만 각도 정렬이 그닥 간단하지 않은 게 함정.. 이 때는 시간 복잡도가 O((n+m)lg(n+m)) 으로 위 풀이보다 훨씬 빠르다.


3. 정원

사실 2015년 봄에 만들어 놓은 풀이 슬라이드가 있다. 약간 직무유기 같지만 (...) 그 풀이 슬라이드가 잘 되어 있는 것 같아 슬라이드로 대체.

(IOI05) 정원 분할.pdf

'공부' 카테고리의 다른 글

RUN@KAIST 7/20 방학 연습 풀이  (0) 2017.08.07
OI Checklist 2017  (0) 2017.08.06
RUN@KAIST 7/26 방학 연습 풀이  (4) 2017.07.28
RUN@KAIST 7/27 방학 연습 풀이  (8) 2017.07.28
RUN@KAIST 7/13 방학 연습 풀이  (0) 2017.07.25
RUN@KAIST 7/16 방학 연습 풀이  (0) 2017.07.24
댓글
  • 프로필사진 블파 안녕하세요 koosaga님 블로그를 자주 보는 학생이에요 ㅎㅎ

    정원 문제에서 직사각형을 구할 때, 장미가 있는 점 i와 j를 포함하게 하는 가장 작은 직사각형을 만들었을 때, 직사각형 영역에 있는 장미의 개수가 k개가 되는

    직사각형만을 고려해서 문제를 해결해보려고 했는데, 안 되더라고요. 그 외의 풀이는 koosaga 님 솔루션과 비슷하게 했는데 뭐가 잘 못 된걸까요?

    저렇게 만든 직사각형 외에 둘레가 더 작은 직사각형을 만들 수 없지 않을까요?
    2017.08.06 21:46
  • 프로필사진 구사과 일단 정확히는 (i, j)를 포함하는 것이 아니라 (i, j)를 오른쪽 아래 끝 점으로 (내지는 왼쪽 위 끝점으로) 포함하는 직사각형들을 고려하는 것입니다. 아마 그렇게 이해하셨겠지만 다시 한번 명확히 하자면 그렇고요.

    제가 한 방식으로 하면 당연히 k개를 포함하는 가장 작은 직사각형을 찾으실 수 있습니다. 구현 방식에 문제가 있지 않았나 싶습니다. 다만 전 코드는 안 봐 드립니다. 제가 고쳐야 할 틀린 코드도 수십개기 때문에...
    2017.08.07 18:41 신고
  • 프로필사진 블파 그동안 이 문제를 아예 생각 안하고 있다가 댓글을 지금 봤어요. 구현에서 실수가 있었어요 ㅎ;
    답변해주셔서 감사합니다
    2017.08.14 12:03
  • 프로필사진 구사과 넵 수고하셨습니다 2017.08.14 18:50 신고
댓글쓰기 폼
공지사항
Total
217,103
Today
403
Yesterday
403