사용자 도구

사이트 도구


ps:problems:boj:10531

Golf Bot

ps
링크https://www.acmicpc.net/problem/10531
출처BOJ
문제 번호10531
문제명Golf Bot
레벨플래티넘 2
분류

고속 푸리에 변환

시간복잡도O(N+M+klogk)
인풋사이즈N<=200,000, M<=200,000, k<=200,000
사용한 언어Python
제출기록66248KB / 724ms
최고기록724ms
해결날짜2021/02/13
태그

46단계

풀이

  • FFT를 이용해서 All possible sums를 찾는 전형적인 문제. 자세한 내용은 All possible sums 참고.
  • 두번에 갈 수 있는 지가 아니라, 두번 이내에 갈 수 있는 지를 구하는 것이라는 점에.
    • 가장 간단한 처리법은 골프 봇이 칠수 있는 거리에 0도 추가한 뒤, 두번에 갈 수 있는지를 체크하는 것이다.
  • 시간복잡도는 O(N+M+klogk). (k=max(d))
    • 실제 fft를 돌리는 데에 걸리는 시간은 배열의 길이인 N, M이 아닌, max(d)에 의해 결정된다는 점을 기억하자.

코드

"""Solution code for "BOJ 10531. Golf Bot".

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

import sys
from teflib import fft


def main():
    N = int(sys.stdin.readline())
    k = [int(sys.stdin.readline()) for _ in range(N)]
    M = int(sys.stdin.readline())
    d = [int(sys.stdin.readline()) for _ in range(M)]
    max_d = max(d)

    f = [1] + [0] * max_d
    for k_i in k:
        if k_i <= max_d:
            f[k_i] = 1
    f_square = fft.multiply(f, f)
    answer = sum(1 for d_i in d if f_square[d_i] > 0)
    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
J F T N᠎ Z
 
ps/problems/boj/10531.txt · 마지막으로 수정됨: 2021/05/05 16:33 저자 teferi