AtCoder が提供しているABC（AtCoder Beginner Contest）370 C問題をC++とPythonで解いてみました。ABC370は、2024年9月7日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Word Ladder（Difficulty : 228）
問題の詳細は、リンク先をご覧ください。
一文字変更した文字列の中で辞書順で一番小さい文字列を見つけます。AtCoder Problems による Difficulty は 228 でした。
解答案
文字列の長さは、100文字以下であるため、全探索をして求めることができます。
少し工夫をします。文字列 $S$ の $i$ 文字目 $S_i$ と文字列 $T$ の $i$ 文字目 $T_i$ の文字コードが $S_i > T_i$ となっていた場合、文字の変換によって、辞書順は小さくなります。文字列の先頭から処理をすれば、一番左で変換した文字列が辞書順で一番小さくなります。
上記の条件を満たさない場合、差分の箇所は、$S_i < T_i$ となっています。この文字の変換によって、辞書順は大きくなります。このため、文字列の後ろから処理をすれば、結果的に辞書順で一番小さくなります。
この操作を繰り返して、$S$ と $T$ を一致させます。
C++ プログラム例（ABC370C）
上記の考察をプログラムとして実装しました。
- 先に文字列を左から走査します（13ー20行目）。
- 文字列の変換がなければ、次に文字列を後ろから走査します（24ー31行目）。
- 最後に配列 result の要素数と、その要素を出力します。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s, t;
cin >> s >> t;
vector<string> result;
bool isChange = true;
while (isChange) {
isChange = false;
for (int i = 0; i < s.length(); ++i) {
if (s[i] > t[i]) {
isChange = true;
s[i] = t[i];
result.push_back(s);
break;
}
}
if (isChange) {
continue;
}
for (int i = s.length() - 1; i >= 0; --i) {
if (s[i] != t[i]) {
isChange = true;
s[i] = t[i];
result.push_back(s);
break;
}
}
}
cout << result.size() << endl;
for (int i = 0; i < result.size(); ++i) {
cout << result[i] << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC370C）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 370 C"""
s = input()
t = input()
result = []
isChange = True
while isChange:
isChange = False
for i in range(len(s)):
if s[i] > t[i]:
isChange = True
s = s[:i] + t[i] + s[i + 1:]
result.append(s)
break
if isChange:
continue
for i in range(len(s) - 1, -1, -1):
if s[i] != t[i]:
isChange = True
s = s[:i] + t[i] + s[i + 1:]
result.append(s)
break
print(len(result))
for e in result:
print(e)こちらも「AC」と判定されました。
最後に
辞書順で出力が必要な問題でしたが、うまく解くことができました。
引き続き ABC の問題を紹介していきます。
