結果
問題 | No.2644 Iro Iro-Iro |
ユーザー | cho435 |
提出日時 | 2024-02-13 04:49:11 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 1,687 ms / 2,000 ms |
コード長 | 1,191 bytes |
コンパイル時間 | 136 ms |
コンパイル使用メモリ | 12,032 KB |
実行使用メモリ | 168,128 KB |
最終ジャッジ日時 | 2024-02-13 17:37:38 |
合計ジャッジ時間 | 42,846 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 760 ms
159,900 KB |
testcase_01 | AC | 722 ms
159,900 KB |
testcase_02 | AC | 755 ms
159,900 KB |
testcase_03 | AC | 794 ms
159,896 KB |
testcase_04 | AC | 846 ms
162,000 KB |
testcase_05 | AC | 844 ms
161,944 KB |
testcase_06 | AC | 754 ms
159,944 KB |
testcase_07 | AC | 853 ms
161,984 KB |
testcase_08 | AC | 826 ms
161,944 KB |
testcase_09 | AC | 757 ms
159,916 KB |
testcase_10 | AC | 785 ms
159,896 KB |
testcase_11 | AC | 797 ms
161,992 KB |
testcase_12 | AC | 759 ms
159,896 KB |
testcase_13 | AC | 1,507 ms
164,728 KB |
testcase_14 | AC | 1,490 ms
164,524 KB |
testcase_15 | AC | 1,497 ms
162,136 KB |
testcase_16 | AC | 1,480 ms
162,136 KB |
testcase_17 | AC | 1,540 ms
164,184 KB |
testcase_18 | AC | 1,553 ms
168,128 KB |
testcase_19 | AC | 1,533 ms
168,128 KB |
testcase_20 | AC | 1,535 ms
168,128 KB |
testcase_21 | AC | 1,541 ms
168,128 KB |
testcase_22 | AC | 1,574 ms
168,128 KB |
testcase_23 | AC | 1,561 ms
166,192 KB |
testcase_24 | AC | 1,575 ms
167,420 KB |
testcase_25 | AC | 1,632 ms
167,712 KB |
testcase_26 | AC | 1,674 ms
167,708 KB |
testcase_27 | AC | 1,549 ms
167,512 KB |
testcase_28 | AC | 762 ms
159,896 KB |
testcase_29 | AC | 1,687 ms
168,064 KB |
testcase_30 | AC | 1,345 ms
165,492 KB |
testcase_31 | AC | 1,332 ms
165,488 KB |
testcase_32 | AC | 1,467 ms
165,896 KB |
ソースコード
import numpy as np # https://maspypy.com/数学・numpy-高速フーリエ変換fftによる畳み込み 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] N, M = map(int,input().split()) Max_size = 101 ** 3 V = np.zeros(Max_size) W = [0] * M for i in range(N): a, b, c = map(int,input().split()) V[a + 101*b + 101*101*c] = 1 for i in range(M): x, y, z = map(int,input().split()) W[i] = x + 101*y + 101*101*z rV = V[::-1] res = convolve(V, rV) ans = N for i in range(M): ans = max(ans, N*2 - res[Max_size - 1 + W[i]]) print(ans)