動機 1次元累積和クラスはよく使っているため 2次元累積和を使う問題と出会ったため Code // 2次元累積和 struct AccSum2D{ VV Ac; // accumulate ll W; ll H; AccSum2D(){} AccSum2D(VV &A){ H = A.size(); W = A[0].size(); Ac.resize(H+1, VI(W+1)); // i…

Quiz https://yukicoder.me/problems/no/755 AC Code https://yukicoder.me/submissions/353176 解法 二次元累積和 その他 1-indexedで考えて、添字0の箇所は0で埋めておくと、sumを求めるときの引き算が統一的に扱えるのでバグりにくい ll sum = A[x1][y1] …

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

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の説明が書いてあり、まさにこれ！ まと…

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>…

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をした…

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

Quiz https://atcoder.jp/contests/abc084/tasks/abc084_d Submit https://atcoder.jp/contests/abc084/submissions/3879182 要素 エラトステネスのふるい（今回はなくてもよい） 累積和 left～rightでの個数＝＞f(v) : 0～vまでの個数を求めておき、f(right…