AtCoder が提供しているABC（AtCoder Beginner Contest）386 C問題をC++とPythonで解いてみました。ABC386は、2024年12月28日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Operate 1（Difficulty : 254）
問題の詳細は、リンク先をご覧ください。
2つの文字列の長さの違いにより判定します。AtCoder Problems による Difficulty は 254 でした。
解答案
文字列 S と T の長さの差に応じて、以下のように場合分けして考えます。
- 文字列 S と T の長さが同じ場合
文字列を比較して、差異が1か所以内であれば、一致させることができる。 - 文字列 S と T の長さの差の絶対値が 1 を超える場合
どのように操作しても、一致させることはできません。 - 文字列 S の長さが、T よりも 1 文字長い場合
文字列 S から 1 文字抜いて、文字列 T と同じになれば、一致させることができる。 - 文字列 T の長さが、S よりも 1 文字長い場合
文字列 T から 1 文字抜いて、文字列 S と同じになれば、一致させることができる。
C++ プログラム例（ABC386C）
上記の場合分けをコードで実装します。以下は補足です。
- 文字列 S の長さが、T よりも 1 文字長い場合
一致していない文字があれば、S の該当文字をスキップして次を調べます。差異が2か所あれば、ループを終了します。 - 文字列 T の長さが、S よりも 1 文字長い場合
一致していない文字があれば、T の該当文字をスキップして次を調べます。差異が2か所あれば、ループを終了します。 - C++ の場合、文字列の末尾にヌル文字（’\0’）が付加されているため、文字列走査中に配列外参照は発生しません（’\0′ にはアクセスする可能性はあります）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int k;
cin >> k;
string s;
cin >> s;
string t;
cin >> t;
bool result = true;
if (s.length() == t.length()) {
int mismatch = 0;
for (int i = 0; i < (int)s.length(); ++i) {
if (s[i] != t[i]) {
++mismatch;
}
}
if (mismatch > 1) {
result = false;
}
} else if (abs((int)s.length() - (int)t.length()) != 1) {
result = false;
} else if (s.length() > t.length()) {
int mismatch = 0;
int i = 0;
int j = 0;
while (i < (int)s.length()) {
if (s[i] != t[j]) {
++mismatch;
if (mismatch <= 1) {
--j;
} else {
break;
}
}
++i;
++j;
}
if (mismatch != 1) {
result = false;
}
} else if (s.length() < t.length()) {
int mismatch = 0;
int i = 0;
int j = 0;
while (j < (int)t.length()) {
if (s[i] != t[j]) {
++mismatch;
if (mismatch <= 1) {
--i;
} else {
break;
}
}
++i;
++j;
}
if (mismatch != 1) {
result = false;
}
}
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC386C）
基本的な考え方は同じです。Python の文字列は、文字列の長さ分のみメモリが確保されています。このため、短い方の文字列に一致しない文字（’#’）を加えています（17、33行目）。以下がプログラムです。
"""AtCoder Beginner Contest 386 C"""
k = int(input())
s = input()
t = input()
result = True
if len(s) == len(t):
mismatch = 0
for i in range(len(s)):
if s[i] != t[i]:
mismatch += 1
if mismatch > 1:
result = False
elif abs(len(s) - len(t)) != 1:
result = False
elif len(s) > len(t):
t += '#'
mismatch = 0
i = 0
j = 0
while i < len(s):
if s[i] != t[j]:
mismatch += 1
if mismatch <= 1:
j -= 1
else:
break
i += 1
j += 1
if mismatch != 1:
result = False
elif len(s) < len(t):
s += '#'
mismatch = 0
i = 0
j = 0
while j < len(t):
if s[i] != t[j]:
mismatch += 1
if mismatch <= 1:
i -= 1
else:
break
i += 1
j += 1
if mismatch != 1:
result = False
print("Yes" if result else "No")こちらも「AC」と判定されました。
最後に
引き続き ABC の問題を紹介していきます。
