제6회 SMUPC Open Contest

• 명찰 색 고르기
• 독서실 자리 배정
• 가위바위보 계단 오르기
• 입소문의 힘
• 마감일 정하기
• 최후의 백업
• 이전 수

- 총 7문제였고 웰노운 셋이었다. 최후의 백업 문제를 못풀어서 6솔로 끝난는데 틀린 이유를 모르겠다. 뭐가 틀렸을까? (나중에 확인해보니 스페셜 저지가 설정되지 않아서 그랬다. 정상화되니까 AC 받았다)

- 맞힌 문제당 평균 11분 정도 걸렸는데 7분 정도로 단축이 필요하다. 구현 속도가 느린 건 어쩔 수 없으니 미리 템플릿이나 만들어두고 사고 과정을 분명히 하자

명찰 색 고르기

• 문제 출처: 정올 26273번

- 각 자릿수의 합을 $3$으로 나눈 나머지를 구하는 게 메인

def solution():
    N = int(input())
    answers = [0, 0, 0]
    for _ in range(N):
        x = list(input().rstrip())
        s = sum(map(int, x))
        answers[s % 3] += 1
    print(*answers)


solution()

- 예상 티어: 브론즈 $2$

독서실 자리 배정

• 문제 출처: 정올 25504번

- 동시간에 겹치는 예악의 최대 개수만큼 자리가 필요하다

- $S$가 증가하는 순으로 예약을 순회하자. 그럼 시작 시각은 무조건 증가하여 포함 관계이니 마감 시각만 고려하면 된다

- 새로운 $i$번째 예약을 고려할 때 $S_i$보다 작은 마감 시각은 안 겹치니 필요 없다. 따라서 마감 시각들을 최소 힙으로 관리하면 $O(N\log N)$에 문제를 해결할 수 있다

import heapq


def solution():
    N = int(input())
    array = [list(map(int, input().split())) for _ in range(N)]
    pq = []
    answer = 0
    for s, e in array:
        while pq and pq[0] <= s:
            heapq.heappop(pq)
        heapq.heappush(pq, e)
        answer = max(len(pq), answer)
    print(answer)


solution()

- 예상 티어: 실버 $1$

가위바위보 계단 오르기

• 문제 출처: 정올 26278번

- 현재 몇 번째 계단에 있는지와 사용한 손의 상태에 따른 가짓수를 비트마스크 DP로 계산하자

- 전체 알고리즘의 시간 복잡도는 $O\left(3 \times 2^3 \times N\right)$이다

def solution():
    mod = 10**9 + 7
    N = int(input())
    dp = [[0] * 8 for _ in range(N + 3)]
    dp[0][0] = 1
    for i in range(N):
        for mask in range(8):
            for j in range(3):
                k = i + j + 1
                b = mask | (1 << j)
                dp[k][b] += dp[i][mask]
                dp[k][b] %= mod
    answer = dp[N][7]
    print(answer)


solution()

- 사실 비트마스크를 쓸 필요는 없고 그냥 배열로 관리해도 된다. 단지 고려할 상태가 많아서 귀찮을 뿐

- 예상 티어: 골드 $5$

입소문의 힘

• 문제 출처: 정올 26276번

- 매개변수 탐색 + 도달 가능성 DFS로 확인하기

- 총 $O((N + M) \log W)$

def binary_search(graph, source, sink):
    low, high = 0, 10**9
    while low <= high:
        mid = (low + high) // 2
        is_possible = dfs(graph, source, sink, mid)
        if is_possible:
            low = mid + 1
        else:
            high = mid - 1
    return high


def dfs(graph, source, sink, k):
    n = len(graph)
    visited = [False] * n
    stack = [source]
    while stack:
        u = stack.pop()
        for v, w in graph[u]:
            if visited[v] or w < k:
                continue
            visited[v] = True
            if v == sink:
                return True
            stack.append(v)
    return False


def solution():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        A, B, W = map(int, input().split())
        graph[A].append((B, W))
        graph[B].append((A, W))
    S, E = map(int, input().split())
    answer = binary_search(graph, S, E)
    print(answer)


solution()

- 예상 티어: 골드 $5$

마감일 정하기

• 문제 출처: 정올 25505번

- 시작일은 $1$일로 동일하다. 마감일을 기준으로 큰 것부터 고려하자. 역순으로 고려하기에 이들은 마감되지 않으며 점수를 가장 많이 주는 과제를 해결해 나가면 된다

- $\max(D)$부터 $1$까지 순회하며 마감일이 이와 동일한 과제들의 점수를 우선순위 큐에 삽입하자. 그리고 최대 점수를 $O(\log N)$에 고르면 된다

import heapq


def solution():
    N = int(input())
    array = [list(map(int, input().split())) for _ in range(N)]
    array.sort()
    total = 0
    pq = []
    for deadline in range(array[-1][0], 0, -1):
        while array and array[-1][0] == deadline:
            _, s = array.pop()
            heapq.heappush(pq, -s)
        if pq:
            mx = -1 * heapq.heappop(pq)
            total += mx
    print(total)


