zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC125-C「GCD on Blackboard」です。
ポイント
実装量は少ないものの，解きごたえのある問題でした。まず，問題文の解釈を行います。行う操作は$N$個の整数から1つ選んで書き換えるというものですが，目的は最大公約数を大きくすることです。したがって，ある整数が選ばれれば，その整数を適当に設定すれば全体の最大公約数は「残りの$(N-1)$個の最大公約数」にすることができます。なぜなら，選んだ整数をどのように変えようと，残りの$(N-1)$個の最大公約数を変えることはできないからです。
すると，$N$個の整数に関してそれぞれの整数以外の$(N-1)$個の整数の最大公約数のうち最大の数を答えとして出力すればよいことが分かります。さて，どのようにこの数を求めれば良いのでしょうか。
まず単純には全探索が考えられます。このとき，全ての$N$に対して残りの$(N-1)$個の最大公約数を求めるのに必要な計算量は$O(N\log\min \{A_i\})$であるため，全体で計算量は$O(N\cdot N\log \min\{A_i\})$かかってしまいアウトです。そこで，全探索の方法を工夫することが求められます。
今回は$N$個の整数を調べるという前提は崩せません。そこで，$(N-1)$個の最大公約数を求めるフェーズの計算量を削減することが求められます。少し考えてみると，$(N-1)$回ともほぼ同じ操作をしていることが分かります。自分以外の整数というのは，毎回ほぼ同じですからね。
すると，前もって$N$個の最大公約数を区間ごとに求めておくというアイディアが浮かびます。メモ化や累積和と呼ばれることもあります。今回は累積の最大公約数を求めます。このときコツがあるのですが，両方向からの累積最大公約数を求めておくと見通しが良くなります。
今回利用する最大公約数の性質は，結合則です。$A,B,C$の最大公約数は「$A$と$B$の最大公約数」と$C$の最大公約数になります。このように，最大公約数は累積和のように前から（後ろから）次々に（再帰的に）計算することが可能です。
なお，最大公約数を求める方法に関しては，以下の記事をご覧ください。ユークリッドの互除法を利用すれば便利に求められます。
両方向からの累積計算
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {
return b != 0 ? gcd(b, a % b) : a;
}
int N;
ll A[100010];
ll X[100010];
ll Y[100010];
int main(){
cin >> N;
rep(i, N) cin >> A[i];
X[0] = A[0];
Y[0] = A[N-1];
rep(i, N){
// 左方向からの累積最大公約数を結合則を使って求める
X[i+1] = gcd(X[i], A[i+1]);
// 右方向からの累積最大公約数を結合則を使って求める
Y[i+1] = gcd(Y[i], A[(N-1)-(i+1)]);
}
ll ans = 0;
// 初期値は0インデックスの整数が選ばれたときの最大公約数Y[N-2]と
// N-1インデックスが選ばれたときの最大公約数X[N-2]の大きい方に設定する
ans = max(X[N-2], Y[N-2]);
// 初期値で使った両端を除いたN-2個の要素に関して全探索を行う
rep(i, N-2){
// ansを更新
ans = max(ans, gcd(X[i], Y[(N-1)-(i+2)]));
}
cout << ans << endl;
}
コメント