AtCoder が提供しているABC（AtCoder Beginner Contest）324 のC問題をC++とPythonで解いてみました。ABC324は、2023年10月14日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Error Correction（Difficulty : 637）
問題はリンク先をご覧ください。
2つの文字列を比較しますが、少し工夫が必要です。AtCoder Problems による Difficulty は、637 でした。
解答案
本質的には、2つの文字列を比較する問題です。大きく分けて2つの方針でプログラムしました。
- 前から走査して、差異ができたら文字列の長さで処理を分ける。
- 前後から走査して、後で判定する。
それぞれの方針の詳細は、プログラム例として紹介します。
C++ プログラム例（ABC324C）
前から走査して、差異ができたら文字列の長さで処理を分ける。
文字列 T’ と Si を以下の手順で比較します。
- T’ と Si の長さの差が1を超える場合、次を調べる（18ー20行目）。
- 2つの文字列を前から比較していく。文字が異なれば、変数 diff をひとつ増やす。
- Si の方が長い場合、Si の次の文字と比較します。一致しない場合は、diff を増やして、ループを抜けます。一致する場合は、Si のインデックスをひとつ増やします（24ー29行目）。
- T’ の方が長い場合、T’ の次の文字と比較します。一致しない場合は、diff を増やして、ループを抜けます。一致する場合は、T’ のインデックスをひとつ増やします（30ー35行目）。
- 変数 diff の値が1以下であれば、T と等しい可能性があるため、配列 k に格納します（40ー41行目）。
このプログラムは、ループ内でループカウンタを更新しています（35行目）。一般的にはあまりよくないと考えられていますが、29行目と対称性もあり、許容することにしました。
少し長くなりましたが、以下がC＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
string t;
cin >> n >> t;
vector<string> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
vector<int> k;
for (int i = 0; i < n; ++i) {
int si = 0;
int diff = 0;
if (abs((int)t.length() - (int)s[i].length()) > 1) {
continue;
}
for (int j = 0; j < t.length(); ++j) {
if (t[j] != s[i][si]) {
++diff;
if (t.length() + 1 == s[i].length()) {
if ((si + 1 < s[i].length())&&(t[j] != s[i][si + 1])) {
++diff;
break;
}
++si;
} else if (t.length() - 1 == s[i].length()) {
if ((j + 1 < t.length())&&(t[j + 1] != s[i][si])) {
++diff;
break;
}
++j;
}
}
++si;
}
if (diff <= 1) {
k.push_back(i + 1);
}
}
cout << k.size() << endl;
for (int i = 0; i < k.size(); ++i) {
cout << k[i] << " ";
}
cout << endl;
return 0;
}前後から走査して、後で判定する。
文字列 T’ と Si を以下の手順で比較します。
- T’ と Si の長さの差が1を超える場合、次を調べる（16ー18行目）。
- 2つの文字列を前から比較していく。一致した文字数を left として保存しておく（19ー26行目）。
- 2つの文字列を後ろから比較していく。一致した文字数を right として保存しておく（27ー34行目）。
- T’ と Si の長さにより場合分けして以下の判定を行う（35ー41行目）。
- T’ と Si の長さが等しい場合、left + right が文字列の長さ-1以上なら、配列 k に格納します。
- T’ の方が長い場合、left + right がT’の長さ-1以上なら、配列 k に格納します。
- T’ の方が短い場合、left + right がT’の長さ以上なら、配列 k に格納します。
こちらのプログラムの方が、分かりやすいと感じる人が多いと思います。以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
string t;
cin >> n >> t;
vector<string> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
vector<int> k;
for (int i = 0; i < n; ++i) {
if (abs((int)t.length() - (int)s[i].length()) > 1) {
continue;
}
int left = 0;
for (int j = 0; j < min(t.length(), s[i].length()); ++j) {
if (t[j] == s[i][j]) {
left = j + 1;
} else {
break;
}
}
int right = 0;
for (int j = 0; j < min(t.length(), s[i].length()); ++j) {
if (t[t.length() - 1 - j] == s[i][s[i].length() - 1 - j]) {
right = j + 1;
} else {
break;
}
}
if ((t.length() == s[i].length())&&(left + right >= t.length() - 1)) {
k.push_back(i + 1);
} else if ((t.length() - 1 == s[i].length())&&(left + right >= t.length() - 1)) {
k.push_back(i + 1);
} else if ((t.length() + 1 == s[i].length())&&(left + right >= t.length())) {
k.push_back(i + 1);
}
}
cout << k.size() << endl;
for (int i = 0; i < k.size(); ++i) {
cout << k[i] << " ";
}
cout << endl;
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC324C）
後者のC++プログラムを移植しました。以下となります。
"""AtCoder Beginner Contest 324 C"""
n, t = input().split()
n = int(n)
s = [input() for i in range(n)]
k = []
for i in range(n):
if abs(len(t) - len(s[i])) > 1:
continue
left = 0
for j in range(min(len(t), len(s[i]))):
if t[j] == s[i][j]:
left = j + 1
else:
break
right = 0
for j in range(min(len(t), len(s[i]))):
if t[len(t) - 1 - j] == s[i][len(s[i]) - 1 - j]:
right = j + 1
else:
break
if len(t) == len(s[i]) and left + right >= len(t) - 1:
k.append(i + 1)
elif len(t) - 1 == len(s[i]) and left + right >= len(t) - 1:
k.append(i + 1)
elif len(t) + 1 == len(s[i]) and left + right >= len(t):
k.append(i + 1)
print(len(k))
print(*k)こちらも「AC」と判定されました。
最後に
文字列を比較する問題ですが、前から走査するプログラムと前後から走査するプログラムを紹介しました。どちらも文字列の長さによる処理が必要でした。このような場合、紙に書くなどして、頭を整理するとミスが減ると考えています。
引き続き ABC の問題を紹介していきます。
