結果

問題 No.2860 Heal Slimes
ユーザー dyktr_06
提出日時 2025-04-18 16:03:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,823 bytes
コンパイル時間 801 ms
コンパイル使用メモリ 73,116 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-18 16:03:42
合計ジャッジ時間 3,452 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25 WA * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric> // 標準ライブラリインクルード（今回は直接は使わない）

// 負の数も扱えるように剰余を計算する関数 (modulus > 0 を想定)
// C++の % 演算子は結果が負になることがあるため、常に 0 以上 modulus 未満の値を返すように調整します。
long long correct_modulo(long long value, long long modulus) {
    long long result = value % modulus;
    // 結果が負の場合は、modulus を足して非負にする
    return result < 0 ? result + modulus : result;
}

int main() {
    // 標準入出力の高速化
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    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];
    }

    // --- 条件1: 全てのスライムの体力が X で割った余りが等しいか ---
    // 回復魔法は体力を X ずつ増やす操作です。
    // 最終的に全てのスライムの体力を等しくするためには、
    // どのスライムの体力も X で割った余りが同じでなければなりません。
    // なぜなら、操作によって体力は X の倍数だけ変化するため、
    // X で割った余りは変化しないからです。
    // したがって、初期状態で全ての H_i mod X が等しい必要があります。
    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" << std::endl;
            return 0;
        }
    }

    // --- 条件2: 差分に基づく累積和のチェック ---
    // スライム i と i-1 の体力の差を D_i = H_i - H_{i-1} (i >= 1) とします。
    // 全てのスライムの体力を等しくするということは、最終的に全ての D_i (i >= 1) を 0 にするということです。
    // 回復魔法を j 番目から j+K-1 番目のスライムにかける操作は、
    // D_j を X 増加させ、D_{j+K} を X 減少させる効果があります (ただし j+K < N)。
    // (j=0 の場合は D_0 を X 増加させ、D_K を X 減少させます)
    //
    // 条件1より、全ての D_i (i >= 1) は X で割り切れることが保証されています。
    // そこで、q_i = D_i / X とします。
    // 操作は、q_j に +1 し、q_{j+K} に -1 する (j >= 1)、
    // または D_0 に +X し、q_K に -1 する (j = 0) と言い換えられます。
    //
    // j >= 1 の操作は、インデックスを K で割った余りが同じペア (j と j+K) の間で値 (+1 と -1) を移動させるだけです。
    // このため、インデックス i を K で割った余りが m (ただし m = 1, 2, ..., K-1) であるような q_i の合計値は、
    // j >= 1 の操作によっては変化しません。
    // 最終目標 (全ての q_i = 0, i >= 1) では、これらの合計値は当然 0 です。
    // したがって、初期状態においても、これらのグループ (m=1 から K-1) の q_i の合計値が 0 でなければなりません。
    //
    // グループ m = 0 (インデックス K, 2K, ...) の合計値は、j=0 の操作 (D_0 と q_K に影響) を使うことで
    // 任意の値に変更可能なので、初期値が 0 である必要はありません。

    // 各グループ (mod K) ごとの q_i の合計値を計算します。
    std::vector<long long> sums(k, 0LL); // sums[m] は i % k == m となる q_i の合計を保持 (long long で初期化)

    for (int i = 1; i < n; ++i) {
        // D_i = H[i] - H[i-1]
        // q_i = D_i / x (条件1から割り切れることが保証されている)
        long long qi = (h[i] - h[i - 1]) / x;

        // q_i を、対応するグループ (インデックス i を K で割った余り) の合計に加算します。
        sums[i % k] += qi;
    }

    // グループ m = 1 から K-1 の合計値が 0 かどうかをチェックします。
    for (int m = 1; m < k; ++m) {
        if (sums[m] != 0) {
            // 合計が 0 でないグループが一つでもあれば、目標達成は不可能
            std::cout << "No" << std::endl;
            return 0;
        }
    }

    // 上記の条件1と条件2を両方満たす場合、全てのスライムの体力を等しくすることが可能です。
    std::cout << "Yes" << std::endl;

    return 0;
}
0