AtCoder ABC 080 D - Recording (Go) - あるエンジニアのAtCoder奮闘記

irisruneです。先週はコンテストがなかったので今週は過去問を扱います。

問題

一見関係のないように見える要素も実際は必要になってくる問題です。

package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
)

var sc *bufio.Scanner

func nextStr() string {
    sc.Scan()
    return sc.Text()
}

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

type event struct {
    time    int
    mode    string
    channel int
}

type events []event

func (e events) Len() int {
    return len(e)
}

func (e events) Swap(i, j int) {
    e[i], e[j] = e[j], e[i]
}

func (e events) Less(i, j int) bool {
    return e[i].time < e[j].time
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n, _ := nextInt(), nextInt()
    var events events = make([]event, n*2)
    for i := 0; i < n; i++ {
        s, t, c := nextInt(), nextInt(), nextInt()
        events[i*2] = event{s*2 - 1, "start", c}
        events[i*2+1] = event{t * 2, "end", c}
    }
    sort.Sort(events)
    ans := 0
    channels := make(map[int]int)
    for _, e := range events {
        switch {
        case e.mode == "start":
            _, ok := channels[e.channel]
            switch {
            case ok:
                channels[e.channel]++
            default:
                channels[e.channel] = 1
                if len(channels) > ans {
                    ans = len(channels)
                }
            }
        case e.mode == "end":
            channels[e.channel]--
            if channels[e.channel] == 0 {
                delete(channels, e.channel)
            }
        }
    }
    fmt.Println(ans)
}

直感的に、各時刻について同時に放送される番組数が最大となるときを考えると、そのときの番組数が解となります。しかし時刻の最大値 $T'\leq10^5$ であるため、計算量 $O(NT')$ となるようなアルゴリズムでは実行時間が足りません。そこで、番組の開始と終了をそれぞれイベントとして考えると、イベントを時刻でソートした配列について先頭から順番に見ていくことで同時に放送される番組数の推移を追うことができます。イベント数は $2N$ であるため実行時間的にも問題ありません。

具体的なアルゴリズムとしては、以下の通りになります。

番組の開始イベントについては発生時刻を $2s_i-1$ 、終了イベントについては発生時刻を $2t_i$ とおく。
$2N$ 個のイベントを発生時刻でソートした配列をおく。
配列の先頭からチェックし、開始イベントであれば増やし、終了イベントであれば番組数を減らす。
番組数の推移から最大値を求める。

しかしこれではWAとなってしまいます。どういうことかといえば、ここまで~~不要だと思っていたので~~着目していなかったチャンネルが関係してきます。問題文には以下のように示されています。

また、録画機は、あるチャンネルの時刻 $S$ から $T$ までを録画するとき、時刻 $S-0.5$ から時刻 $T$ までの間、他のチャンネルの録画に使うことができません。（ただし時刻 $S-0.5$ を含み、時刻 $T$ を除く）

よく読むと他のチャンネルの録画に使うことができないとしか書いておらず、同じチャンネルの録画に使うことはできるのです。実は入出力例1でも、時刻 $7$ から $8$ までの番組と時刻 $8$ から $12$ までの番組を同じ録画機で録画できることが示されています。つまり求めるべきは同時に放送される番組の数ではなく、同時に放送されるチャンネルの数となります。それを踏まえ上記アルゴリズムに多少の変更を加えれば解くことができました。