zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC118-C「Monsters Battle Royale」です。
ポイント
良問でした。サンプルの回答から「最大公約数を出力すればいいのでは？」と勘付くことができるため，考察フェーズが少なくて済むという面でもC問題として出題されているのでしょう。しかし，証明も込みで考えると，個人的には300点問題よりも難しいのではないかと思います。
まず最初に考えるべきことは，全探索です。しかし，今回はモンスターが最大で$10^5$体いるので難しそうです。そこで，「生き残ったモンスターの体力が最小値をとるときモンスターを倒す順番は関係ないのではないか」というお気持ちになります。そこで，問題をよりシンプルに捉えてみようという発想につながります。
つまり，結局この問題は与えられた整数同士の線形和を考えているだけにすぎないということです。線形和とは，足し引きのことだと思ってもらえればOKです。与えられた整数同士を足し引きすることで，最後に残った0以外の整数の最小値を求めなさいという問題ですね。
具体的には，モンスターの体力$A_1, A_2,\ldots, A_N$に対して生き残ったモンスターの体力$X$は
X &= x_1 A_1 + x_2 A_2 + \cdots x_N A_N
\end{align}
と表されます。実は，この状況は以下の等式を拡張したものだと捉えられます。
$a$と$b$を0でない整数とし，$d$をそれらの最大公約数とする。このとき整数$x$と$y$が存在して
ax + by = d
\end{align}
となる。さらに
- $d$ は $a x+b y$ と書ける最小の正の整数である。
- $a x+b y$ の形のすべての整数は $d$ の倍数である。
ベズーの等式を帰納的に用いれば，$g=\mathrm{gcd}(A_1, A_2, \ldots, A_N)$としたときに
X &= x_1 A_1 + x_2 A_2 + \cdots x_N A_N\\
&= g
\end{align}
となる$x_1, \ldots, x_N$が存在し，このとき$g$は$X$として作ることができる正の整数のうち最小の整数になります。以上で，この問題の答えが$g=\mathrm{gcd}(A_1, A_2, \ldots, A_N)$であることが示されました。
実際のところ，この問題で行なっている操作はユークリッドの互除法（の一部）になります。一回の攻撃は一回の引き算（割り算の一部）に相当します。正確には，ユークリッドの互助法はずっと同じモンスターを攻撃し続けることに相当しますが，上でお伝えした通り，生き残ったモンスターの体力の最小値を考える上では与えられた整数の線形和を考えればよいだけですので，必ずしも同じモンスターを攻撃し続ける必要はありません。
ユークリッドの互除法に関しては，以下の記事をご覧ください。
ベズーの等式とユークリッドの互除法
実装
#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];
int main(){
cin >> N;
rep(i, N) cin >> A[i];
int g;
// 初期値は最初の二体の最大公約数
g = gcd(A[0], A[1]);
// あとは全てのモンスターについて最大公約数を計算していく
rep(i, N-2) g = gcd(g, A[i+2]);
cout << g << endl;
}
コメント