D - Draw Your Cards

[hxrxchang]

https://atcoder.jp/contests/abc260/tasks/abc260_d

問題概要

山札に数字が書かれたカードがある。 一番上からカードを引いて、

• 引いたカードより大きい数字が書かれたカードが置かれていたら、自分より大きいカードの中で最小の数字が書かれたカードの上にそれを重ねる。
• 何もカードが置かれてなかったら、それを置く
• 重なったカードがK枚以上になったら、そのカード達は食われる

↑の一連の動作を1ターンとする。 各カードが食われるのは何ターン目か出力せよ。食われない場合は-1を出力せよ。

解き方

自分より大きいカードの中で最小の数字が書かれたカード を求めるために二分探索をしたいので、SortedSetを使う。

sortedSetの他に、

• カードiが場に表で置かれているとして、その山に積まれているカードの枚数
• カードiの下に置かれたカードの番号

を管理すると、効率的にどのカードがどの山に入っているかが分かる。

ターンの毎に

cardGroup := make(map[int][]int)

のような、場に表で置かれているカードの下にどのカードが入っているかを表す配列を更新していくとO(N ** 2)になり間に合わない。 TLEになった提出: https://atcoder.jp/contests/abc260/submissions/53915955

問題の制約的に、同じ数字のカードは無いので、連結リストのように自分の下に置かれたカードを1枚だけ管理すればOK。

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

    ss := newSortedSet[int]()

    // pile[i]: カードiが場に表で置かれているとして、その山に積まれているカードの枚数
    pile := make([]int, n + 1)
    // under[i]: カードiの下に置かれたカードの番号
    under := make([]int, n + 1)

    res := make(map[int]int)

    for i, v := range p {
        target := ss.upperBound(v)
        if !target.IsValid() {
            pile[v] = 1
            ss.add(v)
        } else {
            under[v] = target.Value()
            pile[v] = pile[target.Value()] + 1
            ss.remove(target.Value())
            ss.add(v)
        }

        if pile[v] == k {
            ss.remove(v)
            pile[v] = 0
            x := v
            for j := 0; j < k; j++ {
                res[x] = i + 1
                x = under[x]
            }
        }
    }

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

https://atcoder.jp/contests/abc260/submissions/53916983