問題
https://atcoder.jp/contests/abc091/tasks/arc092_b
提出
https://atcoder.jp/contests/abc091/submissions/3868349
公式解説放送を見て
- bitごとに求めて間に合う（30bitとしてもNlogN x 30はTLEしない）
- 周期が見える
- modをとってよい
- sortしておいて二分探索する
- （要素多いな・・・）
振り返り
- 難しい。解説を読んで理解して実装
- 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; とすればいい
