AtCoder

ABC305 B問題(ABCDEFG)を解く

AtCoder_ABC305_B

AtCoder が提供しているABC(AtCoder Beginner Contest)305 のB問題をC++とPythonで解いてみました。ABC305は、2023年6月10日21:00に実施されました。

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

B問題 ABCDEFG(Difficulty : 23)

問題はリンク先をご覧ください。

ABC305 B問題 ABCDEFG

直線上に与えらえた2点の距離を求める問題です。AtCoder Problems による Difficulty は 23 でした。

解答案

直線上に A から G までの点があります。与えられた2点間の距離を求めます。以下の図は、問題から借用しました。

応答を繰り返すわけではないため、地道に2点間の距離を計算しても解くことができます。ただし、今回は、累積和を使いました。これは累積和の書き方をパターン化しているため書きやすいと考えたためです。

補足ですが、問題の点の間隔は円周率になっています。

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

点の間隔を配列 a に格納しておきます(6行目)。ひとつ要素が多い配列 s を用意して、s[0] = 0、s[i] は配列 a の i 個の累積和となるように計算しておきます(8-11行目)。

与えられた p と q は、p < q となるように入れ替えておきます(15、16行目)。

回答は、累積和の配列 s を使って、すっきりと書くことができます(19行目)。

以下が、C++プログラムとなります。

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

int main()
{
	int a[6] = {3, 1, 4, 1, 5, 9};
	vector<int> s(7);
	s[0] = 0;
	for (int i = 0; i < 6; ++i) {
		s[i + 1] = s[i] + a[i];
	}

	char p, q;
	cin >> p >> q;
	if (p > q) {
		swap(p, q);
	}

	int result = s[q - 'A'] - s[p - 'A'];

	cout << result << endl;

	return 0;
}

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

Python プログラム例(ABC305B)

Python 版も累積和を使いました。前準備の考え方も C++ と同じです。関数 ord で、文字から文字コードへの変換ができます(12行目)。

"""AtCoder Beginner Contest 305 B"""
a = [3, 1, 4, 1, 5, 9]
s = [0] * 7
s[0] = 0
for i in range(6):
    s[i + 1] = s[i] + a[i]

p, q = input().split()
if p > q:
    p, q = q, p

result = s[ord(q[0]) - ord('A')] - s[ord(p[0]) - ord('A')]

print(result)

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

最後に

累積和は1個違いのミスに注意する必要があります。この問題は該当しませんでしたが、何回もクエリに従い計算するような場合に有効です。

ABC305 について、引き続き問題を紹介していきます。

COMMENT

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

CAPTCHA