結果
問題 |
No.910 素数部分列
|
ユーザー |
![]() |
提出日時 | 2025-06-12 16:34:47 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,068 bytes |
コンパイル時間 | 320 ms |
コンパイル使用メモリ | 82,496 KB |
実行使用メモリ | 79,292 KB |
最終ジャッジ日時 | 2025-06-12 16:34:58 |
合計ジャッジ時間 | 9,696 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 WA * 45 |
ソースコード
import sys import math def is_prime(n): if n < 2: return False for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]: if n % p == 0: return n == p d = n - 1 s = 0 while d % 2 == 0: d //= 2 s += 1 for a in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]: if a >= n: continue x = pow(a, d, n) if x == 1 or x == n - 1: continue for _ in range(s - 1): x = pow(x, 2, n) if x == n - 1: break else: return False return True def generate_primes(max_length): primes = set() digits = ['1', '3', '5', '7', '9'] for length in range(1, max_length + 1): for num_tuple in itertools.product(digits, repeat=length): num_str = ''.join(num_tuple) num = int(num_str) if is_prime(num): primes.add(num_str) return primes def main(): import itertools max_length = 6 primes = set() digits = ['1', '3', '5', '7', '9'] for length in range(1, max_length + 1): for num_tuple in itertools.product(digits, repeat=length): num_str = ''.join(num_tuple) num = int(num_str) if is_prime(num): primes.add(num_str) primes_list = list(primes) max_len = max(len(s) for s in primes_list) if primes_list else 0 primes_by_length = {} for s in primes_list: l = len(s) if l not in primes_by_length: primes_by_length[l] = set() primes_by_length[l].add(s) N = int(sys.stdin.readline()) S = sys.stdin.readline().strip() dp = [0] * (N + 1) for i in range(1, N + 1): dp[i] = dp[i-1] for l in primes_by_length: if i - l >= 0: substring = S[i - l : i] if substring in primes_by_length.get(l, set()): if dp[i - l] + 1 > dp[i]: dp[i] = dp[i - l] + 1 print(dp[N]) if __name__ == "__main__": main()