結果
問題 | No.206 数の積集合を求めるクエリ |
ユーザー | ygd. |
提出日時 | 2022-03-05 16:27:25 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 351 ms / 7,000 ms |
コード長 | 2,090 bytes |
コンパイル時間 | 114 ms |
コンパイル使用メモリ | 10,748 KB |
実行使用メモリ | 61,592 KB |
最終ジャッジ日時 | 2023-09-27 03:56:24 |
合計ジャッジ時間 | 11,897 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 181 ms
50,328 KB |
testcase_01 | AC | 181 ms
49,192 KB |
testcase_02 | AC | 179 ms
50,048 KB |
testcase_03 | AC | 180 ms
50,476 KB |
testcase_04 | AC | 183 ms
49,572 KB |
testcase_05 | AC | 183 ms
49,472 KB |
testcase_06 | AC | 184 ms
49,916 KB |
testcase_07 | AC | 184 ms
49,324 KB |
testcase_08 | AC | 182 ms
49,984 KB |
testcase_09 | AC | 182 ms
50,112 KB |
testcase_10 | AC | 184 ms
50,636 KB |
testcase_11 | AC | 181 ms
49,900 KB |
testcase_12 | AC | 186 ms
49,520 KB |
testcase_13 | AC | 180 ms
50,612 KB |
testcase_14 | AC | 187 ms
49,632 KB |
testcase_15 | AC | 186 ms
49,540 KB |
testcase_16 | AC | 186 ms
50,108 KB |
testcase_17 | AC | 237 ms
59,664 KB |
testcase_18 | AC | 210 ms
56,216 KB |
testcase_19 | AC | 229 ms
61,508 KB |
testcase_20 | AC | 210 ms
55,784 KB |
testcase_21 | AC | 215 ms
57,408 KB |
testcase_22 | AC | 210 ms
57,888 KB |
testcase_23 | AC | 227 ms
61,592 KB |
testcase_24 | AC | 351 ms
60,468 KB |
testcase_25 | AC | 342 ms
59,976 KB |
testcase_26 | AC | 326 ms
55,784 KB |
testcase_27 | AC | 287 ms
54,856 KB |
testcase_28 | AC | 325 ms
57,632 KB |
testcase_29 | AC | 325 ms
57,160 KB |
testcase_30 | AC | 318 ms
54,888 KB |
ソースコード
import sys #input = sys.stdin.readline input = sys.stdin.buffer.readline #文字列はダメ #sys.setrecursionlimit(1000000) #import bisect #import itertools #import random #from heapq import heapify, heappop, heappush #from collections import defaultdict #from collections import deque #import copy #import math #from functools import lru_cache #@lru_cache(maxsize=None) #MOD = pow(10,9) + 7 #MOD = 998244353 #dx = [1,0,-1,0] #dy = [0,1,0,-1] import numpy as np def convolve(f, g): """多項式 f, g の積を計算する。 Parameters ---------- f : np.ndarray (int64) f[i] に、x^i の係数が入っている g : np.ndarray (int64) g[i] に、x^i の係数が入っている Returns ------- h : np.ndarray f,g の積 """ # h の長さ以上の n=2^k を計算 fft_len = 1 while 2 * fft_len < len(f) + len(g) - 1: fft_len *= 2 fft_len *= 2 # フーリエ変換 Ff = np.fft.rfft(f, fft_len) Fg = np.fft.rfft(g, fft_len) # 各点積 Fh = Ff * Fg # フーリエ逆変換 h = np.fft.irfft(Fh, fft_len) # 小数になっているので、整数にまるめる h = np.rint(h).astype(np.int64) return h[:len(f) + len(g) - 1] def main(): L,M,N = map(int,input().split()) A = list(map(int,input().split())) B = list(map(int,input().split())) Q = int(input()) MAX = pow(10,5) + 10 #AX[i]:0/1 iとなる値がAに入っているか否か AX = [0]*MAX BX = [0]*MAX for a in A: AX[a] = 1 for b in B: BX[b] = 1 BXR = list(reversed(BX)) #print(AX) #print(BXR) #BXにqを足してAXと同じになるものが欲しい。、 #AX[i] * BX[i-q]の係数が欲しいもの。 #Bを反転させるとBXR[N-1-i+q]となる。 #iとi+qの関係が、iとN-1+q-iとなるので、和がN-1+qのところを見ればよい。 D = convolve(AX,BXR) #print(D) for v in range(Q): ans = D[MAX-1+v] print(ans) if __name__ == '__main__': main()