結果
問題 |
No.1294 マウンテン数列
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()