#1084005 (C++17) No.576 E869120 and Rings

• 問題: No.576 E869120 and Rings
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:14:05
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,073 ms / 1,500 ms
• コード長: 6,698 bytes
• コンパイル時間: 713 ms
• コンパイル使用メモリ: 97,504 KB
• 実行使用メモリ: 16,552 KB
• 最終ジャッジ日時: 2025-05-14 13:15:11
• 合計ジャッジ時間: 18,355 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
sample	AC * 3
other	AC * 27

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <iomanip>
#include <algorithm> // Required for std::max

using namespace std;

int N; // Number of gems
int K; // Minimum length of the segment
vector<int> b; // Doubled sequence of gems (0 for red, 1 for blue), 0-indexed
vector<double> P; // Prefix sums vector used in the check function

/**
 * @brief Check function for binary search. Determines if there exists a contiguous segment 
 * of gems on the ring with length L, where K <= L <= N, such that the ratio of blue gems 
 * in the segment is at least X.
 * 
 * The problem asks to maximize B/L, where B is the number of blue gems and L is the length.
 * This function checks if max(B/L) >= X is possible.
 * This is equivalent to checking if there exists a segment i..j such that B >= X*L.
 * Let b_k be 1 if gem k is blue, 0 if red. We need sum(b_k for k=i..j) >= X * (j-i+1).
 * Rewriting, sum(b_k - X for k=i..j) >= 0.
 * Let c_k = b_k - X. We need sum(c_k for k=i..j) >= 0.
 * Using prefix sums P, where P[k] = sum(c_p for p=0..k-1), this sum is P[j+1] - P[i].
 * So we need to check if there exists a pair (i, j) satisfying constraints such that P[j+1] >= P[i].
 * 
 * Constraints on segment i..j:
 * The segment starts at index i and ends at index j in the doubled sequence b (0-indexed).
 * The start index i must correspond to a position in the original sequence: 0 <= i <= N-1.
 * The segment must be contiguous on the ring, meaning j < i+N.
 * The length L = j-i+1 must satisfy K <= L <= N.
 * These constraints imply:
 *   0 <= i <= N-1
 *   i + K - 1 <= j <= i + N - 1
 * Which implies overall range for j is K-1 <= j <= 2N-2.
 * 
 * For a fixed j, the valid range for start index i is:
 *   max(0, j - N + 1) <= i <= min(N-1, j - K + 1)
 * Let this range be [L_j, R_j]. We need to check if P[j+1] >= min(P[i] for i in [L_j, R_j]).
 * This minimum is efficiently found using a sliding window minimum approach with a deque.
 * 
 * @param X The ratio value to check.
 * @return True if a segment with ratio >= X exists, False otherwise.
 */
bool check(double X) {
    // Calculate prefix sums P based on the transformed values c_k = b[k] - X.
    // P[k] stores the sum of c_p for p from 0 to k-1. P[0] = 0.
    P[0] = 0.0;
    for (int k = 0; k < 2 * N; ++k) {
        P[k + 1] = P[k] + (double)(b[k]) - X; 
    }

    // Deque stores indices `i` which are candidates for the minimum P[i] in the sliding window.
    // Indices in the deque are strictly increasing.
    // P values corresponding to indices in the deque maintain a specific property required for the algorithm.
    deque<int> dq; 

    // Iterate through all possible segment end points j.
    // j ranges from K-1 to 2N-2.
    for (int j = K - 1; j < 2 * N - 1; ++j) { 

        // Consider the index i_new = j - K + 1. 
        // This is the starting index 'i' for a segment ending at 'j' with minimum required length K.
        // This index is a potential candidate to be added to our sliding window minimum structure.
        // We only consider indices i_new that are valid start positions (0 <= i_new <= N-1).
        int i_new = j - K + 1; 
        if (i_new >= 0 && i_new <= N - 1) {
             // Maintain deque property for sliding window minimum:
             // Remove indices from the back of deque if their P value is >= P[i_new].
             // This ensures that dq.front() will hold the index with the minimum P value in the window.
             while (!dq.empty() && P[dq.back()] >= P[i_new]) {
                dq.pop_back();
            }
            dq.push_back(i_new);
        }

        // The valid range for start index i for a segment ending at j is [L_j, R_j].
        // The lower bound L_j = max(0, j - N + 1) ensures the segment length L <= N.
        // Remove indices from the front of the deque that are smaller than L_j,
        // as they are no longer within the sliding window corresponding to j.
        int L_j = max(0, j - N + 1);
        while (!dq.empty() && dq.front() < L_j) {
            dq.pop_front();
        }

        // If the deque is not empty after adjustments, dq.front() holds the index `i_min_idx` 
        // such that P[i_min_idx] is the minimum P[i] value for all valid `i` in the current window for `j`.
        // Check if P[j+1] >= P[i_min_idx]. This is equivalent to checking if sum(c_k for k=i..j) >= 0.
        if (!dq.empty()) {
            int i_min_idx = dq.front();
            if (P[j + 1] >= P[i_min_idx]) {
                return true; // Found a valid segment meeting the criteria
            }
        }
    }
    // If the loop completes without finding any segment satisfying the condition, return false.
    return false;
}


int main() {
    // Use faster I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Read input: N gems, minimum segment length K
    cin >> N >> K; 
    string a_str; // String representing gem colors ('1' for blue, '0' for red)
    cin >> a_str;

    // Create the doubled sequence `b` to handle circularity easily.
    // The sequence b has length 2N. b[0..N-1] is the original sequence, b[N..2N-1] is a copy.
    b.resize(2 * N);
    for (int i = 0; i < N; ++i) {
        b[i] = a_str[i] - '0'; // Convert char '0'/'1' to int 0/1
        b[i + N] = b[i];
    }
    
    // Pre-allocate space for prefix sums vector P to avoid reallocation within the check function.
    // Size 2N+1 is needed for indices 0 to 2N.
    P.resize(2 * N + 1);

    // Binary search for the maximum possible ratio X.
    // The ratio is between 0.0 and 1.0.
    double low = 0.0, high = 1.0;
    double ans = 0.0; // Stores the best ratio found so far that is achievable

    // Perform a fixed number of iterations (e.g., 100) for binary search.
    // This is sufficient to achieve the required precision (10^-6).
    // 2^-100 is much smaller than 10^-6.
    for(int iter = 0; iter < 100; ++iter) {
        // Calculate midpoint. Using this form avoids potential floating point issues vs (low+high)/2
        double mid = low + (high - low) / 2.0; 
        if (check(mid)) {
            // If a segment with average ratio >= mid exists, then `mid` is a possible answer.
            // We try to find an even higher ratio, so we update `low = mid`.
            ans = mid; 
            low = mid;
        } else {
            // If no segment has average ratio >= mid, the maximum possible ratio must be less than mid.
            // We search in the lower half, so update `high = mid`.
            high = mid;
        }
    }

    // Output the maximum possible ratio found with high precision.
    cout << fixed << setprecision(17) << ans << endl;

    return 0;
}