結果
問題 |
No.1867 Partitions and Inversions
|
ユーザー |
![]() |
提出日時 | 2025-05-14 13:26:30 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 6,274 bytes |
コンパイル時間 | 168 ms |
コンパイル使用メモリ | 82,244 KB |
実行使用メモリ | 60,644 KB |
最終ジャッジ日時 | 2025-05-14 13:27:26 |
合計ジャッジ時間 | 6,851 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 3 |
other | AC * 2 TLE * 1 -- * 62 |
ソースコード
import sys def solve(): N = int(sys.stdin.readline()) P = list(map(int, sys.stdin.readline().split())) # dp[k][i] = min inversions for prefix P[0...i-1] using k segments # Here, indices are 0-based for Python lists. # P[0...N-1] # A sequence A_1, ..., A_{k_prob+1} # 1 = A_1 < ... < A_{k_prob+1} = N+1 # Segments are P[A_idx - 1 ... A_{idx+1} - 2] # dp[num_segments][end_idx_plus_1] # dp[s][j] = min inversions for P[0...j-1] partitioned into s segments. # Base case: dp[0][0] = 0. dp[0][j > 0] = infinity. dp = [[float('inf')] * (N + 1) for _ in range(N + 1)] dp[0][0] = 0 # Precompute frequency structures for cost calculation if possible # For cost(p_len, segment_slice P[p_len...j-1]): # inversions between {P[0]...P[p_len-1]} and sorted(segment_slice) # To store values of P[0...p_len-1] for quick processing # We need counts of values. Maximum value is N. # freq_prefix[val] = count of val in P[0...p_len-1] # cost_val_lt_S_val[val] = count of elements in S smaller than val memo_cost = {} for s in range(1, N + 1): # s = number of segments for j in range(1, N + 1): # j = end_idx_plus_1 (length of prefix) if s > j: continue # Cannot partition j elements into more than j segments # The s-th segment is P[p ... j-1] # The prefix P[0 ... p-1] was partitioned into s-1 segments for p_idx in range(s - 1, j): # p_idx is length of prefix for dp[s-1] # so P[0...p_idx-1] # current segment starts at index p_idx if dp[s-1][p_idx] == float('inf'): continue current_segment_slice = P[p_idx:j] if not current_segment_slice: # Should not happen if p_idx < j cost = 0 else: # Calculate cost: inversions between P[0...p_idx-1] and sorted(current_segment_slice) # key = (p_idx, tuple(current_segment_slice)) # tuple for hash key too slow # key = (p_idx, p_idx, j) # Identifies the two sets of elements # The elements P[0...p_idx-1] are fixed by p_idx. # The elements P[p_idx...j-1] are fixed by (p_idx, j). # However, sorted(current_segment_slice) is what matters. # This cost calculation is the bottleneck # O((j-p_idx)log(j-p_idx) + N) sorted_current_segment = sorted(current_segment_slice) current_cost = 0 if p_idx > 0 and sorted_current_segment: # Optimized calculation for cost: # Sum over x in P[0...p_idx-1] of (count of y in sorted_current_segment where y < x) # Method 1: Using frequency arrays (if values are 1 to N) # freq_S = [0] * (N + 1) # Max value in P is N # for val_in_S in sorted_current_segment: # freq_S[val_in_S] += 1 # cum_freq_S = [0] * (N + 1) # for val_iter in range(1, N + 1): # cum_freq_S[val_iter] = cum_freq_S[val_iter-1] + freq_S[val_iter] # for val_in_prefix_P in P[0:p_idx]: # if val_in_prefix_P > 0: # Values are 1-indexed # current_cost += cum_freq_S[val_in_prefix_P - 1] # Method 2: Two pointers (less direct due to P not sorted) # Or for each element in P[0:p_idx], binary search in sorted_current_segment ptr_s = 0 len_sorted_segment = len(sorted_current_segment) # For each P_val in P[0...p_idx-1]: # Count elements in sorted_current_segment smaller than P_val # This is slow: p_idx * len_sorted_segment in worst case # Using binary search (bisect_left): p_idx * log(len_sorted_segment) # from bisect import bisect_left # for val_in_prefix_P_val in P[0:p_idx]: # current_cost += bisect_left(sorted_current_segment, val_in_prefix_P_val) # Merge-sort like counting (O(p_idx + len_sorted_segment)) # Create pairs (value, type), sort by value, then iterate # This is for inversions between two arbitrary arrays. # Here one is P[0:p_idx] (unsorted), other is sorted_current_segment. temp_p_vals = P[0:p_idx] # O(p_idx) # Count inversions (x > y) where x in temp_p_vals, y in sorted_current_segment # Iterate x in temp_p_vals. For each x, count y in sorted_current_segment s.t. y < x. # This is what bisect_left does. # To make it faster, sort temp_p_vals and use two pointers. # But sorting temp_p_vals is O(p_idx log p_idx). # The Fenwick tree approach over values 1..N is best if N not too large. # Cost: sort segment + (p_idx + len_seg) * log N_values for BIT ops. # Here N_values is N. # Simplest to write: iterate one, bisect other. # Cost per (p_idx, j) transition: O(L log L + p_idx log L) where L = j-p_idx from bisect import bisect_left for val_prefix in P[0:p_idx]: current_cost += bisect_left(sorted_current_segment, val_prefix) cost = current_cost dp[s][j] = min(dp[s][j], dp[s-1][p_idx] + cost) sys.stdout.write(str(dp[s][N]) + "\n") solve()