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月 1
Div1全体で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