「小技」の記事一覧(2 / 19ページ目)

1次元、2次元、3次元配列の累積和

累積和

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

平方分割で区間を指定した値の更新と最大値の取得という大量のクエリに対応する

平方分割

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

double型 float型 誤差への対応策 数値計算の丸めエラーと浮動小数点演算の限界

その他の小技

プログラムで小数点以下の計算をおこなうと誤差が生じることがあります。コンピュータの場合、二進法で計算の処理をおこなっていますが、小数点以下の数を2進数で表現できない場合があり、人間目線だと意外なところで誤差が発生すること・・・

点と線分の最短距離を求める

その他の小技

点(x, y)と線分(点A(x1, y1)と点B(x2, y2)を結ぶ線分)の最短距離を求めます。いろいろなやり方があるかもしれませんが、鳩は以下のように考えました。 平行移動と回転移動で最短距離を求める 全体を平行移動・・・

ページの先頭へ