ABC
354
C - AtCoder Magics

C - AtCoder Magics

キーワード

解説

問題 (opens in a new tab)

  • セグ木を使った解放

まず、カードを AA について昇順にソートして、その順にカードを見ていく。このカードが捨てられないカードであるためには、それより右にあるカードの中で、CC が最小のものよりも CC が小さければいい。 これを満たすカードを求めるために、セグメント木を使う。 ソートした順にカードを入れていく。 ii 番目のカードを見るとき、 i+1 Ni+1 ~ N の最小値を求める。 ii 番目のカードの CC がその最小値よりも小さければ、そのカードは捨てられないカードである。

  • セグ木を使わない解法

まず、カードを AA について降順にソートして、その順にカードを見ていく。カードが捨てられないカードであるためには、それより左にあるカードの CC の中の最小値よりも CC が小さければいい。 最小値は、その時点での最小値を保持しておけばいい。探索自体は O(N)O(N) でできる。

計算量

  • セグ木を使った解法

O(Nlog⁡N)+O(Nlog⁡N)=O(Nlog⁡N)\mathrm{O}(N\log{N}) + \mathrm{O}(N\log{N}) = \mathrm{O}(N\log{N})

  • セグ木を使わない解法

O(Nlog⁡N)+O(N)=O(Nlog⁡N)\mathrm{O}(N\log{N}) + \mathrm{O}(N) = \mathrm{O}(N\log{N})

提出コード

  • セグ木を使った解法
type Card struct {
	A, C int
	index int
}
 
func main() {
	n := readInt()
	C := make([]Card, n)
	for i := 0; i < n; i++ {
		scanIntVariables(&C[i].A, &C[i].C)
	}
	for i := 0; i < n; i++ {
		C[i].index = i
	}
	sort.Slice(C, func(i, j int) bool {
		return C[i].A < C[j].A
	})
 
	t := NewSegmentTree(n, math.MaxInt, func(a, b int) int { return min(a, b) })
	for i := 0; i < n; i++ {
		t.Update(i, C[i].C)
	}
 
	Ans := make([]int, 0)
	for i := 0; i < n; i++ {
		mi := t.Query(i+1, n)
		if C[i].C < mi {
			Ans = append(Ans, C[i].index+1)
		}
	}
 
	sort.Slice(Ans, func(i, j int) bool {
		return Ans[i] < Ans[j]
	})
	writeLine(len(Ans))
	for _, v := range Ans {
		write(v, " ")
	}
	writeLine()
}
  • セグ木を使わない解法
func main() {
	n := readInt()
	C := make([]Card, n)
	for i := 0; i < n; i++ {
		scanIntVariables(&C[i].A, &C[i].C)
	}
	for i := 0; i < n; i++ {
		C[i].index = i
	}
	sort.Slice(C, func(i, j int) bool {
		return C[i].A > C[j].A
	})
 
	mi := math.MaxInt64
	Ans := make([]int, 0)
	for i := 0; i < n; i++ {
		if C[i].C < mi {
			mi = C[i].C
			Ans = append(Ans, C[i].index+1)
		}
	}
 
	sort.Slice(Ans, func(i, j int) bool {
		return Ans[i] < Ans[j]
	})
	writeLine(len(Ans))
	for _, v := range Ans {
		write(v, " ")
	}
	writeLine()
}
B - AtCoder Janken 2355