Yandex.Algorithm Open 2011 Qualification 1
はい。
http://codeforces.com/contest/81
A. Plug-in
implementation
ざっくりと大意
・2つ同じ文字が並んでるのをひたすら取り除く。
方針のようなもの
・例えばサンプルのように'allaz'と並んでいるとllを取り除いたあとにaaが2つ並ぶ。ただひたすら前に見ていくと残してしまい何周も探し直しが必要になる。
・本日も自力では解けず。。
#!/usr/bin/env python # -*- coding: UTF-8 -*- #test20でTLEが解決できないメモ import time import sys, io import re, math n=raw_input() cnt=1 while cnt<len(n): if cnt>0 and n[cnt]==n[cnt-1]: n=n.replace(n[cnt]*2,'') cnt-=1 elif cnt<len(n)-1 and n[cnt]==n[cnt+1]: n=n.replace(n[cnt]*2,'') else: cnt+=2 print n
・今のチェックポイントと手前が同じなら削除してチェックポイントを手前に戻す。
・今のチェックポイントと一つ先が同じなら削除してチェックポイントはそのまま。
・手前も一つ先も同じ文字でないならチェックポイントを二つ前へ
諦めたので他の人の回答をパクリで、、424121の-dp-さんが
s = raw_input() st = [] for c in s: if st and c==st[-1]: st.pop() else: st.append(c) print ''.join(st)
リストとpopで処理していたのを真似しつつ、strのまま処理で書いたら3,4倍遅かった。。。
#!/usr/bin/env python # -*- coding: UTF-8 -*- n=raw_input() k='' for i in n: if k and i==k[-1]: k=k[:-1] else: k+=i print k
処理の流れとしては多分、
nで受け取って、移し替え用?の空のリストを用意する。
リストの中身があれば最後尾と移し替えしようとしたものを比較。
同じ文字なら最後尾を削除して、かつ移し替えはしない。
同じ文字でなければ最後尾へ移し替える。
この流れでなら'allaz'と並んでいると並んでいる文字列も、
最初にリストは空でそのままaがリストに入る
リスト最後尾はaなのでlがリストに入る
lは同じ文字なのでリストに入った最後尾のlを削除してリストにも何も入れない(この時に最後尾はaに変わる)
aは同じ文字なので(ry