結果
| 問題 |
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 |
ソースコード
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()