[Boot camp for Beginners] C - Prison [Rust]

概要

AtCoder Problems: Boot camp for Beginners をRustで解いてみる

• 今回の問題：C - Prison
• 書いたコード：提出 #48694728 - AtCoder Beginner Contest 127

学んだことmemo

• まずカードの一覧を作る
  • (1..=n) で作って vec にすれば良さそう
  • rust の range は慣れてくると使いやすくてとてもいい
• 通れるかどうかのチェックは？
  • (l, r) に対してカードがその範囲内にあるかどうかを all でチェックすればいい
• これで終わるかと思ったら流石にそんなことなかった
  • 提出 #48694249 - AtCoder Beginner Contest 127
  • TLE が 2件
• なぜTLEになるのか
  • n * m が最大の計算量になるが、10^10 になるので多かった

• 仕切り直してロジックを考え直す
• (l, r) のリストを重なる範囲だけマージしていけば、全て通れる範囲が決まるはず
• 最小の範囲がもとまれば、min_l - min_r + 1 でその範囲に入る個数は求められる
  • 提出 #48694518 - AtCoder Beginner Contest 127
  • ここまでだとまだダメ。
  • エッジケースが何か漏れてる
• min_l - min_r + 1 がマイナスになるパターン = 1枚も全て通れるものがないパターン が漏れてそう
  • そのチェックを足したら通った