累積和

No.754 畳み込みの和

Quiz https://yukicoder.me/problems/no/754 Submission https://yukicoder.me/submissions/350209 解法 N=3で書いてみると以下の和を求めればいいと分かる 配列AかBの累積和を持っておけば、和はO(N)で求められる

2次元imos DSL_5_B いもす

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_5_B Submission http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3589681#1 参考 https://imoz.jp/algorithms/imos_method.html 2次元imosの説明が書いてあり、まさにこれ! まと…

B. Expansion coefficient of the array

Quiz https://codeforces.com/contest/1159/problem/B Submission https://codeforces.com/contest/1159/submission/54048500 実験 サンプル3を見る |i-j| = 3のとき、minは717 k x 3 <= 717 k <= 239 これは答えと一致する 解法 |i-j|を幅と呼ぶことにする …

累積和クラスを作ってみた

作成動機 元となる配列サイズ+1で作ったり、範囲の和を取る時に添え字でミスりそう いつも同じ作成をしているので省略したい Code struct AccSum{ vector<ll> Ac; ll L; AccSum(vector<ll> &A){ L = A.size(); Ac.resize(L+1); FOR(i, 0, L){ Ac[i+1] = Ac[i] + A[i]</ll></ll>…

B - 交通費

Quiz https://atcoder.jp/contests/bitflyer2018-final-open/tasks/bitflyer2018_final_b Submit https://atcoder.jp/contests/bitflyer2018-final-open/submissions/4881138 解法 editorialの通り 感想 lower_boundでiteratorを取ってきた後、+1, -1をした…

C. Painting the Fence

Quiz https://codeforces.com/contest/1132/problem/C Submit https://codeforces.com/contest/1132/submission/50862056 解法 除去する2人を全パターン試すとO(N3)となってしまう 除去する1人を固定する 残りq-1人で塗る。各箇所が何回塗られたかをカウント…

「この範囲内の個数を求めよ」というクエリが10^5個とかある時、累積和で前準備 abc084_d

Quiz https://atcoder.jp/contests/abc084/tasks/abc084_d Submit https://atcoder.jp/contests/abc084/submissions/3879182 要素 エラトステネスのふるい 累積和