結果
問題 | No.398 ハーフパイプ(2) |
ユーザー |
![]() |
提出日時 | 2023-11-02 18:30:26 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,297 ms / 2,000 ms |
コード長 | 1,174 bytes |
コンパイル時間 | 131 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 79,360 KB |
最終ジャッジ日時 | 2024-09-25 18:16:19 |
合計ジャッジ時間 | 24,256 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
import numpy as np def convolve(f, g): 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] a, b = input().split(".") X = int(a + b)//25 M = 100 S = set() ans = int(X % 4 == 0) memo = [[0] * (M + 1) for i in range(M + 1)] for a in range(M + 1): for b in range(a, M + 1): dp = [0] * (M + 1) for i in range(a, b + 1): dp[i] = 1 temp2 = convolve(dp, dp) temp4 = convolve(temp2, temp2) temp6 = convolve(temp4, temp2) memo[a][b] = temp6 S.add((a,b)) for a in range(M + 1): for b in range(a + 1, M + 1): if X + a + b >= 6 * b: continue if X + a + b <= 6 * a: continue ans += memo[a][b][X + a + b] if (a,b-1) in S: ans -= memo[a][b-1][X + a + b] if (a+1,b) in S: ans -= memo[a+1][b][X + a + b] if (a+1,b-1) in S: ans += memo[a+1][b-1][X + a + b] print(ans)