ながめも

競技プログラミングについて

BIT

AtCoder Beginner Contest 174 ABC174 参加記

Eまでノーペナ30分だったのにF既出を検索できずにしょっぱいパフォを取ってしまいました。もったいなかったです。 jjjjjjjtgpptmjjさんのAtCoder Beginner Contest 174での成績:1161位パフォーマンス:1476相当レーティング:1307→1325 (+18) :)#AtCoder #A…

AtCoder Beginner Contest 106 D - AtCoder Express 2

atcoder.jp 区間を二次元座標とみなし、二次元累積和で。 一方、クエリ先読みして区間を終端ソートすると、終端が前の区間から順に確認していくことで問題を解くことができる。終端の順番を固定し、始端の分布をBITでもち、和をで得ることができ、計算量はと…

yukicoder No.649 ここでちょっとQK!

yukicoder.me 類題がこれとこれ。 coonevo.hatenablog.com coonevo.hatenablog.com 上記の類題と違うのは値の範囲が広いこと。こういうやつはクエリ先読みすると種類数が少ないから順序データに座標圧縮すればよい。あとはライブラリでやるだけ。 座圧のうま…

AtCoder Regular Contest 021 ARC021 C - データ構造

atcoder.jp 類題がこれ。 coonevo.hatenablog.com ライブラリでやるだけ。 template<typename T> class BIT{ public: int N; vector<T> data; BIT(T _N):N(_N){ data.assign(N+1, 0); }; // a is 1-indexed void add(int a, T w){ for(int x = a; x <= N; x += x & -x)data[</t></typename>…

Educational Codeforces Round 87 (Rated for Div. 2) D - Multiset

コンテスト参加記はこちら。 coonevo.hatenablog.com D - Multiset 問題概要 解説 D - Multiset 問題へのリンク 問題概要 集合の初期状態が与えられる。 以下2つのクエリを処理したあと、残っている要素のいずれかを出力せよ(空の場合は-1)。 要素を追加。…

Educational Codeforces Round 87 (Rated for Div. 2) 参加記

コンテストへのリンク 参加しました。結果は以下です。 (プレテスト中) Dができて嬉しかったです。 A B C1 C2 D E A 問題へのリンク 周期性があるのでごちゃごちゃやるといいです(こういうの嫌い) void solve(){ ll a,b,c,d; cin >> a >> b >> c >> d; i…

AtCoder Regular Contest 101 ARC 101 D - Median of Medians

問題 方針 単調性 判定問題 区間の中央値がX以上になる条件 区間列挙の解決策 実装 問題 長さNの数列が与えられる。この中の全ての連続部分列における中央値の中央値を求めよ。 問題へのリンク 方針 単調性 二分探索する。 中央値がX以上となる区間の数が全…

AOJ 反転数(転倒数)BITによる高速化

反転数とは 方針 愚直にO(N2) 高速化、O(NlogN) 方針転換 準備 実装 今回は反転数について扱っています。転倒数とも呼ばれるようです(というより競プロ界隈では転倒数の方が一般的かも?)。 問題へのリンク 反転数とは 数列があるとき、 のとき となるの組…

Binary Indexed Tree で Range Sum Query

AOJ RSQ 問題へのリンク AOJ RSQ Binary indexed Treeによる解答 BITとは 実装 提出 Binary indexed Treeによる解答 BITとは 以下のスライドが参考になります。説明はいろいろなところにあるので、適宜調べてみてください。 Binary Indexed Tree のはなし 実…

AtCoder Beginner Contest 091 ABC091 D - Two Sequences

AtCoder Beginner Contest 091 ABC091 D - Two Sequences AtCoder Beginner Contest 091 ABC091 D - Two Sequences 問題概要 解説 方針 解答方法 提出 問題概要 長さNの二つの数列a,bがある。これらの全ての組み合わせa_i + b_jに対して、全てxorをとったと…