E - Somen Nagashi

[hxrxchang]

https://atcoder.jp/contests/abc320/tasks/abc320_e

問題概要

N人で流しそうめんをしている。 それぞれの人に1~Nの番号が振られて、その順番(昇順)に並んでいる。 M回以下のイベントが起きる。

• 時刻Tに量Wのそうめんが流れる。流れたそうめんは全部先頭の人のものになる。先頭の人は列から離れてS単位時間たったら列の元の場所に戻ってくる。

それぞれのそうめんの獲得量を求めよ。

解き方

意外と簡単。 列に並んでいる中で番号が一番若い人にそうめんを与えればいいので、だれが列の中で一番番号が若いかはheapで管理できる。 時間の経過は1秒ずつ管理すると当然間に合わないから、イベントごとの時間を見て、その時間に待ち時間が過ぎている人を全員戻せばいい。それも待ち時間をheapで管理できる。 待ち時間ごとに誰が待っていたかは普通に待ち時間をkeyにmapで管理できる。

type Event struct {
    t, w, s int
}

func solve() {
    in := getInts()
    n, m := in[0], in[1]

    events := make([]Event, m)
    for i := 0; i < m; i++ {
        in = getInts()
        events[i] = Event{in[0], in[1], in[2]}
    }

    row := newMyHeap[int]()
    for i := 0; i < n; i++ {
        row.push(i)
    }

    waitingTime := newMyHeap[int]()
    waitingPerson := make(map[int][]int)

    res := make([]int, n)

    for i := 0; i < m; i++ {
        for waitingTime.len() > 0 && waitingTime.heap[0] <= events[i].t {
            t := waitingTime.pop()
            for _, p := range waitingPerson[t] {
                row.push(p)
            }
            waitingPerson[t] = []int{}
        }
        if row.len() > 0 {
            p := row.pop()
            res[p] += events[i].w
            nextBackTime := events[i].t + events[i].s
            waitingTime.push(nextBackTime)
            waitingPerson[nextBackTime] = append(waitingPerson[nextBackTime], p)
        }
    }

    for i := 0; i < n; i++ {
        fmt.Println(res[i])
    }
}

https://atcoder.jp/contests/abc320/submissions/54931947