競技プログラミング

【超初心者向け】AtCoderで最初に解くべき過去問集を分かりやすく解説します【9問目】

プログラミング

こんにちは!サトシ(@satoshi365_blog)です!

 

この記事では、「AtCoderに登録して最初に解くべき10問(AtCoder Beginners Selection)」の9問目「白昼夢 / Daydream」をめちゃくちゃ分かりやすく解説していきます。

AtCoder で問題を解くためには、新規登録しないといけません。

新規登録はこちらから → AtCoder に新規登録する

 

それでは、「白昼夢 / Daydream」の解説をしていきます!

プログラミング
【競プロ】最初に解くべき過去問10問をPythonで分かりやすく解説します!【AtCoder】こんにちは!サトシ(@satoshi365_blog)です! この記事では、「競技プログラミング(AtCoder)に登録し...

9問目「白昼夢 / Daydream」で身につくスキル

この問題では、こんなスキルが身につきます。

身につくスキル
  • replace() の使い方

先に、これがどのようなスキルなのかを説明します。

 

replace() の使い方

replace() を使うと、ある文字列を他の文字列に書き換えることができます。

例えば、下のように書きます。

a = "12345"
a = a.replace("34", "test")
print(a)   # "12test5" と出力される

9問目「白昼夢 / Daydream」の解説

下の順番で解説していきます。

  • 問題文
  • 入力例と出力例
  • 解答例
  • 解説

それでは見ていきましょう。

 

問題文

 

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

・T の末尾に ‘dream’ ‘dreamer’ ‘erase’ ‘eraser’ のいずれかを追加する。

制約
・1 ≤ |S| ≤ 105
・S は英小文字からなる。

入力
入力は以下の形式で標準入力から与えられる。

S

出力
S = T とすることができる場合 ‘YES’ を、そうでない場合 ‘NO’ を出力せよ。

ABC049C – 白昼夢 / Daydreamより引用

 

入力例と出力例

入力例

dreameraser

出力例

YES

‘dream’、’eraser’の順番でTの末尾に追加すれば、’dreameraser’が作れるので、「YES」と出力します

 

解答例

s = input()
s = s.replace('eraser', '')
s = s.replace('erase', '')
s = s.replace('dreamer', '')
s = s.replace('dream', '')
if s:
  print('NO')
else:
  print('YES')

解説

空文字列Tに ‘dream’ ‘dreamer’ ‘erase’ ‘eraser’ を追加して、S=Tとすることができるということは、Sから ‘eraser’ ‘erase’ ‘dreamer’ ‘dream’ を消していくと、空文字にできるということです。

しかし、順番が大事で、次の順番で消していかないといけません。

  1. ‘eraser’
  2. ‘erase’
  3. ‘dreamer’
  4. ‘dream’

 

例えば、S=’dreameraser’ という文字列を考えます。

上の順番で文字列を無くしていくと、下のようになります。

  1. S=’dreameraser’
  2. S=’dream’
  3. S=”

「Sを空文字にできた」ので、空文字列Tに ‘dream’ ‘dreamer’ ‘erase’ ‘eraser’ を追加して、S=Tとすることができます。(’dream’、’eraser’の順番で追加すればいい)

※試しに ‘dreamer’ から無くしてみると、S=’raser’ となり、うまくいきません。

 

では、コードを詳しく解説していきます。

 

まずは、入力を受け取ります。

s = input()

 

先ほど説明した順番で、文字列を無くしていきます。

s = s.replace('eraser', '')
s = s.replace('erase', '')
s = s.replace('dreamer', '')
s = s.replace('dream', '')

 

 

sに何か文字が残っているときは「NO」と出力します。

※空文字列”はFalseと同じように扱われます。

if s:
  print('NO')

 

sに文字が残っていないときは、「YES」と出力します。

else:
  print('YES')

 

 

まとめとして、もう一度プログラムを確認してみましょう。

s = input()
s = s.replace('eraser', '')
s = s.replace('erase', '')
s = s.replace('dreamer', '')
s = s.replace('dream', '')
if s:
  print('NO')
else:
  print('YES')

これで「N枚のお札で、合計Y円になる可能性があるか」を調べることができました。

まとめ

もし分からない点などありましたら、気軽にTwitterやコメントなどでご質問ください^^

少しでも参考になれば嬉しいです!

POSTED COMMENT

  1. mokkey より:

    replace() の使い方
    例題の出力が間違っています!

    • サトシ より:

      本当ですね、気がつきませんでした >_<
      ’12test45′ → ’12test5’に修正させていただきました!

      ご指摘ありがとうございました^^

COMMENT

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です