「小技」の記事一覧

ダイクストラ法とその制約 ダイクストラ法はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムです。1959年エドガー・ダイクストラによって考案されたアルゴリズムでOS・・・

続きを読む

15パズルの最短手数の最大値ってどうなっているんだろう？とふと疑問に思い調べてみると、「任意の可能な配置へ80手以内で変形でき、80手が必要な配置は確認されている」（Wikipediaより）とのこと。 15パズルは空白を・・・

続きを読む

今回は平衡二分探索木のひとつである赤黒木を実装します。 赤黒木とは？ 赤黒木は平衡二分探索木のひとつです。赤黒木は以下のような特徴をもっています。 二分探索木である以上、ノードの左側の子はそのノードがもつ値より小さく、右・・・

続きを読む

AVL木（AVL tree、Adelson-Velskii and Landis’ tree）は二分探索木の一種（そのなかでも平衡二分探索木の一種）です。 二分探索木とは？ 二分探索木とはこの図のようなもので・・・

続きを読む

かつて JavaScript ユーザーがアップロードした不適切な画像を検出する という記事を書いたのですが、ここでは NSFW JS というJavaScriptライブラリを使ってエロ画像かどうかを判断しています。しかし不・・・

続きを読む

ソートのアルゴリズムの一つにバケットソート（bucket sort）があります。 バケットソート（bucket sort）とは？ バケットとはバケツのことです。このソートアルゴリズムはどんな場合でも使えるわけではありませ・・・

続きを読む

結論から言えば「非負数と負数にわけて総和を計算する」です。 D – ±1 Operation 2 問題の趣旨 長さ N の数列 A がある。 A[i]に 1 を加算または減算するという操作を 0 回以上繰り返・・・

続きを読む

064 – Uplift（★3） 問題の趣旨 区画 i の標高を E[i] とするとき、不便さを |E[1] – E[2]| + |E[2] – E[3]| + … + |・・・

続きを読む

ベル数とは？ わかりにくいタイトルで申し訳ありませんが、ここではN個のものをグループに分ける方法（グループの順番、グループ内の順番は区別しない）を考えます。この個数をベル数 B(N) といいます。3つのものをグループにわ・・・

続きを読む

関数の局所的な最小値と局所的な最大値をそれぞれ極小値と極大値と呼びます。微分可能な関数では、極大値をとる点で導関数（f'(x)）が正から負に変化し、極小値をとる点で導関数（f'(x)）が負から正に変化します。最大値や最小・・・

続きを読む