結果

問題 No.711 競技レーティング単調増加
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:07:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 149 ms / 2,000 ms
コード長 4,799 bytes
コンパイル時間 243 ms
コンパイル使用メモリ 82,668 KB
実行使用メモリ 119,384 KB
最終ジャッジ日時 2025-05-14 13:08:54
合計ジャッジ時間 6,347 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import bisect

# Function to read input efficiently
readline = sys.stdin.readline

def solve():
    # Read N, the number of elements
    N = int(readline())
    # Read the array A
    A = list(map(int, readline().split()))

    # The problem requires finding the minimum number of operations to make A strictly increasing.
    # An operation consists of changing an element A[i] to any positive integer.
    # This is equivalent to maximizing the number of elements we *don't* change.
    # Let the final strictly increasing array be B.
    # If we decide to keep A[i] (0-based index), meaning B[i] = A[i], then these kept elements must satisfy:
    # 1. If we keep A[i] and A[j] with i < j, then B[i] < B[j]. So A[i] < A[j].
    # 2. The sequence B must be strictly increasing: B[0] < B[1] < ... < B[N-1].
    # 3. All B[k] must be positive integers: B[k] >= 1.
    #
    # Let I = {i_1, i_2, ..., i_k} be the set of indices (0-based) where we keep the original values, i.e., B[i_j] = A[i_j].
    # The indices must be sorted: 0 <= i_1 < i_2 < ... < i_k < N.
    # We must have B[i_j] < B[i_{j+1}] for all j. So A[i_j] < A[i_{j+1}}.
    # Also, there must exist values for the changed elements B[p] (p not in I) such that the whole sequence B is strictly increasing and positive.
    # For indices between i_j and i_{j+1}, we need B[i_j] < B[i_j + 1] < ... < B[i_{j+1} - 1] < B[i_{j+1}].
    # This requires at least B[i_j] + (i_{j+1} - (i_j + 1) + 1) <= B[i_{j+1} - 1] < B[i_{j+1}].
    # The number of elements between B[i_j] and B[i_{j+1}] is (i_{j+1} - 1) - (i_j + 1) + 1 = i_{j+1} - i_j - 1.
    # We need at least i_{j+1} - i_j steps of size 1 between B[i_j] and B[i_{j+1}].
    # Thus, B[i_j] + (i_{j+1} - i_j) <= B[i_{j+1}}.
    # Since B[i_j] = A[i_j] and B[i_{j+1}] = A[i_{j+1}], this condition becomes A[i_j] + (i_{j+1} - i_j) <= A[i_{j+1}}.
    # Rearranging gives A[i_{j+1}] - i_{j+1} >= A[i_j] - i_j.
    # Let C[p] = A[p] - (p+1). Then the condition is C[i_{j+1}] >= C[i_j].
    #
    # Additionally, we need B[k] >= 1 for all k.
    # For the first kept element A[i_1], we need B[0] < B[1] < ... < B[i_1-1] < B[i_1] = A[i_1].
    # The minimum possible values for B[0]..B[i_1-1] are 1, 2, ..., i_1.
    # Thus, we need B[i_1-1] < B[i_1], which means i_1 < A[i_1].
    # This is equivalent to A[i_1] >= i_1 + 1.
    # In terms of C values: C[i_1] = A[i_1] - (i_1+1) >= 0.
    # So, we need to find the longest subsequence of indices i_1 < i_2 < ... < i_k such that
    # A[i_1] >= i_1 + 1 (which implies C[i_1] >= 0) and C[i_j] <= C[i_{j+1}] for all j.
    # This is equivalent to finding the Longest Non-decreasing Subsequence (LNS) of the sequence C[i]
    # for those indices i where A[i] >= i + 1.

    # Create the filtered sequence of C values.
    C_filtered = []
    for i in range(N):
        # Check the condition A[i] >= i + 1.
        # This ensures that A[i] is large enough to be placed at index i+1 in a strictly increasing sequence starting from 1.
        if A[i] >= i + 1:
            # Compute the transformed value C = A[i] - (i + 1).
            # Note that A[i] and i+1 are potentially large, but A[i] is positive.
            # The result C_val can be positive, zero, or negative.
            # The condition A[i] >= i+1 ensures C_val >= 0.
            C_val = A[i] - (i + 1)
            C_filtered.append(C_val)

    # Compute the length of the Longest Non-decreasing Subsequence (LNS) of C_filtered
    # We use the standard patience sorting based algorithm which takes O(L log L) time,
    # where L is the length of C_filtered (L <= N).
    tails = []
    for x in C_filtered:
        # bisect_right(tails, x) finds an index `idx` such that all elements in `tails[:idx]` are <= x,
        # and all elements in `tails[idx:]` are > x.
        # This is the correct function for finding the place to update/insert for LNS.
        idx = bisect.bisect_right(tails, x)
        
        if idx == len(tails):
            # If x is greater than or equal to all elements currently in tails,
            # it means we can extend the longest non-decreasing subsequence found so far.
            tails.append(x)
        else:
            # If x is smaller than some element in tails, it means we found a potentially
            # better (smaller) ending value for a non-decreasing subsequence of length idx+1.
            # We replace tails[idx] with x. tails[idx] was the smallest element in tails
            # that is strictly greater than x.
            tails[idx] = x

    # The length of the LNS is the final size of the tails list.
    k = len(tails)
    
    # The maximum number of elements we can keep unchanged is k.
    # Therefore, the minimum number of elements we must change is N - k.
    print(N - k)

# Execute the solve function
solve()
0