「その他の小技」の記事一覧

優先度付きキュー（priority queue）は、要素を優先度付きで追加し、要素を取り出すときは最も高い優先度を持つものから取り出されます。ただいったん格納した要素の優先度を変更したり要素がもつ値を変更することはできま・・・

続きを読む

E – Best Performances 問題の趣旨は以下のとおりです。 配列 A のある要素の値を別の値に変更する。 そのあと降順にソートして先頭から K 番目までの総和を求めよ。 配列 A の長さは最大・・・

続きを読む

配列から値を削除するだけなら・・・ B – Search and Delete 配列 A から 配列 B の値を削除せよというのが問題の趣旨です。配列の長さは最大で100です。 配列ではなくリストにしてRem・・・

続きを読む

C# JavaScript 不規則な形をした図形との当たり判定ではCrossing Number アルゴリズムを用いて点と多角形の内外判定をしました。この方法は「多角形の各線分ごとに指定した点を通るx軸に平行な線との交点・・・

続きを読む

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

続きを読む

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

続きを読む

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

続きを読む

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

続きを読む

タイトルそのままです。「連続する部分列の総和が0になる場合」が何通りあるのかを数えます。これもループを何重にも回すのではなく1回で終わらせます。累積和をつかえば配列が長くても一発で終わります。 連続する部分列の総和が0の・・・

続きを読む

連続する部分列の総和を最大にする方法を考えます。 間違ってはいないが時間がかかる まずは何の工夫もない方法から。二重ループですべての部分列の総和を計算してそのなかから最大値を求めようとしています。与えられた配列が短ければ・・・

続きを読む