E - Takahashi Quest

[hxrxchang]

https://atcoder.jp/contests/abc333/tasks/abc333_e

問題概要

高橋くんが冒険中に2種類のN個のイベントと遭遇する。

• t=1のときタイプxのポーションを1つ発見する。高橋くんは拾うか捨てるかどちらかをする。
• t=2のときタイプxのモンスターと遭遇する。タイプxのポーションを使うことでモンスターを倒せる。持っていなかったら敗北する。

高橋くんが敗北する場合-1を出力せよ。 高橋くんが勝つ場合、高橋くんが所持するポーションの数が最小となるような個数Kを求めよ。また、各t=1のとき拾う場合は1を拾わない場合は0を出力せよ。

解き方

t = 1のときそのポーションを使うかどうかは、自分より後に同じタイプのモンスターがいるかどうかを知る必要があるが、それを判定するにはO(N ** 2)かかってしまう。 そこで、queriesを後ろから見ていき、モンスターが登場した後に一番早く登場した同じタイプのポーションを使うようにするとO(N)でそのポーションを使うかどうか決定できる。 使うポーションは後ろから見ていったときの最新、言い換えると前から見た場合に同じタイプのモンスター登場の直前のものを貪欲に選んで行って問題ない。

1 1
1 1
2 1

というクエリだったら最初のポーションでも2番目のポーションでもどちらでもいいが、簡単のために2番目(同じタイプのモンスター登場の直前のものを使う)でいいということだ。 使うポーションが決まれば、全イベント中の所持ポーション数を

• 今まで持っていたポーション数の最大を記録する変数 cnt を用意
• 今現在持っているポーション数を記録する変数 tmp を用意
• クエリを前から見ていき、使うポーションだったら tmp をカウントアップ。一緒に tmpがcntを上回る場合は cnt を tmpにする
• モンスターが現れたらtmpをカウントダウン

という計算で算出できる。

type Query struct {
    t, x int
}

func solve() {
    n := getInt()

    queries := make([]Query, n)
    for i := 0; i < n; i++ {
        in := getInts()
        t, x := in[0], in[1]
        queries[i] = Query{t, x}
    }

    queries2 := reverse(queries)
    monsters := make(map[int]int)
    choicedPortions := newSet[int]()

    for i, query := range queries2 {
        t, x := query.t, query.x
        if t == 2 {
            monsters[x]++
        } else {
            if monsters[x] > 0 {
                monsters[x]--
                choicedPortions.add(n - i - 1)
            }
        }
    }

    monstersCnt := 0
    for _, v := range monsters {
        monstersCnt += v
    }
    if monstersCnt > 0 {
        fmt.Println(-1)
        return
    }

    tmp := 0
    cnt := 0
    viewData := make([]int, 0)

    for i, query := range queries {
        if query.t == 1 {
            if choicedPortions.has(i) {
                viewData = append(viewData, 1)
                tmp++
                cnt = max(cnt, tmp)
            } else {
                viewData = append(viewData, 0)
            }
        } else {
            tmp--
        }
    }

    fmt.Println(cnt)
    fmt.Println(sliceToStr(viewData, " "))
}

https://atcoder.jp/contests/abc333/submissions/55353318