과부화 방지

• 멀티탭은 소켓이 많은것부터 사용하는 것이 유리하다. 전자기기는 D값이 큰것들을 나중에 꼽는것이 유리하긴 할텐데, 그렇다고 d값이 작은것부터 꼽는 것은 당연히 최적이 아니라서 바로 풀리지는 않는다.
• 대신 결정문제로 바꿔서 이분탐색으로 접근하자. K개의 전자기기를 꼽을수 있는지 없는지를 확인하는 문제라면, D값이 큰것부터 K개를 골라서 꼽을수 있는지를 보면 된다. D값이 큰것부터 K개를 골랐다면, 그 K개중에서는 그리디하게 가장 D값이 작은것부터 꼽아나가면서 연결이 가능한지 불가능한지를 확인하면 된다.
• 현재 남은 기기중에서 D값이 가장 작은것이 d1 이라면, 길이가 d1이 될때까지 멀티탭들을 소켓이 많은것부터 연결한다. 이렇게해서 길이가 d1인 빈 소켓들이 준비되면, 여기에 D값이 d1인 기기들을 모두 꼽는다. 이때 소켓이 기기보다 부족하면 꼽는것이 불가능한 것이다. 기기들을 꼽고 남은 소켓들에 다시 멀티탭들을 길이가 d2가 될때까지 연결하고, D값이 d2인 기기들을 꼽고 하는 것을 반복해서 전부 꼽을수 있는지를 확인하면 된다.
• 이렇게 결정 문제 하나를 푸는데에는 O(K+N) = O(M+N) 이 걸린다. 이것을 logM번 해줘야 하므로 총 시간복잡도는 O((N+M)logM) 이 된다
• 결정문제를 풀때, 남은 빈 소켓 갯수만큼 멀티탭을 연결한 뒤에 바뀌는 빈 소켓의 갯수를 세는것은, 멀티탭을 하나씩 더해주는 대신 누적합을 이용하는 식으로 조금 최적화할수 있다. 시간복잡도는 O(M+N)에서 O(M+min(N,D))로 바뀌는 수준이라 최악 경우에는 별 차이가 없지만, 실제 실행시간은 많이 빨라졌다.

"""Solution code for "BOJ 31396. 과부하 방지".

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

Tags: [greedy] [binary search]
"""

import functools
from teflib import binsearch


def is_valid(device_count, strip_psum, devices, init_socket_count):
    tot_strip_count = len(strip_psum) - 1
    used_strip_count = 0
    socket_count = init_socket_count
    max_strip_len = 0
    for d_i in devices[-device_count:]:
        while used_strip_count < tot_strip_count and max_strip_len < d_i:
            max_strip_len += 1
            newly_used_strip = min(
                socket_count, tot_strip_count - used_strip_count
            )
            socket_count += (
                strip_psum[used_strip_count + newly_used_strip]
                - strip_psum[used_strip_count]
                - newly_used_strip
            )
            used_strip_count += newly_used_strip
        if socket_count == 0:
            return False
        socket_count -= 1
    return True


def main():
    # pylint: disable=unused-variable
    N, K, M = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    D = [int(x) for x in input().split()]

    is_valid_func = functools.partial(
        is_valid,
        strip_psum=[v := 0] + [v := v + x for x in sorted(A, reverse=True)],
        devices=sorted(D),
        init_socket_count=K,
    )
    print(binsearch.maximum_valid_integer(1, M + 1, is_valid_func))


if __name__ == '__main__':
    main()

• Dependency: teflib.binsearch.maximum_valid_integer