質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.46%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

1回答

1262閲覧

「ABC049C - 白昼夢」がエラーになる

jeanbiego

総合スコア3966

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

0クリップ

投稿2020/12/30 11:54

AtCoderのABC049C - 白昼夢 / Daydreamについての質問です。以下、問題文を引用します。

問題文

英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。
T の末尾に dream dreamer erase eraser のいずれかを追加する。

困っていること&試したこと

提出コード1で提出したところケースの4つ目以降で[RE](実行時エラー)と出ました。
提出コード2に変えて提出したところ[AC](正解)となりました。
提出コード1において、エラーになったケースではどのような状況だったのか…想像しましたが思いつきませんでした。どなたか、わかる方いらっしゃればご教示ください。

提出コード1

後ろ7~5文字が"dreamer", "eraser", "dream", "erase"のいずれかであれば、そこを削って再帰するアルゴリズムです。どれにも該当しなくなった時に残った文字列を返します。

python3

1def main(check_txt:str): 2 def pop_txt(check_txt:str, words:tuple): 3 for i in [7, 6, 5]: 4 if check_txt[-i:] in words: 5 return pop_txt(check_txt[:-i], words) 6 return check_txt 7 words = ("dreamer", "eraser", "dream", "erase") 8 result = pop_txt(check_txt, words) 9 if result == "": 10 return "YES" 11 else: 12 return "NO" 13 14print(main(input()))

提出コード2

"eraser", "erase", "dreamer", "dream"の順にreplaceで削った残り文字列を返すアルゴリズムです。

python3

1def main(check_txt:str): 2 def pop_txt(check_txt:str, words:tuple): 3 for w in words: 4 check_txt = check_txt.replace(w, "") 5 return check_txt 6 words = ("eraser", "erase", "dreamer", "dream") 7 result = pop_txt(check_txt, words) 8 if result == "": 9 return "YES" 10 else: 11 return "NO" 12 13print(main(input()))

自前のtest用コード

これを使うと、提出コード1でも2でも通りました。エラーケースはこのような単純なケースではないようです。

python3

1tests = ["erase", "erasedream", "dreameraser", "dreamerer"] 2corrects = ["YES", "YES", "YES", "NO"] 3for t, c in zip(tests, corrects): 4 assert c == main(t), f'期待する値[{c}], 入力値[{t}], 出力値[{main(t)}]'

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

入力文字列の制約が以下になっています。
1≦|S|≦100000

例えば、"dream"が20000個ある文字列が入力され、再帰呼び出しがオーバーしたのでは。

"dreamdreamdreamdreamdreamdreamdream..."

投稿2020/12/30 13:21

akiruno-oneone

総合スコア815

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

jeanbiego

2020/12/30 14:05

akiruno-oneoneさん ありがとうございます。納得しました。 再帰上限増やしたら結果が「メモリ制限超過」に変わったので、ご推察通りという感じがします。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.46%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問