【AtCoder】ARC148解説（Python）

AtCoder Regular Contest 148の解説記事です。

ARC148 A – mod M

問題

問題文の要約は以下の通りです。

問題の要約

整数列 \(A = \left( A_1, A_2, \dots, A_N \right)\) に対して、ちょうど1回だけ、\(M \ge 2\) の整数を1つ選び、すべての \(A_i\) を \(A_i \bmod M\) に置き換える操作を行う。この操作の後、整数列に含まれる値の種類数が最小になるようにしたとき、その種類数を求めよ。

解説

操作後の整数列の値の種類数をできるだけ少なくすることが目的ですが、実は 最大でも2種類 にしかならないことが分かります。なぜなら、\(M=2\)のとき、余りは必ず 0 または 1 になるからです。

より理想的なのは、すべての値を同じにする、つまり種類数を1にすることです。
このためには、操作後に各要素が同じ余りになる必要があります。
すなわち、すべての \(i\) について、 \(A_i \bmod M = A_{i+1} \bmod M\)となる必要があります。

すべての \(i\) について、 \(A_i \bmod M = A_{i+1} \bmod M\)となるためには、\((A_i – A_{i+1}) \bmod M = 0\) すなわち、\(A_i – A_{i+1}\)​ が \(M\) で割り切れる必要があります。

これはすべての隣接する差 \(|A_i – A_{i+1}|\) について、ある \(M \ge 2\) が共通に割り切れるかどうかを調べる問題に置き換えられます。

そこで、隣接する差の最大公約数（GCD）を考えます。$$g = \gcd\left( |A_1-A_2|,\; |A_2-A_3|,\; \dots,\; |A_{N-1}-A_N| \right)$$

解説

最大公約数を求める関数を定義します。math.gcdを使用することもできます。

# 最大公約数
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)

入力を受け取ります。

# 入力
N=int(input())
A=list(map(int,input().split()))

隣り合う各要素の差について GCD を計算し、\(g\)の計算結果によって答えを出力します。

# 変数 g を初期化
g=0

# 整数列の隣り合う各要素の差について GCD を計算する
for i in range(N - 1):
    g=gcd(g,abs(A[i]-A[i+1]))

# g が 1 なら、すべて同じ余りにできないため答えは 2
# それ以外（g=0 または g>=2）の場合は答えは 1
print(2 if g==1 else 1)

解答

# 最大公約数
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)

# 入力
N=int(input())
A=list(map(int,input().split()))

# 変数 g を初期化
g=0

# 整数列の隣り合う各要素の差について GCD を計算する
for i in range(N - 1):
    g=gcd(g,abs(A[i]-A[i+1]))

# g が 1 なら、すべて同じ余りにできないため答えは 2
# それ以外（g=0 または g>=2）の場合は答えは 1
print(2 if g==1 else 1)