AtCoder

ABC301 B問題(Fill the Gaps)を解く

AtCoder_ABC301_B

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

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

B問題 Fill the Gaps(Difficulty : 67)

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

ABC301 B問題 Fill the Gaps

与えられた数列に数列を加えながら出力する問題です。AtCoder Problems による Difficulty は 67 でした。

解答案

数列の隣接する2項の差が1を超える場合に、その中間の数を挿入していきます。

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

問題の制約から、数列 A の隣接する2項は異なります。中間に数字を挿入するのではなく、以下の手順で直接出力することにします。

  • Ai を出力します(14行目)。
  • 2項の差が1の場合は、なにもしません(15-17行目)。
  • 2項の差が1を超える場合は、[Ai + 1, Ai+1) の数字を出力します(Ai < Ai+1 の場合)。Ai > Ai+1 の場合は、同じように数字を減らしながら中間にある数字を出力します。
  • 最後に数列 A の最後の要素を出力します(28行目)。

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

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

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

	for (int i = 0; i < n - 1; ++i) {
		cout << a[i] << " ";
		if (abs(a[i] - a[i + 1]) == 1) {
			continue;
		}
		if (a[i] < a[i + 1]) {
			for (int j = a[i] + 1; j < a[i + 1]; ++j) {
				cout << j << " ";
			}
		} else {
			for (int j = a[i] - 1; j > a[i + 1]; --j) {
				cout << j << " ";
			}
		}
	}
	cout << a[n - 1] << endl;

	return 0;
}

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

Python プログラム例(ABC301B)

Python 版は、出力する結果をリスト result に格納しました(8、13、16、17行目)。 print 関数は、変数に ‘*’ をつけて各要素を出力できます。変数 sep を空白に指定して、空白区切りで出力しています(19行目)。

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

result = []

for i in range(n - 1):
    result.append(a[i])
    if abs(a[i] - a[i + 1]) == 1:
        continue
    if a[i] < a[i + 1]:
        for j in range(a[i] + 1, a[i + 1]):
            result.append(j)
    else:
        for j in range(a[i] - 1, a[i + 1], -1):
            result.append(j)
result.append(a[n - 1])

print(*result, sep=" ")

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

最後に

問題文に記載してある通りに実装する問題でした。このような問題も、手早く解けるようになりたいです。

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

COMMENT

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

CAPTCHA