結果

問題 No.2860 Heal Slimes
コンテスト
ユーザー dyktr_06
提出日時 2025-04-18 16:28:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,299 bytes
コンパイル時間 955 ms
コンパイル使用メモリ 77,928 KB
実行使用メモリ 7,936 KB
最終ジャッジ日時 2025-04-18 16:28:08
合計ジャッジ時間 5,472 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 45 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm> // std::max を使うため

// gemini

// 負の数も扱えるように剰余を計算する関数 (modulus > 0 を想定)
long long correct_modulo(long long value, long long modulus) {
    long long result = value % modulus;
    // 結果が負の場合は、modulus を足して非負にする
    return result < 0 ? result + modulus : result;
}

// 各テストケースを処理する関数
void solve() {
    long long n; // スライムの数
    long long k; // 回復魔法の対象となる連続するスライムの数
    long long x; // 回復量
    std::cin >> n >> k >> x;

    std::vector<long long> h(n); // 各スライムの体力
    for (int i = 0; i < n; ++i) {
        std::cin >> h[i];
    }

    // --- Special Case: K = N ---
    if (k == n) {
        bool all_equal = true;
        for (int i = 1; i < n; ++i) {
            if (h[i] != h[0]) {
                all_equal = false;
                break;
            }
        }
        std::cout << (all_equal ? "Yes\n" : "No\n");
        return;
    }

    // --- Condition 1: Modulo X Check ---
    long long h0_mod = correct_modulo(h[0], x);
    for (int i = 1; i < n; ++i) {
        if (correct_modulo(h[i], x) != h0_mod) {
            std::cout << "No\n";
            return;
        }
    }

    // --- Calculate scaled differences q_i ---
    std::vector<long long> q(n - 1);
    for (int i = 1; i < n; ++i) {
        q[i - 1] = (h[i] - h[i - 1]) / x;
    }

    // --- Determine minimum required a0 based on A_i >= 0 and c_j >= 0 (j%k==0) ---

    // Calculate max prefix sum P_i = sum_{l=1..i} q_l
    // This relates to the condition A_i >= 0 -> a0 >= max P_i
    long long max_p_sum = 0; // max_{1<=i<N} P_i (Initialize to 0, because a0 >= 0 is required)
    long long current_p_sum = 0;
    for (int i = 0; i < n - 1; ++i) {
         current_p_sum += q[i];
         max_p_sum = std::max(max_p_sum, current_p_sum);
    }

    // Calculate max prefix sum S_r = sum_{l=1..r} q_{lK}
    // This relates to the condition c_{rK} >= 0 -> a0 >= max S_r
    long long max_s_sum = 0; // max_{r>=1, rK<=N-K} S_r (Initialize to 0)
    long long current_s_sum = 0;
    for (long long r = 1; ; ++r) {
        long long index_rk = r * k;
        if (index_rk > n - k) break; // Check if index corresponds to an existing c_j (j<=N-K)
        if (index_rk - 1 >= q.size()) break; // Check bounds for q array access

        current_s_sum += q[index_rk - 1];
        max_s_sum = std::max(max_s_sum, current_s_sum);
    }

    // Determine the minimum valid non-negative a0
    // a0 must be >= 0, >= max P_i, and >= max S_r
    long long a0 = std::max({0LL, max_p_sum, max_s_sum});

    // --- Calculate virtual operation counts c_i and check conditions ---
    // Calculate c_i for i = 0 to N-1 using the recurrence relation
    // c_i = a_i + c_{i-K}, where a_0 is the calculated value and a_i = -q_i for i>=1.
    std::vector<long long> c(n, 0LL);
    bool possible = true;
    for (int i = 0; i < n; ++i) {
        // Determine a_i for the recurrence
        long long ai = (i == 0) ? a0 : (i < n ? -q[i - 1] : 0); // Use q[i-1] for a_i (i>=1)

        // Determine c_{i-K} (0 if i < K)
        long long c_prev = (i < k) ? 0 : c[i - k];

        // Calculate c_i
        c[i] = ai + c_prev;

        // Check Condition 1: c_j >= 0 for actual operations (0 <= j <= N-K)
        if (i <= n - k) {
            if (c[i] < 0) {
                possible = false;
                break;
            }
        }
        // Check Condition 2: "virtual" c_j must be 0 for non-existent operations (N-K < j < N)
        // This ensures the operations properly terminate and don't leave residual effects.
        else { // i > n - k
             if (c[i] != 0) {
                 possible = false;
                 break;
             }
        }
    }

    // Output the final result based on the checks
    std::cout << (possible ? "Yes\n" : "No\n");
}

int main() {
    // 高速化のための設定
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t; // テストケース数
    std::cin >> t;
    while (t--) { // T 回ループ
        solve(); // 各テストケースを解く関数を呼び出す
    }
    return 0;
}
0