結果

問題 No.1867 Partitions and Inversions
ユーザー qwewe
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #

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()
0