ABC125 C-GCD on Blackboard

どんな感じでブログを書けば良いかわからないのでとりあえず先日行われたABC125のC問題をどのように自分が考えたか書き連ねたいと思います。なおこれはあくまで僕の思考過程を書くものであって、決して最適な方法ではないと思われますし、もしかしたら嘘解法の可能性もありますので、参考程度に流し読みしてくれたら嬉しいです。

当然ですが与えられたある数の約数が答えの候補になりますので、そこから絞ればいけるのでは考え、とりあえずソートし一番小さい数に注目しました。(このソートは不要でしたね) この１番小さい数と他の全ての数とのgcdをひとつずつとっていきその値が最も小さい数１つを消せばそれが答えになるはずです。具体的に、(4,6,7,12)のような数列を考えました。

gcd(4,6)=2, gcd(4,7)=1, gcd(4,12)=4

となり7を消せば最大値2が得られます。とりあえずこのように実装し投げたところいくつかWAとなったため、考察を深めました。一番小さい数自体が不要なケースもあることに気づき(3,8,10,12のような場合)、この一番小さい数を消す場合と他で消す場合で、gcdが大きくなる方を出力するように変えることでACできました。(なおコンテストが終わってから累積gcdなるものを知り、勉強になりました。)以下コードです。

#include <iostream>
#include <algorithm>
using namespace std;
int  gcd( int a,int b){
    if (a%b==0){
        return b;
    }
    else{ 
        return gcd(b,a%b);
    }
}
int N;
int a[100010];
int main() { 
    cin>>N;
    for(int i=0;i<N;i++) cin>>a[i];
    //1番小さい数と２番目に小さい数を見つけるためにソート
    sort(a,a+N);
    int min_gcd=a[0];
    int remove_index=0;

    //a[0]とのgcdを取り一番小さくなったindexを書き換えたい
    for(int i=1;i<N;i++){
        int s=gcd(a[0],a[i]);
        if(s<min_gcd) {
            min_gcd=s;
            remove_index=i;
        }
    }

    //1,まずはa[0]を書き換えた時
    int ans1=a[1];
    for(int i=1;i<N;i++){
        ans1=gcd(ans1,a[i]);
    }

    //2,それ以外、つまりa[remove_index]を取り除いた時のgcd
    int ans2=a[0];
    for(int i=0;i<N;i++){
        if(i==remove_index) continue;
        ans2=gcd(ans2,a[i]);
    }

    //1,2の大き方が答え
    cout<<max(ans1,ans2)<<endl;

    return 0;
}