結果

問題 No.1294 マウンテン数列
ユーザー qwewe
提出日時 2025-05-14 13:04:29
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 7,582 bytes
コンパイル時間 299 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 85,212 KB
最終ジャッジ日時 2025-05-14 13:06:19
合計ジャッジ時間 4,178 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 5 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys

# Increase recursion depth if needed, though the solution is iterative.
# sys.setrecursionlimit(3000) 

def solve():
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    MOD = 998244353

    # Memoization dictionary to store computed values of N(V)
    # Key is V, value is the count of sequences with risk <= V.
    memo_N = {}

    # Function to compute N(V): the number of mountain sequences with risk degree <= V.
    # The dynamic programming approach takes O(N^2) time per call to this function.
    def count_sequences_with_risk_le_V(V):
        # Base case: Risk cannot be negative.
        if V < 0: 
            return 0
        
        # Use V as the key for memoization.
        state_key = V
        # Return memoized result if available.
        if state_key in memo_N:
            return memo_N[state_key]

        # dp_prev maps tuple (left_endpoint_idx, right_endpoint_idx) to count.
        # It stores the DP states from the previous step (i+1) while computing step i.
        dp_prev = {} 
        
        # Handle the base case N=2 separately.
        # The main DP loop runs from i = N-3 down to 0, which requires N >= 3.
        if N == 2:
             # For N=2, the sequence elements are {A[0], A[1]}.
             # The peak must be A[1]. The set A \ {peak} = {A[0]}.
             # We partition {A[0]} into L and R.
             # Case 1: L={A[0]}, R={}. The sequence is {A[0], A[1]}. Risk is |A[1]-A[0]|.
             # Case 2: L={}, R={A[0]}. The sequence is {A[1], A[0]}. Risk is |A[1]-A[0]|.
             # Both are valid mountain sequences if N=2.
             # We need to check if the risk is <= V.
             if A[1] - A[0] <= V:
                  # Both sequences are valid, total count is 2.
                  memo_N[state_key] = 2
                  return 2
             else:
                  # Neither sequence is valid, total count is 0.
                  memo_N[state_key] = 0
                  return 0
        
        # General case for N >= 3 begins here.
        # The DP builds the sequence structure by considering elements A[N-2], A[N-3], ..., A[0] one by one.
        # Base Case for the DP: Consider placing A[N-2] relative to the peak A[N-1].
        # This corresponds to step i = N-2 in the conceptual DP indexing from N-2 down to 0.
        
        diff_peak_neighbor = A[N-1] - A[N-2] # Difference between peak and its largest neighbor
        # Check if placing A[N-2] next to A[N-1] satisfies the risk constraint V.
        if diff_peak_neighbor <= V:
            # If A[N-2] is placed to the left of A[N-1]:
            # Sequence fragment looks like ..., A[N-2], A[N-1], ...
            # The endpoints of this fragment are (A[N-2], A[N-1]). Store indices (N-2, N-1).
            # There is 1 way to form this fragment initially.
            dp_prev[(N-2, N-1)] = 1 
            
            # If A[N-2] is placed to the right of A[N-1]:
            # Sequence fragment looks like ..., A[N-1], A[N-2], ...
            # The endpoints of this fragment are (A[N-1], A[N-2]). Store indices (N-1, N-2).
            # There is 1 way to form this fragment initially.
            dp_prev[(N-1, N-2)] = 1 
        
        # DP loop: Iterate downwards from i = N-3 down to 0.
        # In each step i, we consider placing element A[i].
        for i in range(N-3, -1, -1):
            dp_curr = {} # Dictionary to store DP states for the current step i.
            
            # Iterate through all valid states computed in the previous step (i+1).
            # The number of states in dp_prev is O(N-i), so this loop is efficient.
            for state, count in dp_prev.items():
                # `state` is a tuple (l_prev_idx, r_prev_idx)
                # `count` is the number of ways to reach this state.
                
                l_prev_idx, r_prev_idx = state # Indices of endpoints from previous step's fragment

                # Option 1: Place A[i] to the left of the current leftmost element A[l_prev_idx].
                # The new sequence fragment will start with A[i], A[l_prev_idx], ...
                # Check the difference constraint: The new difference is |A[l_prev_idx] - A[i]|.
                # Since A is sorted, A[l_prev_idx] > A[i], difference is A[l_prev_idx] - A[i].
                if A[l_prev_idx] - A[i] <= V:
                    # If constraint satisfied, update the DP state for step i.
                    # New endpoints are A[i] and A[r_prev_idx]. Indices are (i, r_prev_idx).
                    new_state = (i, r_prev_idx) 
                    # Add the count from the previous state to the new state count.
                    dp_curr[new_state] = (dp_curr.get(new_state, 0) + count) % MOD

                # Option 2: Place A[i] to the right of the current rightmost element A[r_prev_idx].
                # The new sequence fragment will end with ..., A[r_prev_idx], A[i].
                # Check the difference constraint: The new difference is |A[r_prev_idx] - A[i]|.
                # Since A is sorted, A[r_prev_idx] > A[i], difference is A[r_prev_idx] - A[i].
                if A[r_prev_idx] - A[i] <= V:
                    # If constraint satisfied, update the DP state for step i.
                    # New endpoints are A[l_prev_idx] and A[i]. Indices are (l_prev_idx, i).
                    new_state = (l_prev_idx, i) 
                    # Add the count from the previous state to the new state count.
                    dp_curr[new_state] = (dp_curr.get(new_state, 0) + count) % MOD
            
            # Update dp_prev to dp_curr for the next iteration (step i-1).
            dp_prev = dp_curr 

        # After the loop finishes (all elements A[0]...A[N-2] are placed),
        # dp_prev contains the final states representing complete mountain sequences.
        # Sum up the counts for all final states to get N(V).
        final_count = 0
        for count in dp_prev.values():
            final_count = (final_count + count) % MOD
        
        # Store the computed result in the memoization table and return it.
        memo_N[state_key] = final_count
        return final_count


    # Calculate the total sum of risk degrees over all mountain sequences.
    total_sum = 0
    
    # The maximum possible risk degree is A[N-1] - A[0].
    max_risk_possible = 0
    if N >= 2: # Check N>=2 as per problem constraints.
       max_risk_possible = A[N-1] - A[0] 
    
    # Compute the total sum using the identity:
    # Sum = Sum_{V=1..max_risk} V * (Number of sequences with risk exactly V)
    # Number of sequences with risk V = N(V) - N(V-1)
    
    # Initialize N(V-1) for V=0. N(-1) is defined as 0.
    prev_N_val = count_sequences_with_risk_le_V(-1) 
    
    # Iterate through all possible risk values V from 0 up to max_risk_possible.
    for V in range(max_risk_possible + 1):
       # Compute N(V), the count of sequences with risk <= V.
       curr_N_val = count_sequences_with_risk_le_V(V) 
       
       # Calculate the count of sequences with risk exactly V.
       # This is N(V) - N(V-1). Add MOD to handle potential negative result before taking modulo.
       count_risk_V = (curr_N_val - prev_N_val + MOD) % MOD
       
       # Add the contribution of sequences with risk V to the total sum: V * count_risk_V
       total_sum = (total_sum + V * count_risk_V) % MOD
       
       # Update prev_N_val for the next iteration (V+1).
       prev_N_val = curr_N_val

    # Print the final total sum modulo MOD.
    print(total_sum)

# Execute the solve function
solve()
0