roiti46's blog

主に競プロ問題の解説を載せてます

AOJ 1315: Gift from the Goddess of Programming

よく読むと簡単だった。問題はこちら

問題

プログラミングの女神様とプログラマーの人たちの、ある部屋への入出記録が与えられる。記録は複数日にわたることもあるが、毎日00:00には部屋にはだれもいなくなっている。女神様と同じ部屋に一緒にいた時間の合計がもっとも長いプログラマーの、その一緒にいた時間を答える。

解法

1日ごとに部屋にいる人間の数が0人からはじまるので、じつは日付を区別する必要はない。単純に今誰が部屋にいるかと、いつから部屋にいるかを管理して、退室があるごとに女神様と一緒にいた時間を計算してやればいい。

while 1:
    n = int(raw_input())
    if n == 0: break
    exist = set([])
    enter = [0]*1000
    bless = [0]*1000
    for loop in xrange(n):
        md,hm,io,p = raw_input().split()
        h,m = map(int,hm.split(":"))
        t = 60*h+m
        p = int(p)
        if io == "I":
            enter[p] = t
            exist.add(p)
        else:
            exist.remove(p)
            if p == 0:
                for i in exist: bless[i] += t-max(enter[p],enter[i])
            elif 0 in exist:
                bless[p] += t-max(enter[0],enter[p])
    print max(bless)
広告を非表示にする