[Boot camp for Beginners] C - Exception Handling [Rust]

概要

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

• 今回の問題：C - Exception Handling
• 書いたコード：提出 #48825587 - AtCoder Beginner Contest 134

学んだことmemo

• 2*10^5 が最大の個数
• 要素ごとに、自身を filter して max を求めて出力すればいいが、それだと O(n^2) になるので遅い
• 自身を除いた最大値だと、基本的には a の最大値しか出力されない
  • 例外は ai 自身が最大値のとき
  • 最大値が複数あれば、最大値を出力しても問題ない
  • 最大値が単一であれば、最大値の次に大きい数を出力する必要がある
• ということで
  • 事前に最大値とその次に大きい数を求めておく
    • clone した配列を sort して、last と その一つ前を取ればいい
  • 合わせて最大値の個数も求めておく
    • これは max で filter して count しておけばいい
  • これで計算量は O(n) に収まるはず
• この方法で解けた
  • 今回は計算量に引っ掛からなかった