どうもこんにちは！
AtCoderなるもので毎週土曜日にビギナー向けのコンテストがあるということで初参加しました。結果はA,Bを完答、Cで方針はまとまったものの実装が間に合わず終了となりました。以下は個人記録もかねた振り返りです。
問題
問題は以下から。以下では取り組んだA～Cまでを振り返り。
A -22222-
数字で構成される文字列から、2だけを抜き取って結合した文字列を出力するというもの。ここは効率はともかく特に苦労はなし。
実施日が2/22にちなんでとのこと。
s = input()
for i in s:
if i == '2':
print(i,end="")
print("")
B -CAT-
標準入力で得た文字列を長さが短い順に並び変えて結合して出力するというもの。とりあえずリストに入れて、文字列の長さでソートして、結合したらいけるよねと考えました。
問題名は実施日が猫の日にちなんでとのこと。
n = int(input())
s = [input() for _ in range(n)]
s.sort(key=len)
print("".join(s))
C -Debug-
英大文字からなる文字列を最も先頭のWAをACに置き換えることを繰り返して、WAがなくなったら最終の文字列を出力するというもの。入力例にあったWWAだと、WWA→WCA→CAAという手順で置き換わっていくことになりますね。文字列は最大$3×10^5$、実行時間制限は2秒。
Pythonには指定した文字を置き換えるreplace関数があるので、WAがすべて置き換わるまで繰り返すことにしました。問題が先頭のWAをCAに置き換えるのを繰り返しということで、関数の実行回数は1回に指定。
s = input()
while "WA" in s:
s = s.replace("WA","AC",1)
print(s)
これで置き換え処理自体はできると思うのですが、タイムオーバーで実行できないテストデータが多数。WWWWWWWAのようにWが続くと文字列全部を対象にした置き換えの回数が増えて時間がかかるんですよね。
途中で文字列を最後からチェックして順番に置き換えていけば手戻り無く置き換えできることに気づいたんですが、いろいろこねくり回して作ったもののデバッグが間に合わずタイムアップ。心の乱れはコードの乱れにつながりますね。。
一夜明けて取り組んだのが以下。これならテストコードをすべてクリアできました。
s = list(input())
for i in range(len(s)-1,0,-1):
if s[i] == 'A' and s[i-1] == 'W':
s[i] = 'C'
s[i-1] = 'A'
print("".join(s))
--- 2025/9/20追記 ---
緑コーダー目指してD問題取り組んだので追記しました。
D
()[]<>の6文字の組み合わせで構成された文字列が与えられます。文字を前から順番にスタックして、閉じ括弧が出たときに同種類の開き括弧と並んだ場合は消去するとしたとき、最終的に空文字列になるかを判定する問題です。例えば(())という文字列なら、(()) → () → 空文字となります。
先に書いたとおりスタックで処理しました。dequeでは末尾のpopの計算量がO(1)なので問題ないと考えました。最後に空文字列になっているかの判定は必要です。(1敗)
from collections import deque
s = input()
d = deque()
ans = True
for i in s:
if i == '(' or i == '[' or i == '<':
d.append(i)
elif i == ')':
if len(d) == 0 or d.pop() != '(':
ans = False
break
elif i == ']':
if len(d) == 0 or d.pop() != '[':
ans = False
break
elif i == '>':
if len(d) == 0 or d.pop() != '<':
ans = False
break
if len(d) != 0:
ans = False
print("Yes" if ans else "No")
--- ここまで ---
おわりに
完答が2問と悔しい結果ですが、次回は3問完答、3月中に4問は完答を目指して頑張りたいと思います。
ではでは。