結果

問題 No.711 競技レーティング単調増加
ユーザー qwewe
提出日時 2025-05-14 13:07:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,777 bytes
コンパイル時間 684 ms
コンパイル使用メモリ 78,160 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-14 13:09:07
合計ジャッジ時間 2,920 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream> 
#include <vector> 
#include <algorithm> 

/**
 * @brief Solves the competitive rating monotonically increasing problem.
 * 
 * The problem asks for the minimum number of operations to make an array A strictly increasing.
 * An operation consists of changing any element A_i to any positive integer.
 * This is equivalent to finding the maximum number of elements that can be kept unchanged,
 * such that they form a subsequence that can be part of a strictly increasing sequence.
 * Let the indices of the kept elements be i_1 < i_2 < ... < i_k.
 * The original values A_{i_1}, A_{i_2}, ..., A_{i_k} must satisfy the condition
 * that it's possible to fill in the values between them to make the whole sequence strictly increasing.
 * Specifically, for any two consecutive kept indices i_j and i_{j+1}, we need to be able to
 * assign values A'_{p} for i_j < p < i_{j+1} such that A_{i_j} < A'_{i_j+1} < ... < A'_{i_{j+1}-1} < A_{i_{j+1}}.
 * This requires having enough distinct integer values between A_{i_j} and A_{i_{j+1}}.
 * The number of elements to fill is (i_{j+1} - 1) - (i_j + 1) + 1 = i_{j+1} - i_j - 1.
 * The number of available integers strictly between A_{i_j} and A_{i_{j+1}} is A_{i_{j+1}} - A_{i_j} - 1.
 * We need A_{i_{j+1}} - A_{i_j} - 1 >= i_{j+1} - i_j - 1, which simplifies to A_{i_{j+1}} - A_{i_j} >= i_{j+1} - i_j.
 * Let's define a transformed sequence B where B_i = A_i - i.
 * The condition A_{i_{j+1}} - A_{i_j} >= i_{j+1} - i_j is equivalent to A_{i_{j+1}} - i_{j+1} >= A_{i_j} - i_j,
 * which is B_{i_{j+1}} >= B_{i_j}.
 * Also, if B_{i_{j+1}} >= B_{i_j}, then A_{i_{j+1}} - i_{j+1} >= A_{i_j} - i_j.
 * Rearranging gives A_{i_{j+1}} >= A_{i_j} + (i_{j+1} - i_j). Since i_{j+1} > i_j$, i_{j+1} - i_j >= 1$.
 * Thus, A_{i_{j+1}} >= A_{i_j} + 1$, which implies A_{i_{j+1}} > A_{i_j}$.
 * So, the condition B_{i_{j+1}} >= B_{i_j} for a subsequence of indices i_1 < ... < i_k implies both
 * the original values A_{i_j} are strictly increasing and there's enough room to fill the gaps.
 * The problem reduces to finding the Longest Non-decreasing Subsequence (LNDS) of the sequence B_i = A_i - i.
 * If the length of the LNDS is k, then the maximum number of elements we can keep is k.
 * The minimum number of operations (changes) required is N - k.
 * We can find the length of the LNDS in O(N log N) time using dynamic programming with binary search.
 */
void solve() {
    int N; // Number of elements in the array
    // Read the number of elements N from standard input
    std::cin >> N; 
     
    // `dp` vector stores the minimum ending value for Longest Non-decreasing Subsequences (LNDS)
    // of increasing lengths. Specifically, dp[k] will store the smallest ending value of an LNDS of length k+1.
    std::vector<long long> dp; 
    // Reserve capacity N for the dp vector. This is an optimization that can potentially avoid 
    // multiple memory reallocations as the vector grows, improving performance slightly.
    dp.reserve(N);  
     
    // Iterate through the input sequence using 1-based indexing from 1 to N,
    // consistent with the problem statement indices A_1, A_2, ..., A_N.
    for (int i = 1; i <= N; ++i) { 
        long long A_i; // Variable to store the i-th rating value
        // Read the i-th rating value from standard input
        std::cin >> A_i; 
         
        // Calculate the transformed value B_i = A_i - i.
        // The core idea is to find the LNDS of this transformed sequence B.
        // Cast i to long long to prevent potential issues with large N, although N <= 2e5 fits in int. It's safer with arithmetic involving A_i which is long long.
        long long val = A_i - (long long)i; 
         
        // Use std::upper_bound to find the iterator pointing to the first element in the `dp` vector
        // that is strictly greater than `val`. The `dp` vector is maintained in non-decreasing order
        // throughout this process, satisfying the precondition for `std::upper_bound`.
        auto it = std::upper_bound(dp.begin(), dp.end(), val); 
         
        if (it == dp.end()) { 
            // If `std::upper_bound` returns `dp.end()`, it signifies that `val` is greater than or equal to
            // all elements currently present in `dp`. This means `val` can extend the
            // longest non-decreasing subsequence found so far.
            // Append `val` to the `dp` vector. This increases the length of the LNDS tracked by `dp` by 1.
            dp.push_back(val); 
        } else { 
            // If `it` points to an element `*it` within the `dp` vector (i.e., `it != dp.end()`),
            // it means `*it` is the smallest element in `dp` that is strictly greater than `val`.
            // Replacing `*it` with `val` updates the minimum possible tail element for an LNDS of length `(it - dp.begin()) + 1`.
            // This maintains the property that `dp[k]` stores the minimum tail for an LNDS of length k+1.
            // Crucially, having a smaller tail value (`val` instead of the original `*it`) might allow 
            // subsequent elements in the sequence B to extend this subsequence where they couldn't before.
            *it = val; 
        } 
    } 
     
    // After processing all N elements, the final size of the `dp` vector represents the length
    // of the Longest Non-decreasing Subsequence of the transformed sequence B.
    int lnds_length = dp.size(); 
     
    // The problem asks for the minimum number of operations (changes) needed to make the sequence A strictly increasing.
    // This minimum number is achieved by maximizing the number of elements kept unchanged.
    // The maximum number of elements that can be kept is equal to the LNDS length.
    // Therefore, the minimum number of operations required is N (total elements) minus `lnds_length`.
    int min_operations = N - lnds_length; 
     
    // Output the calculated minimum number of operations to standard output, followed by a newline character.
    std::cout << min_operations << "\n"; 
}

/**
 * @brief Main function to handle input/output setup and call the solver function.
 */
int main() { 
    // Optimize C++ standard input/output streams for faster execution.
    // std::ios_base::sync_with_stdio(false) disables synchronization between C++ streams and C stdio functions.
    // std::cin.tie(NULL) unties std::cin from std::cout, preventing flushes of std::cout before std::cin operations.
    // These are common optimizations in competitive programming.
    std::ios_base::sync_with_stdio(false); 
    std::cin.tie(NULL); 
    
    // Call the function `solve()` which contains the core logic of the problem solution.
    solve(); 
     
    // Return 0 to indicate successful program execution.
    return 0; 
}
0