結果

問題 No.206 数の積集合を求めるクエリ
ユーザー mkawa2mkawa2
提出日時 2020-01-28 11:11:26
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,467 bytes
コンパイル時間 90 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 96,052 KB
最終ジャッジ日時 2024-09-15 08:17:46
合計ジャッジ時間 21,367 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

import numpy as np

def main():
    # aa=[3,4,6]とbb=[1,2,5,7]とする
    # aaに要素iが存在すればa[i]に1を立てる
    # a=[0,0,0,1,1,0,1] b=[0,1,1,0,0,1,0,1]
    # これにFFTをかけると「和(i+j)がある数になる組合せの個数」が分かる
    # しかし今回欲しいのは「差(i-j)がある数になる組合せの個数」
    # そのためにbを反転してb[j]をb[n-j]にする
    # すると「i-j+nがある数になる組合せの個数」が分かる
    # bbの要素jにvを足したときaaの要素iと等しくなるのはi=j+vのとき
    # すなわちi-j=vのとき
    # よってi-j+n=v+nなので、i-j+nがv+nになるときの個数を答えればよい
    def bitarr(aa):
        res = np.zeros(n+1,'i8')
        for a in aa: res[a] = 1
        return res

    l, m, n = MI()
    aa = LI()
    bb = LI()
    q = II()
    a = bitarr(aa)
    b = bitarr(bb)
    b = b[::-1]
    s=(n+1)*2
    cc = (np.fft.irfft(np.fft.rfft(a, s) * np.fft.rfft(b, s)) + 0.5).astype(np.int)
    for i in range(n,n+q):
        print(cc[i])

main()
0