競技プログラミング

ABC049C – 白昼夢

https://atcoder.jp/contests/abs/tasks/arc065_a

この問題では、文字列Sが与えられ、その文字列が4つの特定の文字列を繰り返し使用して形成できるかどうかを判定します。その4つの文字列は “dream”, “dreamer”, “erase”, “eraser” です。

まず、逆順に問題を考えることで解決を容易にします。つまり、Sを逆順に読み、4つの文字列も逆順にして考えます。これにより、Sの先頭から順に読んで行くだけで、どの文字列が適用可能かを判定することが可能になります。

この問題のコードは以下のような流れで進みます。

  1. 文字列Sを逆順にしたものを配列として取得します。これは let S = Array(readLine()!.reversed()) の部分です。
  2. 判定に使用する4つの文字列も逆順にして配列として格納します。これは let words = ["dream", "dreamer", "erase", "eraser"].map { Array($0.reversed()) } の部分です。
  3. Sの先頭から順に4つの文字列と比較していきます。比較は if S[index..<index + word.count] == ArraySlice(word) { の部分で行っています。ここで index はSの現在の位置を指し、word.count は現在比較している文字列の長さを表します。もし一致すれば、indexをその文字列の長さ分だけ進めます。
  4. 一致する文字列がなければ、NO を出力して終了します。
  5. 全てのSを比較し終えた(つまり index がSの長さと同じになった)時点で、YES を出力します。全てのSを比較し終えていない場合は NO を出力します。

以上がこの問題のSwiftによる解法になります。この解法は「貪欲法」や「グリーディアルゴリズム」と呼ばれるアルゴリズムを使用しており、各ステップで最適な選択を行うことで最終的な解を求めています。

以下にそのコードを示します。

func canFormDreamSequence() {
    let S = Array(readLine()!.reversed())
    let words = ["dream", "dreamer", "erase", "eraser"].map { Array($0.reversed()) }
    var index = 0

    while index < S.count {
        var matched = false
        for word in words {
            if S[index..<index + word.count] == ArraySlice(word) {
                index += word.count
                matched = true
                break
            }
        }
        if !matched {
            print("NO")
            return
        }
    }

    if index == S.count {
        print("YES")
    } else {
        print("NO")
    }
}

canFormDreamSequence()

COMMENT

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