結果
問題 |
No.910 素数部分列
|
ユーザー |
![]() |
提出日時 | 2025-04-16 15:29:14 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,180 bytes |
コンパイル時間 | 327 ms |
コンパイル使用メモリ | 82,464 KB |
実行使用メモリ | 98,464 KB |
最終ジャッジ日時 | 2025-04-16 15:31:51 |
合計ジャッジ時間 | 5,851 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 WA * 40 |
ソースコード
def is_prime(n): if n <= 1: return False if n <= 3: return True if n % 2 == 0 or n % 3 == 0: return False i = 5 w = 2 while i * i <= n: if n % i == 0: return False i += w w = 6 - w return True def generate_1_9_primes(): from itertools import product primes = set() for length in range(2, 6): for bits in product(['1', '9'], repeat=length): s = ''.join(bits) num = int(s) if is_prime(num): primes.add(s) return primes primes_set = generate_1_9_primes() n = int(input()) s = input().strip() step1_count = 0 remaining = [] for c in s: if c in {'3', '5', '7'}: step1_count += 1 else: remaining.append(c) remaining_str = ''.join(remaining) m = len(remaining_str) dp = [0] * (m + 1) for i in range(1, m + 1): dp[i] = dp[i-1] for k in range(2, 6): if i >= k: substr = remaining_str[i - k:i] if substr in primes_set: if dp[i - k] + 1 > dp[i]: dp[i] = dp[i - k] + 1 step2_count = dp[m] print(step1_count + step2_count)