【ABC109】C - SkipをC++を使って解説

はじめに

　皆さんこんにちは！ 競プロの問題の理解を深めるために解説記事を書いていこうと思います！今回は ABC109 C です！
気に入っていただけたらLGTMして頂けるとうれしいです！
何かあればコメントやTwitterからお願いいたします!

C - Skip

問題概要

座標$X$から$N$個の座標$x_i$を以下の条件で1回以上訪れるとき
　・座標$x$から座標$x + D$に移動する
　・座標$x$から座標$x - D$に移動する
このときの最大値$D$を求めよ．

制約

・$1 \leq N \leq 10^5$
・$1 \leq X \leq 10^9$
・$1 \leq x_i \leq 10^9$
・$x_i$はすべて異なる
・$x_1, x_2, ..., x_N \not= 0$

考察

ポイント

各座標の差から最大値の$D$を求める

解説

各座標をそれぞれ移動するのでそれぞれの座標との距離が必要であると考えられます．それぞれの距離での最大公約数を求めることによって座標を$D$だけで移動することができます．
　入力例2では

3 81
33 105 57
//計算
81 - 33 = 48
81 - 105 = -24
81 - 57 = 24
33 - 105 = -72
33 - 57 = -24
105 - 57 = 48

となり絶対値をとって最大公約数を求めると24となり，出力と一致します．

それでは実装していきましょう．

実装

　最大公約数はgcdがC++のライブラリにあるので使いましょう．
　互いの距離を一直線で順番になるようにsortを使っています．

正解コード

#include <bits/stdc++.h>
using namespace std;

int main()
{
    //入力
    int N;
    cin >> N;
    long long ans, X;
    cin >> X;
    vector<long long> x(N); 
    for(int i = 0; i < N; i++){
        cin >> x[i];
    }
    //ソートして順番通りにする
    sort(x.begin(), x.end());
    //初期値はXとxの最小値
    ans = abs(X - x[0]);
    //N個分繰り返す
    for(int i = 1; i < N; i++){
        ans = gcd(ans, x[i] - x[i-1]);
    }
    //出力
    cout << ans << endl;
}