solution()

- 순서만 반대로 했을 뿐인데 살짝 뇌정지가 왔다

- 예상 티어: 골드 $2$

최후의 백업

• 문제 출처: 정올 26279번

- 나이브하게 풀면 $O(NM\log M)$으로 시간 초과

- 효율적으로 다익 돌리면 $O(N + M\log M)$이다. 근데 왜 틀렸는지 모르겠다 $\to$ 스페셜 저지 이슈로 정상화된 후 AC 받았음

import heapq


def dijkstra(graph, source):
    inf = float("inf")
    n = len(graph)
    distances = [inf] * n
    distances[source] = 0
    predecessors = [None] * n 
    pq = [(0, source)]
    while pq:
        d_u, u = heapq.heappop(pq)
        if distances[u] < d_u:
            continue
        for v, w in graph[u]:
            if distances[v] <= d_u + w:
                continue
            distances[v] = d_u + w
            predecessors[v] = u
            heapq.heappush(pq, (distances[v], v))
    return distances, predecessors


def track(predecessors, source, sink):
    route = []
    node = sink
    while predecessors[node] is not None:
        route.append(node)
        node = predecessors[node]
    route.append(source)
    route.reverse()
    return route


def solution():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        graph[A].append((B, C))
        graph[B].append((A, C))
    S1, S2, S3 = map(int, input().split())
    d1, p1 = dijkstra(graph, S1)
    d2, p2 = dijkstra(graph, S2)
    d3, p3 = dijkstra(graph, S3)
    d_min, sink = min((d1[s] + d2[s] + d3[s], s) for s in range(1, N + 1))
    s1_track = track(p1, S1, sink)
    s2_track = track(p2, S2, sink)
    s3_track = track(p3, S3, sink)
    print(d_min)
    print(sink)
    print(len(s1_track))
    print(*s1_track)
    print(len(s2_track))
    print(*s2_track)
    print(len(s3_track))
    print(*s3_track)


solution()

- 예상 티어: 골드 $3$

이전 수

• 문제 출처: 정올 26280번

- 세그먼트 트리를 쓰면 $x$의 랭크와 $k$번째 원소를 $O(\log N)$에 알 수 있다

- 근데 키가 같으면 기존 인덱스가 작은 게 더 앞서기에 동일한 키를 가진 사람들의 인덱스를 배열로 관리하자 (순차 탐색을 하므로 인덱스는 무조건 증가하니 배열을 쓸 수 있다, $O(1)$에 처리 가능)

- $h$보다 작은 사람이 $r$명 있을 때 $r \le M$이면 $M$번째 사람의 키를 구하자. $x$라면 $x$의 랭크 $rx$를 구한 뒤 키가 $x$인 사람 중 $M - rx$번째 사람의 인덱스를 단순 배열 인덱싱으로 구하면 된다. 그 후 트리를 갱신하자

- 총 $O(N \log N)$이다

class OrderStatisticTree:
    _root = 1

    def __init__(self, max_value_or_counts):
        is_int = isinstance(max_value_or_counts, int)
        n = max_value_or_counts + 1 if is_int else len(max_value_or_counts)
        self._size = 1 << n.bit_length()
        self._tree = [0] * (self._size << 1)
        if not is_int:
            self._build(max_value_or_counts)

    def _build(self, array):
        for i, a in enumerate(array, start=self._size):
            self._tree[i] = a
        for i in range(self._size - 1, 0, -1):
            self._tree[i] = self._tree[i << 1] + self._tree[i << 1 | 1]

    @property
    def size(self):
        return self._tree[self._root]

    def count(self, x):
        return self._tree[x + self._size]

    def add(self, x, delta):
        i = x + self._size
        while i:
            self._tree[i] += delta
            i >>= 1

    def find_kth(self, k):
        i = 1
        while i < self._size:
            i <<= 1
            if self._tree[i] < k:
                k -= self._tree[i]
                i |= 1
        return i - self._size

    def bisect_right(self, x):
        i = x + self._size
        f_x = 0
        while i:
            if ~i & 1:
                f_x += self._tree[i]
                i -= 1
            i >>= 1
        return f_x


def solution():
    N, M = map(int, input().split())
    array = list(map(int, input().split()))
    tree = OrderStatisticTree(10**5)
    h2indices = [[] for _ in range(10**5 + 1)]
    ranks = [0] * N
    mth_indices = [0] * N
    for i, h in enumerate(array):
        r = tree.bisect_right(h - 1)
        ranks[i] = r
        if r >= M:
            x = tree.find_kth(M)
            rx = tree.bisect_right(x - 1)
            j = h2indices[x][M - rx - 1]
            mth_indices[i] = j
        h2indices[h].append(i + 1)
        tree.add(h, 1)
    print(*ranks)
    print(*mth_indices)


solution()

- 세그먼트 트리 구현체: https://github.com/Jaesu26/python-cp-templates/blob/main/src/segment-tree.py

- 예상 티어: 플래티넘 $4$