結果

問題 No.910 素数部分列
ユーザー qwewe
提出日時 2025-05-14 13:19:13
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,727 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,700 KB
実行使用メモリ 97,760 KB
最終ジャッジ日時 2025-05-14 13:19:59
合計ジャッジ時間 4,852 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 WA * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    # Read N: the length of the string S
    N = int(sys.stdin.readline())
    # Read the string S
    S = sys.stdin.readline().strip()

    # Initialize the count of operations
    count = 0
    # Create a boolean list to keep track of used characters in S
    used = [False] * N
    
    # --- Phase 1: Greedy removal of single-digit primes ---
    # Iterate through the string S
    for i in range(N):
        # Check if the character at index i is '3', '5', or '7'
        # These are single-digit primes formed from the allowed digits {1, 3, 5, 7, 9}
        if S[i] == '3' or S[i] == '5' or S[i] == '7':
            # If it is a single-digit prime, increment the operation count
            count += 1
            # Mark this character as used
            used[i] = True

    # --- Phase 2: Find maximum pairs "11" or "19" from remaining characters ---
    # Construct the remaining subsequence S' containing only '1's and '9's
    # Preserve the relative order of these characters
    S_prime_chars = []
    for i in range(N):
        if not used[i]:
            S_prime_chars.append(S[i])
    
    # Get the length of the remaining subsequence S'
    N_prime = len(S_prime_chars)

    # If S' is empty, no more operations possible. Print the count from Phase 1.
    if N_prime == 0:
        print(count)
        return

    # Dynamic Programming to find the maximum number of non-overlapping two-digit prime subsequences
    # "11" or "19" that can be formed from S'.
    # We use O(1) space complexity for the DP calculation.
    
    # dp_prev stores the maximum number of pairs using prefix S'[0...k-2] (equivalent to dp[k-1])
    dp_prev = 0 
    # dp_curr stores the maximum number of pairs using prefix S'[0...k-1] (equivalent to dp[k])
    # It will be calculated in each iteration.
    dp_curr = 0
    
    # max_gain_from_prev_1 stores the maximum value of (1 + dp[i]) found so far
    # for indices i < k-1 where S_prime_chars[i] == '1'.
    # This value represents the potential maximum operations count if we pair the character
    # at index k-1 with a preceding '1'.
    # Initialize to -1, indicating that no preceding '1' has been encountered yet,
    # or that pairing with any preceding '1' does not increase the count.
    max_gain_from_prev_1 = -1 

    # Iterate k from 1 to N_prime. In each iteration k, we calculate dp[k].
    for k in range(1, N_prime + 1):
        # idx is the 0-based index corresponding to iteration k
        idx = k - 1 
        
        # --- Calculate dp[k] (value stored in dp_curr) ---
        
        # Option 1: The character S_prime_chars[idx] is not used as the second element of a pair.
        # In this case, dp[k] is the same as dp[k-1].
        current_dp_val = dp_prev 
        
        # Get the character at the current index
        current_char = S_prime_chars[idx]
        
        # Option 2: The character S_prime_chars[idx] is used as the second element of a pair ("11" or "19").
        # This is only possible if the character is '1' or '9', and there was a preceding '1'.
        if current_char == '1' or current_char == '9':
             # Check if max_gain_from_prev_1 is valid (i.e., a preceding '1' was found)
             if max_gain_from_prev_1 != -1:
                # If a valid preceding '1' exists, we can potentially form a pair.
                # The max operations count would be max_gain_from_prev_1.
                # We take the maximum of Option 1 and Option 2.
                current_dp_val = max(current_dp_val, max_gain_from_prev_1)

        # Store the calculated value of dp[k] into dp_curr
        dp_curr = current_dp_val

        # --- Update max_gain_from_prev_1 for the next iteration (k+1) ---
        # This value represents the maximum possible gain if we use S_prime_chars[idx]
        # as the *first* element ('1') of a future pair.
        # The value `1 + dp[idx]` = `1 + dp[k-1]` represents the total pairs count if we form such a pair
        # and optimally solve the subproblem for the prefix ending before index `idx`.
        if current_char == '1':
             # Update max_gain_from_prev_1 by considering using the current '1' at index idx
             # The value associated with completing pairs up to index idx-1 is dp_prev (dp[k-1])
             max_gain_from_prev_1 = max(max_gain_from_prev_1, 1 + dp_prev) 

        # Prepare for the next iteration: dp_curr becomes dp_prev
        dp_prev = dp_curr

    # The final result of the DP is dp[N_prime], which is stored in dp_curr after the loop completes.
    # Add this result to the count from Phase 1 to get the total maximum operations.
    print(count + dp_curr)

# Call the solve function to execute the logic
solve()
0