「二分探索法」の記事一覧

これまでにゲームを作ってきましたが、オブジェクトの数が増えると当たり判定に時間がかかるのでオブジェクトの数をあまり大きくすることはありませんでした。しかし二分探索法を使えば高速化は可能です。思った以上の差となりました。 ・・・

続きを読む

配列のなかから指定された値に対して K 番目に近い値を取得する方法を考えます。 D – K-th Nearest D – K-th Nearest 数直線上に N + Q 個の点 A_1, … ,・・・

続きを読む

二分探索法を活用することで全探索をするよりも計算量を減らすことができます。 全探索でもできるが・・・ A05 – Three Cards 赤・青・白の 3 枚のカードがあります。 太郎君は、それぞれのカードに・・・

続きを読む

変なタイトルですが、こんな問題です。 パイプを切り出そう n 本のパイプがあり、長さはそれぞれ A_1, A_2, …, A_n です。今、n 本のパイプから k 本の同じ長さのパイプを切り出すことを考えます・・・

続きを読む

C# 二分探索法で配列のなかから最も近い値を取得する binary-search-nearest-value 二分探索法はソート済みの配列において、検索する間隔を半分に分割しながらデータを探し出すアルゴリズムです。先頭か・・・

続きを読む

こんな問題が出てきたらあなたはどうするだろうか？ 引用元：長い長い数列 数列 A = (A_1, A_2, …, A_n) と数列 B = (B_1, B_2, …, B_m) が与えられる。 n・・・

続きを読む

値の探索 int型の配列内に指定された整数が存在するかを調べる問題。配列はすでにソートされています。配列のサイズは最大で200,000です。 なにも考えずに以下の方法では時間がかかりすぎであり不合格。 [crayon-6・・・

続きを読む