最近ようやく300点問題がまあまあ解けるようになってきたので、茶diffの400点問題を探しています。 今日解いたのはこれです!! 考えたこと 計算量はO(NlogN)まで間にあう。 愚直にやってたら O(N × Q ) となるので間に合わない… Aをソートして、A_1 <= A_2 <= ・・・<=A_ｎとして、X_i <= A_kを満たす最小のｋを見つけたら、求める数は X_i × (k - 1) - (A_1 + ・・・+ A_(k-1)) + (A_k + ・・・
自分用?に、Atcoderなどで学んだことを書いていきたいと思います。 まだまだ実力不足なので誤りがあるかもしれません。 今日解いたのはこれです。 考えたこと とりあえず制約を見た感じ、O(NlogN)くらいまでなら間に合いそう。 和を求めるには累積和が使えそう。 以上（えぇ…) いざ実装 とりあえず累積和を使いたいので、下準備として計算しておきます。 a[i]で、a_1+a_2+・・・+a_(i-1) までの和（ただしa[1] = 0) とすれば 、P = a[y]
