読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

いわゆるチラシノウラであります

Test SRM

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 -pipe

Javajava version "1.7.0_17"
PythonPython 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かよ。

結果


Div1全体で205人(人数少な!)中20位。Python勢では1位。
f:id:n4_t:20130702110823p:plain

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