[Boot camp for Beginners] C - Low Elements [Rust]

概要

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

• 今回の問題：C - Low Elements
• 書いたコード： 提出 #48883305 - AtCoder Beginner Contest 152

学んだことmemo

• 自分より左にある数字全てが自分より大きいかどうか
• indexをもとにループを回して、その中で毎回配列をスキャンすれば解けそうではある
  • ただし、Nの最大値が大きいので時間がかかりそう
  • 計算量的にも $O(n^2)$ ぐらいかかる
• 「自分より左にある数字のうち、最小のものが自分より大きい」とすれ当初の条件を満たせそう
  • それなら、 fold で (最小値, 条件を満たした個数) を引き回せば $O(n)$ で処理できる
• 発想の転換が難しい
  • 計算量考えて大きくなりそうなら $O(n)$ で処理できるように fold 一つにならないかとか考えるのがまだ慣れない
  • fold の中で始点とか終点の処理だけ特殊になったりするのを漏らしがち