絶対にintを越えないという確信がない変数はlong longにしよう (arc092_b)

問題

https://atcoder.jp/contests/abc091/tasks/arc092_b

提出

https://atcoder.jp/contests/abc091/submissions/3868349

振り返り

  • 難しい。解説を読んで理解して実装
  • lower_boundと仲良くなれた
  • int count = 0; としていたため、大きいテストケースで通らず。ll count = 0; として通った
    • countがintの桁をあふれる訳がないという思い込みがあった
    • 実際はindexの差でcountに足す値を求めているのでかなり大きい値が一気に入る
  • 思考としては *「大きいテストだけWAだな」
    • intであふれてる?intを使ってるのはcountか
    • ダメもとでllにしてみるか→AC

学び

  • sort済み配列に対して、値の範囲に収まる要素数をlower_boundで求めることができた
  • 2のn乗はシフトで書いてもよい
  • イテレータの差でindexの差を求める
  • vectorをどこで宣言するか。forの外側で宣言して再利用した方が速くなる
    • 今回の場合N=200000というのもあり、1秒の差が出た
    • 普段から再利用して速いコードにしておくとよい
  • (最後に) 絶対にintを越えないという確信がない変数はlong longにしよう

追記:int同士のかけ算があるとそこでも溢れうる

  • int a, b;
  • a = pow(10, 9);
  • b = pow(10, 9);
  • ll c = a * b;
    • 溢れたままlong long cnに入ってしまう
    • ll a, b; とすればいい