結果

問題 No.2860 Heal Slimes
ユーザー dyktr_06
提出日時 2025-02-01 20:16:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,218 bytes
コンパイル時間 1,237 ms
コンパイル使用メモリ 78,540 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-02-01 20:16:45
合計ジャッジ時間 8,820 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 43 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
 
// ユークリッドの互除法による gcd の計算
long long gcd(long long a, long long b){
    while(b){
        a %= b;
        swap(a,b);
    }
    return a;
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T; 
    cin >> T;
    while(T--){
        int N, K;
        long long X;
        cin >> N >> K >> X;
        vector<long long> H(N);
        for (int i = 0; i < N; i++){
            cin >> H[i];
        }
 
        // ① 各 H[i] の余りが同じかチェック
        long long rem = H[0] % X;
        bool possible = true;
        for (int i = 0; i < N; i++){
            if(H[i] % X != rem) { 
                possible = false;
                break;
            }
        }
        if(!possible){
            cout << "No\n";
            continue;
        }
 
        // ② H[i] = rem + X*A[i] とおく．
        vector<long long> A(N);
        for (int i = 0; i < N; i++){
            A[i] = (H[i] - rem) / X;
        }
 
        // ③ 不変量：添字の余り（mod d）ごとの総和が操作後も同じ差でしか変わらない．
        // d = gcd(N, K) とおく．
        int d = (int)gcd(N, K);
        // 各クラス r (0 <= r < d) について，総和と個数を求める．
        vector<long long> sumClass(d, 0);
        vector<int> countClass(d, 0);
        for (int i = 0; i < N; i++){
            int cls = i % d;
            sumClass[cls] += A[i];
            countClass[cls]++;
        }
 
        // 最終的に全体が t にそろうとすれば，各クラスの和は t * (そのクラスの個数) になるはず．
        // つまり，任意のクラス r, s について，平均 (sumClass[r] / countClass[r]) が同じでなければならない．
        for (int r = 1; r < d; r++){
            // 整数同士の比較のため，交差掛けして比較
            if(sumClass[r] * (long long)countClass[0] != sumClass[0] * (long long)countClass[r]){
                possible = false;
                break;
            }
        }
 
        cout << (possible ? "Yes" : "No") << "\n";
    }
    return 0;
}
0