귀찮아서 안 쓰고 있었는데, O(nlogn)임에도 계속 시간초과를 받았던게 자꾸 생각나서 늦게나마 해법(결국 Fast I/O까지 써서 시간초과 X)을 올린다 -_-..

문제

철광석과 구리 광석이 묻혀있는 땅이 있다. 여기서 N(1 ≤ N ≤ 100,000)개의 광물(점으로 간주한다)의 좌표가 주어질 때, 어떤 점 P를 원점으로 잡고 1사분면의 구리 광석 개수, 2사분면의 철광석 개수, 3사분면의 구리 광석 개수, 그리고 4사분면의 철광석 개수를 셌을 때의 값을 최대화하도록 P를 정하고, 이때의 합을 출력하자.


파란색 점을 철광석, 갈색 점을 구리 광석이라고 생각하자.

P의 위치를 위와 같이 잡을 경우 합은 3(1사분면) + 3(2사분면) + 3(3사분면) + 2(4사분면) = 11이 된다.


*각 광물의 좌표는 모두 1 ≤ X,Y ≤ N 범위의 정수(자연수)이고, 모든 광물의 X좌표는 서로 다르고, Y좌표도 서로 다르다. 즉, 어떤 수평선 위에도 광물은 최대 한 개 존재하고, 어떤 수직선 위에도 광물은 최대 한 개 존재한다. 그리고, 점 P의 좌표는 실수를 가질 수 있다(즉, 경계선에 놓이는 광물은 없다고 보아도 된다).


풀이

우선 이 풀이를 이해하기 위해선 <Segment Tree> 라는 자료구조에 대한 이해가 필요하다 [링크1] [링크2].

Segment Tree를 처음 배울 때 보통 구간의 합을 구하는 예제를 통해 배우게 되는데, 이를 조금 확장하면 어떤 배열의 Prefix sum, 즉 A[1]+A[2]+...+A[i] (1 ≤ i ≤ N) 의 합이 최대가 되는 i와 그때의 합을 찾을 수 있다. 리프 노드의 최대 접두사 합은 자기 자신의 값으로 하고, 리프가 아닌 노드의 최대 접두사 합은 "왼쪽 자식의 최대 접두사 합"과 "왼쪽 자식의 합 + 오른쪽 자식의 최대 접두사 합" 중 큰 것임이 자명하기 때문에 접두사 합을 저장하는 배열을 하나 더 만들거나, 구조체를 이용해서 세그먼트 트리를 만들면 된다.

세그먼트 트리 코드 보기


이제 위의 자료구조를 이용해서 문제를 해결하는 방법에 대해 살펴보자.


점 P의 X 좌표가 특정한 값(이 값을 Px라고 하자)로 고정되어 있을 경우, 최적의 Y 좌표를 쉽게 구하는 방법은 무엇일까?

직관적으로 쉽게 알 수 있는데, 아래 그림과 같이 배열을 하나 만들고, X좌표가 Px보다 작은 철광석이 있는 Y좌표에는 -1, 구리 광석이 있는 Y좌표에는 +1, 그리고 X좌표가 Px보다 크거나 같은 철광석이 있는 Y좌표에는 +1, 구리 광석이 있는 좌표에는 -1을 준 다음, 접두사 합이 최대가 되는 지점이 바로 Px의 Y좌표가 된다(증명은 귀류법으로 간단히 할 수 있다).


맨 아래에서부터 (-1) + 1 + (-1) + (-1) + 1 + 1 + 1 = 1


이를 처음에 설명한 트리를 응용하여 모든 X좌표(N개(정확힌 N+1개)의 X좌표)에 대해 빠르게(O(logN)) 최적의 Y좌표를 구할 경우, 모든 P의 후보 지점을 살펴보는 데에 O(NlogN)의 시간이 걸리므로 최대 100,000개의 점을 처리하기엔 부족함이 없다.


우선 Px를 나타내는 가상의 수직선을 상상해보고, 다음 그림들을 보자. 


 -> 


이런 상황으로 초기화를 한다(px = 0) - O(NlogN) -> 여기서 최적의 y를 찾는다 - O(1) -> 합을 구한다 - O(1).
(합은 생각해보면, 간단하게 (최대 접두사 합) + (P 오른쪽의 구리 개수) + (P 왼쪽의 철 개수)이다)


