군수품 창고 정리

• 이 문제처럼 뭔가 아이템들을 고르게(최댓값을 최소로) 분배하는 방법을 찾는 유형은 이분탐색으로 풀리는 경우가 매우 많다.
• 그 이유는, 최댓값을 제한한채로 아이템을 나누것이 가능한지 아닌지를 확인하는것이 보통 간단하게 되기 때문이다. 최대한 최댓값에 가깝게 분배하도록 시뮬레이션을 해보는 방식으로 확인해보면 된다.
• 이 문제도 마찬가지로, 이분탐색을 사용한다. 아이템을 각 분대에 {분대의 병사수 * 최댓값} 이하의 범위에서 최대한 많이 나눠줄수 있도록 묶어서 나눠줘보고, 그래서 모든 아이템을 다 나눠줄수 있는지 확인하면 된다.
• 하지만 신경쓸 점이 몇가지 있다
• 한가지는 아이템들을 앞에서부터 묶어서 분대 개수만큼의 묶음을 만들었을때, 각각을 분대들에 매핑시키는 방법을 또 고려해야 한다. 다행히도 분대 개수 M이 최대 7개로 작기때문에, 그냥 무식하게 M!의 모든 순서에 대해서 아이템들을 나누는게 가능한지 확인해서, 한개의 순서라도 가능한 순서가 있다면 가능한것으로 처리하는 것이다.
• 두번째는, 분대들의 순서와 최댓값까지가 정해졌을때, 아이템을 나눠주는 시뮬레이션을 O(n)에 처리하는 것은 너무 느리다는 것이다. 이렇게 하면 결정문제 한번을 푸는데에 O(n*m!)이 되는데 이것은 너무 크다. 아이템을 나눠줄때 {분대의 병사수 * 최댓값} 이하의 범위에서 최대한 많이 나누는 값을 찾는 것에 다시 이진탐색을 사용하는 방법이 있다. 먼저 아이템들의 누적합 배열을 만들어놓고, 여기에 이진탐색을 M번 적용하는 식으로 처리한다면, 나눠주는 시뮬레이션을 O(m*logn)에 처리할수 있고, 모든 순서에 대해서 처리하면 O(m!*m*logn)이 된다.
• 답의 범위를 1~{아이템의 총합} 으로 놓으면, 결정 문제를 O(log(a*n))번 풀어야 한다 (a=박스 한개에 들어갈수 있는 아이템의 최대개수). 총 시간복잡도는 O(m!*m*logn*log(a*n))이 된다

"""Solution code for "BOJ 31412. 군수품 창고 정리".

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

Tags: [binary search]
"""

import bisect
import functools
import itertools
from teflib import binsearch


def is_vaild(limit, psum, b):
    for b_perm in itertools.permutations(b):
        prev = 0
        for b_i in b_perm:
            pos = bisect.bisect_right(psum, prev + b_i * limit)
            if pos == len(psum):
                return True
            prev = psum[pos - 1]
    return False


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

    psum = [v := 0] + [v := v + x for x in a]
    is_valid_func = functools.partial(is_vaild, psum=psum, b=b)
    answer = binsearch.minimum_valid_integer(1, sum(a) + 1, is_valid_func)

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.binsearch.minimum_valid_integer