[Boot camp for Beginners] C - Attack Survival [Rust]

概要

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

• 今回の問題：C - Attack Survival
• 書いたコード：提出 #48711042 - AtCoder Beginner Contest 141

学んだことmemo

• n, k が大きいので普通に処理かくと、処理時間オーバーしそう
• q ラウンドやるということは、最終段階で正解してない場合は k - q ポイントになる
  • 正解した場合は、ポイントが引かれないので正解数を足せば最終ポイントが割り出せる
  • 正解数は a の配列から filter すれば良い
  • 最終ポイントが0より大きい場合はYesを出力すれば良い
• ここまでやったが何件かTLEになる - 提出 #48710841 - AtCoder Beginner Contest 141
  • 正解数を a の配列から filter しているが、ここが毎回 O(n) かかるので遅い
    • 全体でもう一度ループがかかるので O(n^2) になってしまう
• 対策：事前に正解数の HashMap を作っておく
  • HashMap からのgetであれば O(1) なので全体でも O(n) にできる

そのほか

• usize 同士の引き算はそのままやってマイナスになるとエラーになるのを忘れててハマった
  • as isize しておかないといけない