paizaオンラインハッカソン6+
「え、妻が松江?」松江Ruby会議07協賛 回文作成プログラミングコンテスト|POH6+
https://paiza.jp/poh/joshibato/matsue-ruby
前回に引き続き例の回文です
Python 200byte
結果:https://paiza.jp/poh/joshibato/matsue-ruby/result/76d98589
Test case 1 通過 実行時間: 0.02 秒
Test case 2 通過 実行時間: 0.02 秒
Test case 3 通過 実行時間: 0.02 秒
Test case 4 通過 実行時間: 0.03 秒
Test case 5 通過 実行時間: 0.03 秒
元々こっちの案で作ってたやつですね。
といっても基本的な処理はおなじで消込型です。
■for n in r:l+=[w()];
先ずは入力される文字の読み込み、リスト(いわゆる配列)を生成
■l.sort()
リストをソート
■for i in r:
Pythonのforは処理構造がforeach文のそれです。
「r」には最初にrangeで生成した整数の連番が入ったリストが入っており順次「i」カウンタへ格納されていきます。
■k=l[i];t=k[::-1];l[i]=""
「k」に文字列を格納。「t」にはリバース文字列を格納。最後に配列を空文字列に。
■if k != "":
格納された文字が空でない場合のみ処理
■if t in l:m=m+k;l[l.index(t)]=""
「l」のリストからリバース文字列「t」があるか調べある場合、左文字列として追加。
同時に対になるリストを空文字に置き換えます。
indexはその要素が最初に出てくる番号を返します。
このリストで複数回出現しても個々に処理されます。
■elif k==t:c=k
単品でありなおかつ文字列とリバース文字列が一致数る場合中央文字が確定します。
一種類しかない事前提なので若干邪道かもしれません。
■print(m+c+m[::-1])
最後に出力しておしまいです。
「	」
2015年9月30日水曜日
2015年9月29日火曜日
回文処理没案!
paizaオンラインハッカソン6+
「え、妻が松江?」松江Ruby会議07協賛 回文作成プログラミングコンテスト|POH6+
https://paiza.jp/poh/joshibato/matsue-ruby
■問題の要約
・回文に必要な文字列を入力してくる。
・一度目の入力は何回文字列を何回入力するかの数値。値は1以上1000以下
・二度目以降の入力は文字列が入力される
入力される文字列の条件として、1文字以上10文字以下。
また、テストケース毎に文字列の長さは固定。
・入力条件として必ず回文が成立する文字列が入力される
つまり、最低入力は1回でその文字列は必ず単品回文。「aba」や「oo」等
中央が無い場合の最低入力は二回で必ず対になる。「abc」「cba」等
・オフレコな条件を追加すると
中央文字は複数回くる可能性がある。
中央文字は1種類しかない。
中央文字はは毎回あるわけではない。
その逆で中央文字しかない場合もある。
最終テストケースは無論最大値、1000入力の文字列の長さは10。
今回は没案だけを紹介します
Python 174byte
ちなみに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以降のテストケースでタイムアウトするっぽいと言う話。
「おめでとうございます!でも大きいサイズのデータではタイムアウトしてしまうようです。全テストケースクリア目指してみましょう!」
ですって。
「え、妻が松江?」松江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以降のテストケースでタイムアウトするっぽいと言う話。
「おめでとうございます!でも大きいサイズのデータではタイムアウトしてしまうようです。全テストケースクリア目指してみましょう!」
ですって。
登録:
投稿 (Atom)