Sony GO FOR IT 5) 申告制エレベータ

i)

# coding: utf-8
# ライセンス：このプログラムは好きに使ってください

import sys

# 利用者
class user:
    def __init__(self,id_,t_,s_,g_):
        self.id,self.t,self.s,self.g = id_,t_,s_,g_
    def __repr__(self):
        return "user(%d,%d,%d,%d)"%(self.id,self.t,self.s,self.g)

# 入力
U = [user(*map(int,l[:-1].split(","))) for l in sys.stdin]

es = 1      # エレベータのある階
et = 0      # 直前の動作の時刻
ed = "E"    # 扉の状態
eu = []     # 乗員
up = 0      # user[up]を次に運ぶ

while up<len(U):
    u = []  # 乗り降りする利用者
    if ed=="E":
        # 扉が閉じているなら開ける
        ed = "B"
        if eu==[]:
            # 乗員がいなければ次の利用者のいる階
            s = U[up].s
        else:
            # 乗員がいるなら乗員の目的階で扉を開ける
            s = U[eu[0]].g
            u = [U[eu[0]].id]
            eu = []
            up += 1
        et += abs(s-es)*2
        es = s
    else:
        # 扉が開いているなら閉じる
        ed = "E"
        if U[up].s==es:
            # 待っている利用者がいる
            u = [U[up].id]
            eu = [up]
            et = max(et+5,U[up].t)
        else:
            # 待っている利用者がいない
            et += 5
    u += [0]*(5-len(u))
    print "1,%s,%s,%s,%s,%s,%s,%s,%s"%(et,es,ed,u[0],u[1],u[2],u[3],u[4])

ii)

JavaScriptでエレベータの動きを可視化した。

http://sanya.sweetduet.info/goforit/5_2.html

iii)

（A*ではなく）ダイクストラ法。input_i.csvは解けるけど、input_iii_iv.csvは解けないorz

# ライセンス：このプログラムは好きに使ってください。
# coding: utf-8

import sys
import copy
import heapq

# 利用者
class user:
    def __init__(self,i,t,s,g):
        self.id,self.time,self.start,self.goal = i,t,s,g
    def __repr__(self):
        return "user(%d,%d,%d,%d)"%(self.id,self.time,self.start,self.goal)

# 入力
U = [user(*map(int,l[:-1].split(","))) for l in sys.stdin]

# 状態
class state:
    def __init__(self):
        self.C = 0          # コスト
        self.H = sum(u.time for u in U) # ヒューリスティック
        self.time = 0       # 時刻
        self.floor = 1      # エレベータのある階
        self.door = "E"     # 扉の状態（E:閉, B:開)
        self.elev = []      # エレベータに乗っている利用者
        self.remain = (1<<len(U))-1 # エレベータに乗る前の利用者
        self.count = len(U) # エレベータに乗る前＋エレベータに乗っている利用者数
        self.flag = False   # 扉が開いたときに利用者が降りたかどうか
        self.prev = None    # 直前の状態
        self.edge = ""      # 直前の状態からの遷移方法
    def __lt__(self,other):
        return self.C+self.H < other.C+self.H
    def __repr__(self):
        return "state(%s,%s,%s,%s,%s,%s)"%(self.C,self.time,self.floor,self.door,self.elev,self.count)
    def __copy__(self):
        s = state()
        s.C = self.C
        s.time = self.time
        s.floor = self.floor
        s.door = self.door
        s.elev = self.elev[:]
        s.remain = self.remain
        s.count = self.count
        s.flag = self.flag
        return s

S = [state()]

c = 0
while len(S)>0:
    s = heapq.heappop(S)
    
    if s.count==0:
        goal = s
        break
    c += 1
    if c%1000==0:
        print c,len(S),s
    
    if s.door=="E":
        # 扉が閉じているなら、どこかの階で開く
        for floor in range(1,11):
            # 与えられている入力なら問題無い
            if floor==s.floor:
                continue
            
            t = copy.copy(s)
            time = abs(floor-s.floor)*2 # 所要時間
            t.C += t.count*time
            t.H = 0
            t.time += time
            t.floor = floor
            t.door = "B"
            
            # この階が目的の利用者を降ろす
            u = []
            t.elev = []
            t.flag = False
            for x in s.elev:
                if U[x].goal==floor:
                    u += [x+1]
                    t.count -= 1
                else:
                    t.elev += [x]
            t.flag = u!=[]
            
            t.prev = s
            u += [0]*(5-len(u))
            t.edge = "1,%s,%s,B,%s,%s,%s,%s,%s"%(t.time,floor,u[0],u[1],u[2],u[3],u[4])
            
            heapq.heappush(S,t)
    else:
        # 扉が開いているなら5秒もしくは5秒以上で利用者が来るまで待って閉じる
        for time in [5]+[u.time-s.time for u in U if u.time>s.time+5 and u.start==s.floor]:
            t = copy.copy(s)
            t.C += t.count*time
            t.H = 0
            t.time += time
            t.door = "E"
            
            # 乗車可能な利用者を乗せる
            u = []
            for i,ui in enumerate(U):
                if t.remain>>i&1 and ui.time<=t.time and ui.start==t.floor:
                    t.elev += [i]
                    t.remain ^= 1<<i
                    u += [i+1]
            
            t.prev = s
            u += [0]*(5-len(u))
            t.edge = "1,%s,%s,E,%s,%s,%s,%s,%s"%(t.time,t.floor,u[0],u[1],u[2],u[3],u[4])
            
            if t.flag or u!=[0]*5:
                heapq.heappush(S,t)

hist = []
x = goal
while x.prev:
    hist += [x.edge]
    x = x.prev
for h in hist[::-1]:
    print h
print goal.C - sum(u.time for u in U)