Pythonで競プロに挑む日誌 vol.8 ~文字列 replace~

腑に落ちない.

現在の目標

• 今年の10月内に茶色を取得する ←イマココ
• 年内に緑色を取得する
• APG4b で C++ にも手を出す

今日の問題

ABC049C - 白昼夢 / Daydream
https://beta.atcoder.jp/contests/abs/tasks/arc065_a

結果

answer1.py

# coding: utf-8
S = input()
li_s = ["dream", "dreamer", "erase", "eraser"]

if "dreameraser" in S:
    S = S.replace("dreameraser", "")
elif "dreamerase" in S:
    S = S.replace("dreamerase", "")

sum_s = sum(S.count(s) * len(s) for s in li_s)

if sum_s == len(S):
    print("YES")
else:
    print("NO")

# 実行時間：19 ms
# メモリ　：3188 KB
# コード長：322 Byte
# 得点　　：0/300

うーん...昨日からずっと考えているのですがうまくいかない. 不本意ながら, 今回もいくつかほかの方の回答を参照しました.

---

answer2.py

# coding: utf-8
S = input().replace("eraser", "").replace("erase", "").replace("dreamer", "").replace("dream", "")
if S:
    print("NO")
else:
    print("YES")

# 実行時間：18 ms
# メモリ　：3188 KB
# コード長：166 Byte
# 得点　　：300/300

模範解答の多くはこのような感じでした.

• dreamer より前に dream を消してはいけない（er だけ残ったりするから）
• eraser より前に erase を消してはいけない（er だけ残ったりするから）
• erase や eraser より前に dreamer を消してはいけない（dreameraser がおかしなことになるから）

このように考えると、eraser → erase → dreamer → dream の順に消去していき, ピッタリ消去しきれるかどうか判定すればよい, という考え方は理解できます.

しかしながら, この方法だと, たとえば S = "dreameeraserr" が反例になると思いました.

dream, dreamer, erase, eraser のいずれかを末尾に単純追加するだけでは実現できない文字列でも, S に等しくなると判定されてしまいます.

---

というわけで, 自分としては下記に落ち着きました. 「S が小文字列」という条件もうまいこと利用できています.

answer3.py

S = input().replace('dream', 'D').replace('erase', 'E').replace('Der', 'D').replace('Er', 'E').replace('D','').replace('E','')

if len(S) == 0:
    print('YES')
else:
    print('NO')

# 実行時間：19 ms
# メモリ　：3188 KB
# コード長：189 Byte
# 得点　　：300/300

うーむ, まだまだ自力でたどり着けない...精進あるのみですね.

明日やること

ABC086C - Traveling を解く. AtCoder Beginners Selection は次がラスト.