이제 수직선을 한 칸 이동시켜서(Px = 1) 반복해보자.

수직선을 이동할 때 갱신해야 하는 것은 세 가지이다:

1. 세그먼트 트리에서 해당 X좌표에 있는 점의 부호를 바꿔준다 - O(logN).

2. 해당 점이 철광석일 경우 P 왼쪽에 있는 철 개수를 저장하는 변수(LEFT_IRON) - O(1)

3. 해당 점이 구리 광석일 경우 P 오른쪽에 있는 구리 개수를 저장하는 변수(RIGHT_COPPER) - O(1).




다시 같은 방식으로 Px=2, ...., Px = N까지 모두 확인해가며 합의 최댓값을 갱신해주면 정답을 구할 수 있다.


정답 코드 보기(base = LEFT_IRON + RIGHT_COPPER)

*10.23: 정식 채점이 가능해짐에 따라 코드 오탈자 수정(정식 채점: http://codeground.org)

테스트 데이터

랜덤하게 만들어본 테스트 데이터와 이에 해당하는 정답 데이터로, 이 데이터에 대한 정답이 0.5초안에 모두 나온지 않는다면 일단 시간초과는 확실한걸로..

sample.in.lzma

sample.out.lzma

(압축 해제를 해야 합니다..)


신고
  1. cujun 2016.07.22 15:22 신고

    작성자만 볼 수 있는 글입니다.

  2. chojl1125 2016.09.11 23:29 신고

    퍼가요~

  3. leejk9592@naver.com 2017.07.20 00:38 신고

    안녕하세요... 일단 좋은 글을 작성해주셔서 감사드립니다.
    해설을 읽던 도중,이해가 가지 않는 부분이 있어 염치불구 하고 질문을 드립니다.


    점 P의 X 좌표가 특정한 값(이 값을 Px라고 하자)로 고정되어 있을 경우, 최적의 Y 좌표를 쉽게 구하는 방법은 무엇일까?

    """
    직관적으로 쉽게 알 수 있는데, 아래 그림과 같이 배열을 하나 만들고, X좌표가 Px보다 작은 철광석이 있는 Y좌표에는 -1, 구리 광석이 있는 Y좌표에는 +1, 그리고 X좌표가 Px보다 크거나 같은 철광석이 있는 Y좌표에는 +1, 구리 광석이 있는 좌표에는 -1을 준 다음, 접두사 합이 최대가 되는 지점이 바로 Px의 Y좌표가 된다
    (증명은 귀류법으로 간단히 할 수 있다).
    """

    제가 이 부분을 하루 정도 고민을 해보고, 테스트를 통해 결과가 최적의 y좌표가 되는 것은 확인을 해보았는데,
    그 이유가 잘 이해되지 않아 귀류법으로 어떻게 증명이 되는지 부탁을 드리려고 댓글을 작성하게 됐습니다.

    여러가지 일로 바쁘실텐데, 답변을 해주지 않으셔도 이해합니다.
    감사합니다

    • kcy1019 2017.07.20 18:23 신고

      안녕하세요, 제가 귀찮음에 글을 부실하게 적어두었네요ㅠㅠ 쓸 당시에 생각해둔 증명은 뭐 엄밀한건 전혀 아니고 직관적이고 단순한 증명으로, 이에 대한 설명은 대부분 알고리즘의 X좌표에 대한 설명과 비슷합니다:

      1. 우선 Py = 0 인 상태에서는 Px 왼쪽의 철광석과 Py 오른쪽의 구리만이 유효하게 카운트됩니다(이 값이 위의 base, 그러니까 LEFT_IRON, RIGHT_COPPER 입니다).

      2. 여기서 이제 Py가 한 칸(즉 가장 가까운 광석의 바로 위로) 올라가면 해당 광석이 Px보다 왼쪽인지 오른쪽인지에 따라, 그리고 광석의 종류가 철광석인지 구리인지에 따라 유효한 광석의 수가 Py = 0일 때 보다 +1이 될 수도 있고, -1이 될 수도 있습니다. 즉 세그먼트 트리에 들어가는 값은 "Py가 이 광석 바로 위일 때 현재 유효한 광석의 수가 변하는 정도" 입니다.

      3. 정리하면, 이 알고리즘은 각 Px에 대해 Py = 0 일 때의 답에서 시작해서 어떤 Py ≠ 0 (정확히는 Py > 0)인 경우의 답들 중 최댓값이 무엇인지 살펴보는 알고리즘 입니다. 즉 Px 가 고정되었을 때 (Py = k일 때의 답) = (Py = 0일 때의 답) + (Py = k일 때 답의 변화량) 과 같은 식으로 계산하는 것이죠.

      4. 이제 증명 비슷한걸 해 봅시다. 최대 접두사 합을 갖는 Y를 OptY라고 하면, 귀류법으로 답이 OptY가 아닌 어떤 Py이고, 그때의 접두사 합이 최댓값이 아니라고 가정할 경우 다음과 같이 살펴볼 수 있습니다.

      우선 Px가 고정되어 있으므로 (Py = 0일 때의 답)은 변하지 않습니다.
      4a. Py < OptY: Py를 OptY까지 올리면 (변화량) 부분이 최소 1 증가합니다.
      4b. Py > OptY: Py를 OptY까지 내리면 (변화량) 부분이 최소 1 증가합니다.
      따라서 Py가 최적의 Y라는 것은 모순이 되어 최적의 Y는 OptY임을 증명할 수 있습니다.

      여담이지만 지금 보니 굳이 귀류법으로 해야 할 필요는 없던 거였네요ㅋㅋㅋ 역시 글로 써 봐야 더 정확해지나 봐요..

      질문 감사합니다!

  4. leejk9592@naver.com 2017.07.22 04:34 신고

    답변 해주셔서 정말로 감사드립니다

분명 난 나름 심한 저체중 + 시력이 안좋은데도 신검 4급 조건이 딱 내가 신검을 받을 때부터 강화되어 3급을 받고, 대학에 진학해서 산업기능요원으로 복무하려고 했더니 법이 저격당해서 못하고, 그래서 대학원에 왔더니 또 다시 전문연구요원을 없앤다고 한다. 퍄퍄...

유예기간? 헬조선에는 그딴거 없습니다. 오히려 높으신 분들의 손짓에 따라 어떤 법이든 즉각즉각 변하는게 바로 매력이죠!

캬.. 이맛헬..

뭐 그래도, 의미없는 몸부림이라도 쳐봐야지.. 하고 민원은 넣어뒀다.

신고

'Random' 카테고리의 다른 글

イロドリ - ClariS  (1) 2017.06.14
사실상 헬조선에 태어난게 중죄  (3) 2016.05.18
졸업  (2) 2016.02.16
블로그 꾸미기  (0) 2016.01.16
SW마에스트로 과정 6기 1단계 후기  (2) 2016.01.04
GMail 전달 기능에 대한 불평  (0) 2015.11.03
  1. 형님형님 2016.05.19 12:53 신고

    캬 헬조선 클라스

  2. cujun 2016.06.15 23:30 신고

    님아 blog글 많이올려주세여

    • kcy1019 2016.06.18 21:23 신고

      제가 게을러서.. 방학엔 뭔가 재밌는걸 써보도록 노력하겠습니다 ㅜ.ㅜ

Lua를 연습해볼 겸 이전에 PacMan에 사용했던 유전 프로그래밍을 약간 변형해서 적용해봤다. 너무 단순한 방법이라 그런가 성능이 좋은 편은 아니지만, Lua의 coroutine을 연습해보는 정도로 만족. 애초에 더 좋은 알고리즘을 만들려면 이전 상태를 고려하고 탄막의 속도를 계산할 줄 아는 알고리즘을 생각해야겠지(일단 지금 드는 생각은, 사람이 직접 이런 feature를 만드는건 귀찮고 재미도 없을 것 같으니 (귀찮아서 안 할듯 하지만)만약 시도한다면 NEAT나 변형된 Deep Q-Learning을 구현할 생각).

GitHub Link: https://github.com/kcy1019/strikersii_ai (forked from https://github.com/aikorea/strikersii_ai)


신고
  1. Bae0231 2016.03.29 10:28 신고

    제가 하는거 보다 낫네요! 멋있어요

  2. agaga 2016.05.12 01:51 신고

    오! 굳. 잘 만들었네요 요즘 루아 쓰시는군요