사격

• M번의 사격 후에 A점 이상이 될수 있기 위해, M-1번의 사격 후에 필요한 (점수, 사격실력) 의 범위를 어떻게 구할수 있을것 같고, 이것으로 부터 다시 M-2번, M-3번 … 후에 필요한 범위를 구할수 있을것 같긴 하다. 영역이 대충 볼록하게 나올테니, 어떻게 잘 하면 될 수고 있을 것 같긴 하지만 복잡할것 같은 생각이 든다.
• 바로 답을 구하는 것이 쉽지 않을것 같으니, 다른 방법을 생각하자. 1) 초기 사격 실력이 주어졌을때, 성공 여부는 시뮬레이션을 통해서 쉽게 구할수 있다. 2) 초기 사격 실력이 증가하면, 총합도 같거나 증가한다. ⇒ 이 두가지가 성립하니 파라메트릭 서치로 해결하면 된다
• 초기사격 실력이 주어졌을때 얻게되는 점수 총합을 구하는 것은 그냥 M번 사격하는 시뮬레이션을 돌리면 된다. 이전 사격에서 스킬이 증가했을때 다음 사격에서 얻을 수 있는 최대 점수를 찾는 것은, 단순하게 그냥 이분탐색을 써서 찾아도 가능하다. 한번의 시뮬레이션을 돌리는데에 O(MlogN)이 걸리지만 통과되는 데에는 별 지장이 없다 (공식 해설에서 설명한 방법). 하지만 스킬이 계속 증가한다는 것을 이용하면 표적들을 그냥 한번 스캔하면서 구해도 된다. 이러면 시뮬레이션 한번 돌리는데에 amortized O(M+N)이 걸리고, 더 빨리 동작한다. 어느 방식을 쓰나 전처리 단계에서 표적들을 정렬하는 것을 필요하다
• 파라메트릭 서치를 돌릴때의 범위는 [min(s), max(s)] 로 잡으면 된다. 초기 실력이 min(s)보다 작으면 최종점수는 0점이니 언제나 실패하고, 초기 실력이 max(s) 보다 커지더라도 최종 점수는 max(s)일때보다 더 커지지 않는다.
• 전체 시간복잡도는 O(NlogN + (M+N)logS)

"""Solution code for "BOJ 31264. 사격".

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

Tags: [binary search]
"""


import functools
from teflib import binsearch

INF = float('inf')


def is_valid(skill, m, s, a):
    tot_score = 0
    s_iter = iter(s)
    cur_score, next_score = 0, next(s_iter)
    for _ in range(m):
        while next_score <= skill:
            cur_score, next_score = next_score, next(s_iter, INF)
        tot_score += cur_score
        if tot_score >= a:
            return True
        skill += cur_score
    return False


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

    s.sort()
    print(
        binsearch.minimum_valid_integer(
            s[0], s[-1] + 1, functools.partial(is_valid, m=M, s=s, a=A)
        )
    )


if __name__ == '__main__':
    main()

• Dependency: teflib.binsearch.minimum_valid_integer