AtCoder が提供しているABC（AtCoder Beginner Contest）394 C問題をC++とPythonで解いてみました。ABC394は、2025年2月22日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Debug（Difficulty : 161）
問題の詳細は、リンク先をご覧ください。
単純な文字列の置き換えでは失敗します。AtCoder Problems による Difficulty は 161 でした。
解答案
単純に連続部分文字列 “WA” を “AC” に変換するだけでは正解になりません。反例が入力例2になります。具体的には、WWA → WAC → ACC と変換する必要があります。変換前の ‘W’ の個数と変換後の ‘C’ の個数は一致します。
C++ プログラム例（ABC394C）
変換前の文字が ‘A’ である場合、遡って一つ前の文字が ‘W’ かを調べて変換します。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin >> s;
for (int i = 1; i < (int)s.length(); ++i) {
if (s[i] == 'A') {
int w_index = i - 1;
while (w_index >= 0) {
if (s[w_index] == 'W') {
s[w_index] = 'A';
s[w_index + 1] = 'C';
--w_index;
} else {
break;
}
}
}
}
cout << s << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC394C）
基本的な考え方は同じです。Python では文字列を直接変更できないため、リストとして扱い、join メソッドを使用します（2、15行目）。以下がプログラムです。
"""AtCoder Beginner Contest 394 C"""
s = list(input())
for i in range(1, len(s)):
if s[i] == 'A':
w_index = i - 1
while w_index >= 0:
if s[w_index] == 'W':
s[w_index] = 'A'
s[w_index + 1] = 'C'
w_index -= 1
else:
break
print("".join(s))こちらも「AC」と判定されました。
最後に
入力例2が無ければ、単純に文字列を置き換えていたかもしれません。
引き続き ABC の問題を紹介していきます。
