「小技」の記事一覧

両端キューは先頭または末尾で要素を追加・削除できるキューです。 通常のキューは要素を追加するときは末尾からしかできず、取り出すときは先頭からしかできません。通常のリスト（C#のList<T>）は任意の場所で要・・・

続きを読む

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

続きを読む

マンハッタン距離と45度回転 マンハッタン距離またはL1-距離とは幾何学における距離概念の一つで、各座標の差の絶対値の総和を2点間の距離とするものです。 平面上であれば、座標(x1, y1)と(x2, y2)のマンハッタ・・・

続きを読む

区間の総和を高速で求める累積和 累積和とは配列の任意の区間の総和を求めるためのアルゴリズムです。 繰り返し処理を使うと大きな計算量になってしまう区間の計算問題を、適切な前処理を行うことによって高速に行うことができます。 ・・・

続きを読む

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

続きを読む

平方分割で区間の最大値を求める大量のクエリに対応するの続きです。前回は最初に整数の配列が与えられましたが、その配列の値が更新されることはありませんでした。今回はある区間の最大値を求める ＋ ある区間で配列の値が更新される・・・

続きを読む

最初に大きなサイズの配列が与えられ、そのあと区間[a, b]の値にXを加えよとか、区間[c, d]の最大値を求めよとか、区間[e, f]の総和を求めよというクエリが大量に飛んできて、しかもそれらの結果を2秒以内に返せとい・・・

続きを読む

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

続きを読む

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

続きを読む

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

続きを読む