unratedなSRMがあったので出てみた。
The solutions are executed at Amazon EC2 m1.medium VMs.
Compiler versions:
C++ – g++ (GCC) 4.4.6 20110731 (Red Hat 4.4.6-3)
Compilation options: --std=c++0x -W -Wall -Wno-sign-compare -O2 -s -pipeJava – java version "1.7.0_17"
Python – Python 2.6.6
C# – .NET Framework 4.0, Microsoft (R) Visual C# 2010 Compiler version 4.0.30319.1
VB – .NET Framework 4.0, Microsoft (R) Visual Basic Compiler version 10.0.30319.233
|
Pythonが言語選択肢に入っているので（そしてunratedなので）今日はPythonで解いてみることにした。2.6.6かよ。
結果
Test SRM (Div.1) oo- 429.56pt (Rank 20), unrated. まさかの部屋1位 #Python参戦SRM
— naoya t (@naoya_t) 2013, 7月 1Div1全体で205人（人数少な！）中20位。Python勢では1位。
Easy ("PalindromeMaker2", 250)
とりあえず通ったけれど、Cで考えてる感じのコードになってる。全くPythonらしい書き方ができてない。[::-1] とかさらっと使えるようになりたい。
218.27 (11'9'') AC
以下提出コード。
if __name__ == '__main__': 以下は提出時に削除。
class PalindromeMaker2:
def __init__(self):
pass
def make(self, baseString):
t = [0]*26
for c in baseString:
t[ord(c) - 65] += 1
odds = []
for i in range(26):
if t[i] % 2 != 0:
odds.append(i)
if len(odds) > 1:
return ''
for i in range(26):
t[i] /= 2
res = []
for i in range(26):
for j in range(t[i]):
res.append(chr(65+i))
ans = ''.join(res)
if len(odds) == 1:
ans += chr(65+odds[0])
res.reverse()
ans += ''.join(res)
return ans
if __name__ == '__main__':
pm = PalindromeMaker2()
print pm.make("AABB")
print pm.make("AAABB")
print pm.make("ABACABA")
print pm.make("ABCD")
Medium ("WebsiteRank2", 500)
トポロジカルソート関数をぐぐってコピペしてる件…
↑Pythonがビルトインで持っててくれてもいいよねそれくらい！
コピペしてきた toposort2() 関数の中で（2.6.xでは使えない）辞書内包表記が使われていて、ローカル（2.7.3）では通るのにsubmit前にサーバ側（2.6.6）でtestしたら全部1が返っていたのでそれを修正するのに時間がかかった。
コピペ元はこれね
http://code.activestate.com/recipes/578272-topological-sort/
211.29 (51'28'') AC
Mediumは撃墜大会だった。参戦してないけど。
部屋 (Room9) でACは自分だけ。
cafelierさんのPythonコードが（WAらしいけど）すごくシンプルでかっこいいなと思った。
以下提出コード。
if __name__ == '__main__': 以下は提出時に削除。
import Queue
from functools import reduce
def toposort2(data):
for k, v in data.items(): v.discard(k)
extra_items_in_deps = reduce(set.union, data.itervalues()) - set(data.iterkeys())
# data.update({item:set() for item in extra_items_in_deps})
d = {}
for item in extra_items_in_deps: d[item] = set()
data.update(d)
while True:
ordered = set(item for item, dep in data.iteritems() if not dep)
if not ordered: break
yield ordered
# data = {item: (dep - ordered)
# for item, dep in data.iteritems()
# if item not in ordered}
data_ = {}
for item, dep in data.iteritems():
if item not in ordered:
data_[item] = (dep - ordered)
data = data_
assert not data, "Cyclic dependencies exist among these items:\n%s"
class WebsiteRank2:
def __init__(self):
pass
def countVotes(self, votes, website):
# tuple(string) -> string -> long integer
s = set()
paths = []
for vote in votes:
sites = vote.split(' ')
to = sites[0]
s.add(to)
for fr in sites[1:]:
paths.append((fr, to))
s.add(fr)
allsites = list(s)
allsites.sort()
arcs = {}
for fr, to in paths:
arcs[fr] = arcs.get(fr, []) + [to]
reach = {}
for site in allsites:
v = set()
q = Queue.Queue()
q.put(site)
while not q.empty():
fr = q.get()
if fr in v: continue
v.add(fr)
for to in arcs.get(fr, []):
if to not in v: q.put(to)
v.remove(site)
reach[site] = list(v)
graph = {}
for site in allsites:
tos = arcs.get(site, [])
for to in tos:
if site not in reach[to]:
s = graph.get(site, set())
s.add(to)
graph[site] = s
if len(graph) == 0: return 1
scores = {}
for site in allsites:
scores[site] = 1
xs = [x for x in toposort2(graph)]
xs.reverse()
for s in xs:
for fr in s:
for to in graph.get(fr, set()):
scores[to] += scores[fr]
return scores.get(website, 0)
if __name__ == '__main__':
wr = WebsiteRank2()
print wr.countVotes({"C A B"}, "C") # 3
print wr.countVotes({"A B C D", "B C D", "C D"}, "A") # 8
print wr.countVotes({"A"}, "A") # 1
print wr.countVotes({"A B", "B A"}, "A") # 1
print wr.countVotes({"A B C D E F", "B A", "C B", "D B"}, "A") # 3
print wr.countVotes({"MYSITE OTHERSITE ANOTHERSITE THIRDSITE"}, "MYSITE") # 4