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

naoya_t@hatenablog

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

SRM583 (new compilers) DIV 1

TopCoder Single Round Match Practice Room 過去問探訪 Python

Practice Roomsの#893にそんなタイトルのがあったので覗いてみる。
問題はSRM583と同じで、コンパイラが昨日のTest SRMと同様の構成らしい。Pythonが使えるのでPythonで書いてみようか。

Easy ("TravelOnMars2", 250)

passed system test.
C++の時よりテストに時間がかかる印象。

def nxn(n, initial):
    return [[initial]*n for i in range(n)]

import Queue
INFTY = 999999

def dijkstra(a, start):
    n = len(a)
    pq = Queue.PriorityQueue()
    pq.put((0, start))
    distance = [INFTY]*n
    while not pq.empty():
        d, curr = pq.get()
        if distance[curr] <= d: continue
        distance[curr] = d
        for nxt in range(n):
            if nxt == curr: continue
            d_ = d + a[curr][nxt]
            if d_ < distance[nxt]:
                pq.put((d_, nxt))
    return distance

class TravelOnMars2:
    def minTimes(self, range_, startCity, endCity):
        n = len(range_)
        a = nxn(n, INFTY)
        for i, r in enumerate(range_):
            for o in range(-r, r+1):
                i_ = (i + o + n*50) % n
                a[i][i_] = 1
        distance = dijkstra(a, startCity)
        return distance[endCity]

if __name__ == '__main__':
    tom = TravelOnMars2()
    assert(2 == tom.minTimes([2,1,1,1,1,1], 1, 4))
    assert(3 == tom.minTimes([2,1,1,2,1,2,1,1], 2, 6))
    assert(4 == tom.minTimes([3,2,1,1,3,1,2,2,1,1,2,2,2,2,3], 6, 13))
    assert(5 == tom.minTimes([2, 4, 2, 3, 4, 1, 4, 2, 5, 4, 3, 3, 5, 4, 5, 2, 2, 4, 4, 3, 3, 4, 2, 3, 5, 4, 2, 4, 1, 3, 2, 3, 4, 1, 1, 4, 4, 3, 5, 3, 2, 1, 4, 1, 4], 24, 8))