最終更新日が2023年以前の記事です。レイアウト変更のため、正常に表示されない場合があります。
こんなことして何になるの？って聞かれそうな機械を作りました。
↑これを見た時にふと思いついた。
Contents
英文元素記号分解機
使用上の注意
- 英語の大文字小文字は問いませんが、カンマやピリオドなどの記号は対応していませんので取り除いてください。
- スペースはすべて勝手に取り除かれます。
- 結果に表示されるのは可能な分解パターンのひとつです。全ての分解パターンを網羅するわけではありません（例えば、”cu”という文字列は2通りの分解パターンがありますが、表示できるのはそのうちの1通りだけです）。あくまで分解可能性を判定するだけです。
- もちろん英語以外の文字を入れると壊れます。
動作原理
競プロの基礎問題のひとつを思い出したかもしれませんが、あれとはちょっと性質が違うのであの解法では解けません。
英小文字からなる文字列 \(S\) が与えられます。
\(T\) が空文字列である状態から始めて、以下の操作を好きな回数繰り返すことで \(S=T\) とすることができるか判定してください。https://atcoder.jp/contests/abs/tasks/arc065_a?lang=ja
- \(T\) の末尾に “dream”, “dreamer”, “erase”, “eraser” のいずれかを追加する。
この問題はTを前から拾ってもどの単語の部分列であるかが特定できないけど後ろから拾えば特定できるよ、というお話でした。でも元素記号で分解する場合は前から拾っても後ろから拾っても特定不可能です。（たとえば”AGACO”という文字列を後ろから拾っても、末尾のOが1文字のOなのかCoのOなのか特定できません）
そこで全く違う解き方をします。ここでは、元素記号は全て1文字か2文字であるという性質に着目します。
まず、全ての文字は以下のステータスを持ちます。ここでいう「使用可能」とは、元素記号として成立しているので文字列分解した時のパーツとして使える、という意味です。また「連結可能である」というのは２文字を合わせた時に元素記号になるという意味です（たとえば、A と U はこの順で連結可能です）。
- 単体で使用可能か
- 他のある文字を前に連結可能か
- 他のある文字を後ろに連結可能か
たとえば、Aであれば以下のような形になります。
- 単体で使用可能か：False
- 他のある文字を前に連結すれば使用可能か：B,C,G,L,N,P,R,T は true
- 他のある文字を後ろに連結すれば使用可能か：c,g,l,m,r,s,t,u はtrue
まず元素記号のリストから26個全ての英文字についてこれを計算しておきます。大した計算量ではないはずです。
次に与えられた文字列を前から走査していき、n番目の文字とn+1番目の文字が連結可能かどうかを判定します。もしここで連結可能でなかった場合、その文字列が分解可能であった時にはそこに必ず区切りが入るため、文字列を分割しておきます。
この操作で与えられた文字列をいくつかの部分文字列に分割しました。これらの部分文字列はその長さによって偶数長と奇数長（１文字である場合も含む）の２通りに分けられます。
このうち偶数長の部分文字列については、これを前から順に２文字ずつ区切っていくことが可能なので、必ず元素記号に分割可能です。
奇数長の文字列については、前から奇数番目の文字に１つ以上の「単体使用可能な文字」が入っている必要があります。あるxについて前から2x+1番目の文字が単体使用可能な文字であれば、その部分で区切ってやるとその文字より前も後も偶数長の部分文字列が残ることになるので、偶数長の部分文字列の処理に帰結します。
奇数長の文字列の前から奇数番目の文字に単体使用可能な文字が存在しない場合、分解は失敗します。
（そのうち気が向いたら図解します。必要以上に難しく書いてしまったような。）
