binary search

このタグでブログを書く

言葉の解説

ネットで話題

binary search

このタグの解説について

この解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。

競技プログラミング日記•10ヶ月前

AtCoder Beginner Contest 324F問題

ABC324F 解法平均の最大化なので，binary search が典型． $I \subset E$ に対して， $$ f_{I} := \frac{\sum_{i \in I}b_{i}}{\sum_{i \in I}c_{i}} $$ とおく． $x \in \mathbb{R}$ を固定したとき，$f_{I} \geq x$ となる $I$ が存在するか，という判定問題を解けばよい．$i \in I$ に対して $w_{i} := b_{i} - c_{i}x$ とおく．与えられたグラフが DAG なので，このグラフ上で DP が可能． \(i \in …

#binary search#平均の最大化#AtCoder#AtCoder Beginner Contest#DP#DAG

ネットで話題

148ブックマーク Binary search with modern processors

speakerdeck.com

107ブックマーク 404 Blog Not Found:アルゴリズム百選 - 二分探索(binary search)

dankogai.livedoor.blog

33ブックマーク Static search trees: 40x faster than binary search 1 Introduction1.1 Problem statement1.2 Motivation1.3 Recommended reading1.4 Binary search and Eytzinger layout1.5 Hugepages1.6 A note on benchmarking1.7 Cache lines1.8 S-trees and B-trees2 Optimizing find2.1 Linear2.2 Auto-vectorization2.3 Trailing zeros2.4 Popcount2.5 Manual SIMD3 Optimizing the...

curiouscoding.nl

24ブックマーク Beautiful Branchless Binary Search

probablydance.com

16ブックマーク Ruby/Bsearch: a binary search library for Ruby Ruby/Bsearch is a binary search library for Ruby. It can search the FIRST or LAST occurrence in an array with a condition given by a block. The latest version of Ruby/Bsearch is available at <URL:/ruby-bsearch/> . Example % irb -r ./bsearch.rb >> %w(a b c c c d e f).bsearch_first {|x| x <=> "c"} ...

0xcc.net

13ブックマーク GitHub - sourcegraph/doctree: First-class library documentation for every language (based on tree-sitter), with symbol search & more. Lightweight single binary, run locally or self-host. Surfaces usage examples via Sourcegraph.

github.com

8ブックマーク MySQL Search Team: A Binary Log API and a Replication Listener måndagen den 25:e juli 2011 A Binary Log API and a Replication Listener This blog will be about the binary log API found in the MySQL Replication Listener package. What does that have to do with intuitive searching in a MySQL database you ask? Because you can use the binary log to update any exte...

intuitive-search.blogspot.com

7ブックマーク Cache-friendly binary search

bannalia.blogspot.com

6ブックマーク How We Beat C++ STL Binary Search

academy.realm.io

関連ブログ

競技プログラミング日記•1年前

AtCoder Beginner Contest 294F問題

ABC294F 最初に濃度を固定した方が簡単．また，2つしか混ぜない．解法 0 自然な解法．濃度 $z$ を固定したとき， 2つの砂糖水 $i \in N, j \in M$ を混ぜて濃度を $z$ 以上に出来ることは， \[ \frac{a_{i} + c_{j}}{a_{i} + b_{i} + c_{j} + d_{j}} \geq z \] と同値．これを $i,j$ に分離すると， \[ a_{i} - z(a_{i} + b_{i}) \geq -(c_{j} + z(c_{j} + d_{j})) \cdots (*) \] と書ける．右辺を \(e_…

#砂糖水#濃度#AtCoder#AtCoder Beginner Contest#binary search

競技プログラミング日記•1年前

AtCoder Beginner Contest 203D問題

ABC203D 解法答えの候補を二分探索する．集合 $A$ に対して， $min(A) \leq x$ である事は， $A$のある元で $x$ 以下となるものが存在することと同地．また， $min(A) \geq x$ である事は， $A$の任意の元が $x$ 以上であることと同値．いずれを使ってもよい．答えの候補$x$を固定すると，指定された範囲の median を調べるためには，値が $x$ 以下の情報しか関係ないことになる． $x$ 以下の個数を数えて，半分より多いかどうかを調べれば， median が $x$ 以下となる事が判定出…

#AtCoder#AtCoder Beginner Contest#binary search#Median

競技プログラミング日記•2年前

AtCoder Beginner Contest 181E

ABC181E 先生の身長を固定して考えて，$h$ に追加しておく．このとき，ペアの作り方の最適解の一つは，ソートした $h$ に対して先頭から貪欲に 2人ずつ組んでいく方法が挙げられる．それが解ければ，あとは先生の身長を全探索すれば OK. 前もって $h$ をソートしておくことと， $h$ のペア達の累積和を前もって計算しておくことで，クエリ毎に $O(log (h.size))$ で答えられる．使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() {…

#binary search#貪欲法#AtCoder#AtCoder Beginner Contest

競技プログラミング日記•2年前

AtCoder Beginner Contest 311E

ABC311E $H, W \leq 3,000$ であるから，$O(HW)$ は間に合う．升目を全探索できるので，その上で穴の無い正方形を高速に数える．升目 $\,(x,y)\,$ を固定したとき，$ (x,y) $ を左上とする正方形のうち，穴の無いものを数えたい．これは単調性があると分かる．すなわち， $n \leq m$ かつ長さ$n$ の正方形に穴が有るならば，長さ $m$ の正方形にも穴がある．よって，binary search などが使えそうである．左上のマスと一辺の長さを指定したとき，その正方形の内部に穴が有るのかを高速に判定したい…

#AtCoder#AtCoder Beginner Contest#2次元累積和#binary search

競技プログラミング日記•2年前

AtCoder Beginner Contest 216E

ABC216E 同じアトラクションに何回乗るのかを高速に求められれば十分． Multiset としての和 $B := \cup_{i \in N} \{1, \cdots, a_{i}\}$ を取る． $B$ の元から，大きいほうから $K$ 個まで取ってくるのが最善． $m \in \mathbb{N}$ に対して， $Bool \ni f(m) := $ ($B$ に含まれる $m$ 以上の値は $K$ 個以下) とする． $C$ を十分大きな定数とする．$C = max_{i \in N} (a_{i}) + 1$ など．以下，最適なアトラクショ…

#AtCoder#AtCoder Beginner Contest

競技プログラミング日記•2年前

AtCoder Beginner Contest 267E

ABC267E 最大値の最小化は, binary search が典型．しかし，解法から攻めるのは王道とは言えない．まずは性質を考える．単調性 $\cdots (*)$取り除く作業を繰り返してく．ある時点でコスト $y$ 以下の vertex は，それ以降もずっとコストが $y$ 以下，という単調性がある．この単調性に基づいて binary search を行う．貪欲$\cdots (**)$先ほどの単調性から，除いてよい vertex は先に取り除いても損をしない．このことから，コストの小さい順に貪欲に削除出来そうである．解法0: Binary search…

#AtCoder#AtCoder Beginner Contest#min priority queue#貪欲法

競技プログラミング日記•2年前

AtCoder Beginner Contest 269E

インタラクティブな問題．解法Binary search と同じで，区間を半分ずつにしていく．行を 2つの区間に分けたとき，区間の行の個数より駒が少ない区間が存在する．そちらの区間に正解の行がある．列も同様．実装入力と出力を一緒に行う関数を用意すると楽．使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n; cin >> n; auto send = [&](ll a, ll b, ll c, ll d) -> ll { cout << "? " << a <<…

#AtCoder#AtCoder Beginner Contest#インタラクティブ

競技プログラミング日記•2年前

AtCoder Beginner Contest 270E

ABC270E 解法は2つある．いずれにせよ，まずは 1周を一塊で考える．解法0: Binary search$K$ を固定する．($m$ 周できるか) $\in Bool$ は単調．$m$ 周すると，各 $i \in N$ に対して $min(a_{i},m)$ 個食べるので，その合計が $K$ 以下かどうかで判定できる．判定に $O(N)$, binary search に $O(log\,K)$．解法1: シュミレーション, min priority queue1周単位で考えるのは同じだが，高速化のためにまとめて周回する． $a$ の内，\…

#AtCoder#AtCoder Beginner Contest#min priority queue#binary search#シュミレーション

競技プログラミング日記•2年前

AtCoder Beginner Contest 305D

ABC305D 0-indexed とする．区間毎に値を振っておく．偶数番目とき数番目の区間に対して，0 と区間の長さを対応させる．この値に関して累積和をとればよい．区間の端だけ中途半端になりうるので微調整．$l,r$が与えられたときに，どの区間に$l,r$が入るのかは binary search で求まる．使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n; cin >> n; vll a(n); rep(i,n) { cin >> a[i]; }…

#AtCoder#AtCoder Beginner Contest#累積和#binary search