ABC 152 C - Low Elements
初手の方針
ぱっと見lower_bound使いそうだなと思ってvectorに詰める方向で諸々思考錯誤した。 最終的に順列Pのi番目の要素p[i]としたときi番目までの集合Piの最小pc[i]がp[i]と一致すればカウントするという方向でコードを書いてLTE。ソート1回の計算量がNlogNなので間に合わない。
Submission #9627256 - AtCoder Beginner Contest 152
正答
初手の方針とやってることは大して変わらない。言い換えるとp[i]以前の要素のminとp[i]を比較してp[i]のほうが小さければ m = min(m, pi) カウントするとなる。
Submission #9634734 - AtCoder Beginner Contest 152
本日の気付き
- sortは計算量を食うのでループは基本不可能と考える
オーダー次第だがコード中1回が限界だと思う。
- 最初の思考に引っ張られすぎない
最初にlower_boundが頭をよぎったせいで最後までvectorに固執してしまった、最終的にはvectorすら不要だった。
