2019-04-27

AtCoder ABC 125 C - GCD on Blackboard (緑色, 300 点)

AtCoder AtCoder300点 ABC-C 最大公約数数学(整数問題) 累積和データ構造テク：前処理数列区間累積和テク:左右両端からの累積和や累積結果を前処理 N個のものうち1個を変更・削除したものを解く緑色diff 累積和テク:累積和や累積結果を前処理しておくそのまま覚えたい典型問題典型要素を詰め合わせた教育的問題操作操作:1文字を変更する累積和の亜種

累積和！累積和！累積和！！！
でも累積和ならぬ累積 GCD なのと、左右両方から累積 GCD を求める。

問題へのリンク

問題概要

$N$ 要素からなる数列 $A_1, A_2, \dots, A_N$ が与えられる。この数列に対して

どれか一つ要素を選んで、 $10^{9}$ 以下の好きな正の整数に書き換える

という操作を行うことができる。そうしてできた数列全体の最大公約数として考えられる最大値を求めよ。

制約

$2 \le N \le 10^{5}$

考えたこと

とりあえず問題の言い換えとして

$N$ 個の値の中から 1 個だけ取り除いた $N-1$ 個の整数の最大公約数の最大値を求めよ

という問題だと思うことができる。なぜなら、 $A_i$ を書き換えようと決めたとき、それ以外の $N-1$ 個の整数の最大公約数を $G$ として、答えを $G$ より大きくすることはできない。そして $G$ に書き換えれば $G$ にすることはできる。

よって、問題がわかりやすく言い換えられたが、愚直にやると取り除く値が $N$ 通りあって、それぞれについて $N-1$ 個の最大公約数をとるので、 $O(N^{2} \log{A})$ の時間がかかってしまう。そこで、、、

どうするか？

問題は各 $i = 0, 1, \dots, N-1$ に対して、

$A_{0}, A_{1}, \dots, A_{i-1}$ , $A_{i+1}, \dots, A_{N-1}$ の最大公約数

を求めて、その最大値をとればよい。これは

$A$ の区間 $\lbrack 0, i)$ の最大公約数と、区間 $\lbrack i+1, N)$ の最大公約数の、最大公約数

と言い換えることができる。これは以下のように累積和ならぬ累積 GCD を前処理で求めておくと、高速にわかるのだ。

${\rm left} \lbrack p \rbrack$ := 区間 $\lbrack 0, p)$ の最大公約数
${\rm right} \lbrack p \rbrack$ := 区間 $\lbrack p, N)$ の最大公約数

これらはそれぞれ

// 累積 GCD (左と右両方)
vector<int> left(N+1, 0), right(N+1, 0);
for (int i = 0; i < N; ++i) left[i+1] = GCD(left[i], a[i]);
for (int i = N-1; i >= 0; --i) right[i] = GCD(right[i+1], a[i]);

という感じで求めることができる。こうしておけば、

前処理: $O(N \log{A})$
集計: $O(N \log{A})$

で求めることができる。

#include <iostream>
#include <vector>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }

int main() {
    int N; cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    // 累積 GCD (左と右両方)
    vector<int> left(N+1, 0), right(N+1, 0);
    for (int i = 0; i < N; ++i) left[i+1] = GCD(left[i], a[i]);
    for (int i = N-1; i >= 0; --i) right[i] = GCD(right[i+1], a[i]);
    
    // 集計
    int res = 0;
    for (int i = 0; i < N; ++i) {
        // 左側
        int l = left[i];

        // 右側
        int r = right[i+1];

        // 更新
        chmax(res, GCD(l, r));
    }
    cout << res << endl;
}

なぜ右からの累積 GCD も必要か

今回の問題が累積 GCD じゃなくて、累積和だったなら、実は

${\rm right} \lbrack p \rbrack$ := 区間 $\lbrack p, N)$ の累積和

は要らなくて、

${\rm left} \lbrack p \rbrack$ := 区間 $\lbrack 0, p)$ の累積和

だけで OK。これで区間 $\lbrack l, r)$ の和は

${\rm left}\lbrack r \rbrack - {\rm left}\lbrack l \rbrack$

で求められるのだ。だが今回の累積 GCD には「 - 」に対応する機能がない。引き算ができない。よって、区間 $\lbrack p, N)$ についての GCD を求めるには右からの累積 GCD が必要になる。

さらなる思考停止プレイのために: セグメントツリー

引き算ができなくても、区間に対する総和・GCD が求められる奥の手がある。それがセグメントツリー。セグメントツリーを使えば区間 $\lbrack l, r)$ の和を $O(\log{N})$ で求めることができる。

#include <iostream>
#include <vector>
#include <functional>
using namespace std;


// セグメントツリー
template<class Monoid> struct SegTree {
    using Func = function<Monoid(Monoid, Monoid)>;
    const Func F;
    const Monoid UNITY;
    int SIZE_R;
    vector<Monoid> dat;
    
    SegTree(int n, const Func f, const Monoid &unity): F(f), UNITY(unity) { init(n); }
    void init(int n) {
        SIZE_R = 1;
        while (SIZE_R < n) SIZE_R *= 2;
        dat.assign(SIZE_R * 2, UNITY);
    }
    
    /* set, a is 0-indexed */
    void set(int a, const Monoid &v) { dat[a + SIZE_R] = v; }
    void build() {
        for (int k = SIZE_R - 1; k > 0; --k)
            dat[k] = F(dat[k*2], dat[k*2+1]);
    }
    
    /* update a, a is 0-indexed */
    void update(int a, const Monoid &v) {
        int k = a + SIZE_R;
        dat[k] = v;
        while (k >>= 1) dat[k] = F(dat[k*2], dat[k*2+1]);
    }
    
    /* get [a, b), a and b are 0-indexed */
    Monoid get(int a, int b) {
        Monoid vleft = UNITY, vright = UNITY;
        for (int left = a + SIZE_R, right = b + SIZE_R; left < right; left >>= 1, right >>= 1) {
            if (left & 1) vleft = F(vleft, dat[left++]);
            if (right & 1) vright = F(dat[--right], vright);
        }                                                                                                              
        return F(vleft, vright);
    }
    inline Monoid operator [] (int a) { return dat[a + SIZE_R]; }
    
    /* debug */
    void print() {
        for (int i = 0; i < SIZE_R; ++i) {
            cout << (*this)[i];
            if (i != SIZE_R-1) cout << ",";
        }
        cout << endl;
    }
};


long long GCD(long long a, long long b) {
    return b ? GCD(b, a%b) : a;
}


int main() {
    int N;
    cin >> N;

    // セグツリーの構築
    SegTree<long long> seg(N, [](long long a, long long b) {
            return GCD(a, b);
        },
        0);
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        seg.set(i, A[i]);
    }
    seg.build();

    // 求める
    long long res = 0;
    for (int i = 0; i < N; ++i) {
        long long left = seg.get(0, i);
        long long right = seg.get(i+1, N);
        res = max(res, GCD(left, right));
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます