[Swift]AtCoderの初心者向け練習問題「白昼夢」で相当苦戦している
私事ではあるが、今回で記念すべき30本目の投稿である。4月12日から少なくとも一本の記事を毎日投稿し続けているのだが、ここまで長続きして投稿出来ていることに自分でも驚いている。
いつもはSwiftのエラーに対する解決策・新機能開発のことを投稿したり、Blenderで困った操作とかをまとめて投稿しているのだが、今回は体験談？みたいなものを初めて投稿しようと思う。
実は先月より、競技プログラミングのAtCoderというサイトに登録し、競技プログラミングを始めた。始めた理由はいろいろあるのだが、それはまたいつか投稿できたらいいなと思っている。
AtCoderには登録したてのビギナーのための問題が用意されており、ビギナーの多くはこの問題で競プロデビューする。
ところがこの初心者用問題、いろいろと曲者。
AtCoderの問題は難易度によってA問題、B問題、C問題とラベリングされているのだが、このC問題がまあ難しい。A問題・B問題は1日~2日あれば簡単に解けるのだが、C問題の一つ「白昼夢」は、執筆時点で解くのに4日かかっている。（たぶんもっとかかる）
なにが難しいのか
英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。
T の末尾に dream dreamer erase eraser のいずれかを追加する。
問題文は上記の通り。一見簡単な問題に見える。
最初に思い付いた方法
最初に取り組んだ解法は「入力文字列を1文字ずつ区切って, n+1文字がTの文字に該当するかしないか」という判定方法。実装自体はswitch文を使って、案外すんなりいけた。
ところがこの方法だと
dreamerer //OK
erasererase //NGと出力される。（当然WA：Wrong Answer）
「er」という文字列が「dreamer」なのか「eraser」なのかその判定が大変。この問題の難しさを認識した。
次に思い付いた方法
ggればSwiftの答えを書いてくれている人がいるんだけど（ありがたい）
自分の掲げている目標の一つに「コードをそのままコピペしない」という目標を掲げており、上記の方法は参考にしない。
while let word = words.first(where: { S.hasSuffix($0) }) {
S.removeLast(word.count)
}また上記には、SwiftAPIに標準で搭載されているAPIを使う解法があるのだけれど、下の記事では、
nums.firstIndex(where: {$0 == target})
ただし、こちらを使用するのは競技プログラミングにおいては反則のようなものなので、アルゴリズムを使ったものを見ていきましょう。
（用意されたAPIを使用して解いてしまっては、アルゴリズムの勉強にならないので）
と一蹴されている。
なので、この配列のfirst（Index）をwhereで絞って一致するか、hasSuffixを使って末尾が合致しているか、みたいな処理はあまり使いたくない。（たぶんこの問題の要旨は10^5乗データを”探索を使って”、いかにシンプルにかつ実行速度を早く処理するか、ってことなのでAPI使ってサクッとACするみたいなのは違う気がする）
次に思い付いた方法は、C++の回答例をSwiftに翻訳したらどうなるだろうか、と考えたり、探索について調べたりしたが、まだ自分は頭が悪いからよく理解できなかった。
個人的にはSwiftで正規表現を用いて、正答誤答判定をしている人が一番賢いと思った。どうしようもなくなったら、この方法を使って実装しようと考えている。
今実装している方法
とはいえ、配列を逆順にして末尾から検索すると一意に定まるという考え方は非常に有益な収穫であった。
配列とSをreverseする
Sの文字ごとに配列を回して S[i]==T[j]配列の文字に合致するか
全文字全通り試す
みたいな流れで実装していくことが必要
なお結果はTLE。（AC*11, TLE*8）
1≦∣S∣≦10 ^ 5
S は英小文字からなる。
おそらく10^4, 10^5のデータだと実行速度が2000ms超えないと処理できないので、上記3でいかに探索方法をシンプルにするか考える必要がある。
正直Blenderでも開発でもやりたいことが山ほどあるので、この問題に使える時間もそんなにないが、これが終わらないと前に進めないので、早く終わらせられるように頑張りたい。