結果

問題 No.910 素数部分列
コンテスト
ユーザー lam6er
提出日時 2025-04-15 21:05:12
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,180 bytes
コンパイル時間 494 ms
コンパイル使用メモリ 82,216 KB
実行使用メモリ 98,260 KB
最終ジャッジ日時 2025-04-15 21:11:04
合計ジャッジ時間 6,152 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 WA * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0