AtCoder が提供しているABC（AtCoder Beginner Contest）314 のD問題をC++とPythonで解いてみました。ABC314は、2023年8月12日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 LOWER（Difficulty : 585）
問題はリンク先をご覧ください。
最後に文字更新したクエリの位置と最後に指定された小文字化と大文字化のクエリの位置を覚えて処理します。AtCoder Problems による Difficulty は 585 でした。
解答案
各クエリで以下を処理します。
- t = 1 : 各文字が最後に更新されたクエリの場所を change[i] に格納する。
- t = 2 : 文字列を最後に小文字化するクエリの場所を lower に格納する。
- t = 3 : 文字列を最後に大文字化するクエリの場所を upper に格納する。
C++ プログラム例（ABC314D）
上記のようにクエリを処理して各文字について、以下のように処理します。
- 最後に文字が更新されてから、小文字化も大文字化も指定されなかった → そのまま文字を出力する。
- 最後に文字が更新されてから、大文字化だけが指定されている → 大文字に変換して文字を出力する。
- 最後に文字が更新されてから、小文字化だけが指定されている → 小文字に変換して文字を出力する。
- 最後に文字が更新されてから、小文字化と大文字化の両方が指定されている。
- 大文字化の方が後ろで指定されている → 大文字に変換して文字を出力する。
- 小文字化の方が後ろで指定されている → 小文字に変換して文字を出力する。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
string s;
cin >> s;
int q;
cin >> q;
vector<int> t(q), x(q);
vector<char> c(q);
for (int i = 0; i < q; ++i) {
cin >> t[i] >> x[i] >> c[i];
--x[i];
}
int lower = -1;
int upper = -1;
vector<int> change(n, -1);
for (int i = 0; i < q; ++i) {
if (t[i] == 1) {
s[x[i]] = c[i];
change[x[i]] = i;
} else if (t[i] == 2) {
lower = i;
} else if (t[i] == 3) {
upper = i;
}
}
for (int i = 0; i < n; ++i) {
if ((lower <= change[i])&&(upper <= change[i])) {
cout << s[i];
} else if ((lower <= change[i])&&(change[i] < upper)) {
cout << (char)toupper(s[i]);
} else if ((change[i] < lower)&&(upper <= change[i])) {
cout << (char)tolower(s[i]);
} else if (lower < upper) {
cout << (char)toupper(s[i]);
} else {
cout << (char)tolower(s[i]);
}
}
cout << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC314D）
C++版を移植しました。文字列の書き換えができないため、リスト s_new を用意して文字を更新して、クエリ後の結果を空文字 result に追加して出力しました。Pythonらしい書き方ではないかもしれません。
ABC314から、使用できる言語が変わりました。このプログラムの結果は以下でした。
- Python (Mambaforge / CPython 3.10.10) → ACです。2回実行して、1189msと1154msでした。
- Python (CPython 3.11.4) → TLE判定となりました（18テストケースでTLE）。
- Python (PyPy 3.10-v7.3.12) → TLE判定となりました（20テストケースでTLE）。
Pythonらしい書き方をしていないことの影響でしょうか。今のわたしのPythonの理解度では理由が分かりません。
"""AtCoder Beginner Contest 314 D"""
n = int(input())
s = input()
q = int(input())
t = [0] * q
x = [0] * q
c = [""] * q
for i in range(q):
query = list(input().split())
t[i] = int(query[0])
x[i] = int(query[1]) - 1
c[i] = query[2]
lower = -1
upper = -1
change = [-1] * n
s_new = [""] * n
for i in range(n):
s_new[i] = s[i]
for i in range(q):
if t[i] == 1:
s_new[x[i]] = c[i]
change[x[i]] = i
elif t[i] == 2:
lower = i
elif t[i] == 3:
upper = i
result = ""
for i in range(n):
if lower <= change[i] and upper <= change[i]:
result += s_new[i]
elif lower <= change[i] and change[i] < upper:
result += s_new[i].upper()
elif change[i] < lower and upper <= change[i]:
result += s_new[i].lower()
elif lower < upper:
result += s_new[i].upper()
else:
result += s_new[i].lower()
print(result)最後に
ABC314から、使用できる言語とライブラリが更新されました。
C++ はもともとC++11/C++14 を意識して書いていたため影響はほとんどありませんでした。一方、Pythonは実行時間が予想できなくなりました。情報を集めて理解度を上げます。
引き続き ABC の問題を紹介していきます。
