AtCoder

ABC390 B問題(Geometric Sequence)を解く

AtCoder_ABC390_B

AtCoder が提供しているABC(AtCoder Beginner Contest)390 B問題をC++とPythonで解いてみました。ABC390は、2025年1月25日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

B問題 Geometric Sequence(Difficulty : 147)

問題の詳細は、リンク先をご覧ください。

ABC390 B問題 Geometric Sequence

公比を求めて、比が一定か確認します。AtCoder Problems による Difficulty は 147 でした。

解答案

数列 A=(A0,A1,,An1) に対して p=A1/A0 を求めて、この比が一定になれば等比数列となります。つまり以下となります

p=A2/A1=A3/A2==An1/An2

C++ プログラム例(ABC390B)

上記の式を確認します。割り算では誤差が生じるため、分母を払って整数として計算します(17行目)。

以下が、C++プログラムです。

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

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

	bool result = true;
	for (int i = 2; i < n; ++i) {
		if (a[i] * a[0] != a[i - 1] * a[1]) {
			result = false;
			break;
		}
	}

	if (result) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC390B)

Python版も基本的な考え方は同じです。以下がプログラムです。

"""AtCoder Beginner Contest 390 B"""
n = int(input())
a = list(map(int, input().split()))

result = True
for i in range(2, n):
    if a[i] * a[0] != a[i - 1] * a[1]:
        result = False
        break

print("Yes" if result else "No")

こちらも「AC」と判定されました。

最後に

浮動小数点数を使って割り算を使うと、誤差によりACを取るのが難しい場合があるようです。公式のユーザ解説で事例が示されています。

引き続き ABC の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA