「え、妻が松江?」松江Ruby会議07協賛 回文作成プログラミングコンテスト|POH6+
https://paiza.jp/poh/joshibato/matsue-ruby
■問題の要約
・回文に必要な文字列を入力してくる。
・一度目の入力は何回文字列を何回入力するかの数値。値は1以上1000以下
・二度目以降の入力は文字列が入力される
入力される文字列の条件として、1文字以上10文字以下。
また、テストケース毎に文字列の長さは固定。
・入力条件として必ず回文が成立する文字列が入力される
つまり、最低入力は1回でその文字列は必ず単品回文。「aba」や「oo」等
中央が無い場合の最低入力は二回で必ず対になる。「abc」「cba」等
・オフレコな条件を追加すると
中央文字は複数回くる可能性がある。
中央文字は1種類しかない。
中央文字はは毎回あるわけではない。
その逆で中央文字しかない場合もある。
最終テストケースは無論最大値、1000入力の文字列の長さは10。
今回は没案だけを紹介します
Python 174byte
l=[];c=a="";w=raw_input for n in range(int(w())):l+=[w()];l.sort while l!=[]: o=l[0];del(l[0]);t=o[::-1] if t in l:a=a+o;l.remove(t) elif t==o:c=t print(a+c+a[::-1])
ちなみにraw_inputをinputにすればPython3で処理可能。
ただし、処理速度はPython2xの方が早い(少なからずあのサイトでは)。
では、何をどう処理するのか?
■for n in range(int(w())):l+=[w()];l.sort
まずリスト(いわゆる配列)の生成。そして最後にソート。
これによりソートされたリストを取得できます。
■while l != []:
while条件はリストの中身が空になるまで行います。
つまり消込型です。有意点は処理が進むほど高速になります。
■o=l[0];del(l[0]);t=o[::-1]
先ずリストの0番目を取得し、そのままリストの0番目の要素を削除。
これにより中央strであった場合でも自身が検索対象になりません。
それと同時に文字の逆順を【 o[::-1] 】で取得しています。
■if t in l:a=a+o;l.remove(t)
ifの条件はlのリストの中にt(逆順文字)があるか?です。
有る場合この時点で回文の左文字列として結合していきます。
さらに【l.remove(t)】で逆文字の要素を削除します。
removeは最初に出てくる要素を消す為リストで複数回出現しても個々に処理されます。
■elif t==o:c=t
左文字列ではない場合において自身単品が中央文字列(回文)かをチェックします。
ここで回文として成立する文字列は必ず1つしかありません。
今回は中央の種類が1つしかない事前提になっている為若干邪道ではあります。
■print(a+c+a[::-1])
最後に出力しておしまいです。
それで今回の落ちなのですが、うまく行ったコードより、こちらの方が高速だろうと書いたこっちが4以降のテストケースでタイムアウトするっぽいと言う話。
「おめでとうございます!でも大きいサイズのデータではタイムアウトしてしまうようです。全テストケースクリア目指してみましょう!」
ですって。
0 件のコメント:
コメントを投稿