AtCoder が提供しているABC（AtCoder Beginner Contest）301 のB問題をC++とPythonで解いてみました。ABC301は、2023年5月13日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Fill the Gaps（Difficulty : 67）
問題はリンク先をご覧ください。
与えられた数列に数列を加えながら出力する問題です。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」と判定されました。
最後に
問題文に記載してある通りに実装する問題でした。このような問題も、手早く解けるようになりたいです。
引き続き ABC の問題を紹介していきます。
