테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 백설공주와 난쟁이 ======

===== 풀이 =====
  * 구간에서 과반수를 차지하는 값이 있는지를 찾는 문제이다. 솔루션은 여러가지가 가능하다.
  * 우선, 어떤 값이 구간 내에 몇개나 존재하는지는 O(logn)에 구할 수 있다
    * 각 값마다, 그 값이 배열에서 등장한 인덱스들을 모아서 정렬된 리스트로 만들어둔다. 그 값이 [l,r] 범위에서 얼마나 존재하는 지는, 인덱스 배열에서 l과 r을 이진검색해준 다음에 그 차를 구하면 계산 가능하다.
  * 그러면 이제 구간에서 과반수를 차지할 가능성이 있는 값을 뽑아서, 그 값이 정말 과반수인지 확인하는 것으로 문제를 풀 수 있다. 후자는 위에 말한대로 O(logn)에 가능하니, 과반수를 차지할 가능성이 있는 값을 뽑는 것이 문제이다.
  * 구간의 최빈값은 과반수가 될 수 있는 유일한 후보이다. 그러나, [[ps:구간 쿼리#구간 최빈값 쿼리]]는 링크에서 설명했듯 빠르게 구하는 것이 어렵다. 그래서 패스
  * 구간의 중간값 역시 과반수가 될 수 있는 유일한 후보이다. [[ps:구간 쿼리#구간 Rank 쿼리]]에서 설명한 방식을 사용하면, 머지소트트리를 활용해서 O(log^2(n))에 구할 수 있다.
  * 세그먼트 트리를 이용해서 구간을 나눈다고 생각해보자. 전체 구간에서 과반수를 차지하는 값이 있다면, 나눠진 구간들중 적어도 한 구간에서는 과반수여야 한다. 따라서 세그먼트 트리의 각각의 구간에 대해서 미리 최빈값이나 중간값을 계산해두면, 임의의 구간에 대해서 나눠진 구간 갯수(=O(logn))개의 과반수 후보를 찾을 수 있다. O(logn)개의 후보에 대해서 O(logn)의 바이너리서치를 시행하므로 이것도 전체 복잡도는 O(log^2(n))이 된다.
  * 쉽지 않은 발상이지만, 그냥 과반수 후보를 구간내에서 랜덤하게 추출한 값으로 해서 테스트하는 방법도 있다. 정말 과반수를 갖는 값이 있다면, 랜덤하게 값을 하나 뽑았을때 과반수 값일 확률이 50% 이상이고, x개의 값을 뽑는다면 그중에 한개 이상이 과반수 값일 확률이 1-(1-0.5)^x 보다 크다. x를 50개쯤 뽑으면 거의 1에 수렴하므로 정답을 맞는데에 지장이 없다. 이렇게 할 경우 k개의 값을 뽑는다면 O(klogn)에 해결 가능하다
  * 랜덤 방식으로(K=50) 풀었을때 1288ms로 통과되었고, 구간의 중간값을 구해서 풀었을때에는 1884ms로 통과되었다. 다른 방법은 시도 안해봄.


===== 코드 =====

==== 코드 1 - 랜덤에 기반한 방법 ====
<dkpr py>
"""Solution code for "BOJ 2912. 백설공주와 난쟁이".

- Problem link: https://www.acmicpc.net/problem/2912
- Solution link: http://www.teferi.net/ps/problems/boj/2912
"""

import bisect
import random
import sys

REPEAT_COUNT = 50


def main():
    N, C = [int(x) for x in sys.stdin.readline().split()]
    colors = [int(x) for x in sys.stdin.readline().split()]
    indexes = [[] for _ in range(C)]
    for i, color in enumerate(colors):
        indexes[color - 1].append(i)
    M = int(sys.stdin.readline())
    for _ in range(M):
        A, B = [int(x) for x in sys.stdin.readline().split()]
        for _ in range(REPEAT_COUNT):
            cand = colors[random.randrange(A - 1, B)]
            cand_indexes = indexes[cand - 1]
            count = (bisect.bisect_left(cand_indexes, B) 
                     - bisect.bisect_left(cand_indexes, A - 1))
            if count > (B - A + 1) // 2:
                print('yes', cand)
                break
        else:
            print('no')


if __name__ == '__main__':
    main()
</dkpr>

==== 코드 2 - 구간 중간값을 이용한 방법 ====
<dkpr py>
"""Solution code for "BOJ 2912. 백설공주와 난쟁이".

- Problem link: https://www.acmicpc.net/problem/2912
- Solution link: http://www.teferi.net/ps/problems/boj/2912
"""

import bisect
import operator
import sys


class MergeSortTreeForKthElem:
    def __init__(self, values):
        l = [[i] for i, value
             in sorted(enumerate(values), key=operator.itemgetter(1))]
        self._values = values
        self._size = 1 << (len(l) - 1).bit_length()
        self._tree = ([[] for _ in range(self._size)]
                      + l + [[]] * (self._size - len(l)))
        for i in range(self._size - 1, 0, -1):
            self._tree[i] = self._tree[i * 2] + self._tree[i * 2 + 1]
            self._tree[i].sort()

    def kth(self, beg: int, end: int, k: int) -> int:
        i = 1
        while i < self._size:
            i += i
            node = self._tree[i]
            t = bisect.bisect_left(node, end) - bisect.bisect_left(node, beg)
            if t < k:
                k -= t
                i += 1
        return self._values[self._tree[i][0]]


def main():
    N, C = [int(x) for x in sys.stdin.readline().split()]
    colors = [int(x) for x in sys.stdin.readline().split()]
    indexes = [[] for _ in range(C)]
    for i, color in enumerate(colors):
        indexes[color - 1].append(i)
    mst = MergeSortTreeForKthElem(colors)
    M = int(sys.stdin.readline())
    for _ in range(M):
        A, B = [int(x) for x in sys.stdin.readline().split()]
        median = mst.kth(A - 1, B, (B - A) // 2 + 1)
        ind = indexes[median - 1]
        count = bisect.bisect_left(ind, B) - bisect.bisect_left(ind, A - 1)
        if count > (B - A + 1) // 2:
            print('yes', median)
        else:
            print('no')


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_3}}