AtCoderBeginnerContest230 D問題400点 「Destroyer Takahashi」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
$ N \leq 2 \times 10^5
解法・お気持ち
まずは、「お気持ち」(どう解こうかな?)というところから考えていきます。
つまり、どう答えに近づいていこうかな、というフェーズです。
https://gyazo.com/0c967afc69c1bab543f3a55a7fa925ff
上記のような壁をできるだけ少ないパンチで壊していきます。
まず、$ N \leq 10^5です。
ここからおそらく $ O(N \log N)で解きたいなぁというきもちになります。($ O(N)は無理だろうなぁという気持ちにもなります。)
ここで$ \log Nであるため、ソートか...??? というきもちにもなります。
よって、ここから以下はソートで解こうかなというきもちで問題に向かいます。
つぎに、極力うまくパンチをするのであれば、Greedy に考えるといいのでは?と至ります。 格子状の区画を一番左から歩いていったときに、極力「貪欲に」パンチをうたないようにすることを考えます。
すると、はじめてどうしてもパンチを打たないと行けないタイミングは、"壁の右端" が一番左側にある壁をすぎたタイミングです。
https://gyazo.com/70004882117f01edf6438f44a52ee894
よって、このギリギリのタイミングになってからパンチをします。
この議論を最後の最後まで繰り返すと
「ある壁の右はしに来たらパンチをうつ。そのパンチの被害を受けた他の壁は一緒に死ぬ。」
になり、実はこれがパンチの最小回数です。
よって、R[i] で昇順ソートして、R[i] - L[j] + 1 <= D となるような最大の $ jまで一気に進めばいいです。
https://gyazo.com/9850bcdd4809941e3c6ef8f4a882be55
これを繰り返す実装をすればよいです。
Greedyの証明の多くは、「最適でない状態」から「問題で許されている操作」を行っても、「良くなることはあっても悪化することはない」ということを示して最適な状態に持っていく、というものが多いです。 正当性の証明は公式解説を参考にしてください。
計算量
$ O(N \log N)
新たな学び
Go の pair 型は [2]int の配列をつかえばいい
pair の配列は [][2]int になる
反省点
コード
code: go
func main() {
io := NewIo()
defer io.Flush()
// ------------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------
N, D := io.NextInt(), io.NextInt()
L := make([]int, N)
R := make([]int, N)
for i := 0; i < N; i++ {
Li, Ri = io.NextInt(), io.NextInt() }
for i := 0; i < N; i++ {
}
sort.Slice(RL, func(i, j int) bool {
}
})
ans := 0
for i, j := 0, 0; i < N; i = j {
for j < N && RLj1-RLi0 <= D-1 { j++
}
ans++
}
fmt.Println(ans)
}