アルゴリズムまとまってるサイト

メモ用、他にあれば追記する

ポータルサイト

英語読めれば大抵の典型問題に関する示唆が得られる

www.geeksforgeeks.org

www.csegeek.com

数学問題に対抗するために

mathtrain.jp

大学の授業シラバス系

• ヨークカレッジ・ペンシルベニア校
  • Lecture Notes

• イリノイ大学アーバナ・シャンペーン校
  • Jeff Erickson's Algorithms, Etc.

個人サイト

• • tubo28.me

このサイトにあったサイトも転記している

• [O] 無料で読める2つのアルゴリズムの講義資料

ダイクストラの出身校とかでググってもいいレクチャーノート出てこないのはちょっと不思議

AtCoder - AtCoder Beginner Contest 040 (道路の老朽化対策について) を解いてみた

ABC 040 D問題に使われるアルゴリズム要素はUnion-Findです。

Union-Find自体は前回ブログ記事にしていたのですが…これだけでは足りませんでした。ACするためには経路圧縮とrankによる木のマージ処理が必要です。

nantonaku-shiawase.hatenablog.com

今回の内容はAOJ本にバッチリ書かれています。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

アルゴリズム

経路圧縮

前の記事の中で、ある要素の最上位の親を求める処理を以下のように求めたはずです。

def root(i, id)
  while i != id[i] do
    i = id[i]
  end
  i
end

しかし、これではある要素を求める際に毎回whileループが回ります。計算量が増えてしまいます。以下のようにすることで、途中までの要素を全て書き換えます。関数名はfind_setに変えます。

def find_set(i, id)
  if i != id[i]
    id[i] = find_set(id[i], id)
  end
  id[i]
end

rankによる木のマージ処理

木のマージ処理に関しては、擬似コードのほうがわかりやすいでしょう。前回作ったuniteという関数に以下のような処理を加えます。

またアメリカの大学の資料から

• http://jeffe.cs.illinois.edu/teaching/algorithms/notes/17-unionfind.pdf
• https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/UnionFind.pdf

UNION-BY-SIZE (x, y) 
    r ← FIND (x).
    s ← FIND (y).
    IF (r = s) RETURN.
    ELSE IF (size(r) > size(s))
        parent(s) ← r.
        size(r) ← size(r) + size(s).
    ELSE
        parent(r) ← s.
        size(s) ← size(r) + size(s).

これらを行うことで計算量が削減され、満点となるようです。AtCoderの問題としては、これらの計算量の削減がなくてもロジックとUnion-FIndの実装ができていれば50点もらえます。

解答

• 今回、解答の作成にあたってはだいぶ他の人の解答を真似している面があります…コピペはしてないけど

Submission #1754689 - AtCoder Beginner Contest 040 | AtCoder

Instaparseでパーサジェネレータ

Instaparseの位置づけ

InstaparseはClojure言語による パーサジェネレータ - Wikipedia である

github.com

これのルール記述はBNFの拡張であるEBNFが使われている。

EBNFで構造化言語のルールを記述する

さっそくだが、「＜p＞sample＜/p＞」を読み取るBNFのルールを書いてみた。とは言え、HTMLの複雑なルールを最初から書くのは無理なので、とりあえずタグの開始と終了を読み取れるものを作る。

しかもこのルール記述、de.setf.xml/html-grammar.bnf at master · lisp/de.setf.xml · GitHub からコピーしてきたものである。

コードサンプル

(ns sample
  (:require [instaparse.core :as insta]))

;;
;; https://github.com/lisp/de.setf.xml/blob/master/bnf/html-grammar.bnf
;;
(def as-and-bs
  (insta/parser
   "HtmlDocument ::= Root
    Root         ::= ElementHtml
    ElementHtml  ::= HtmlTag | ( STag ( '/>' | ( '>' #'\\w'++ ETag ) ) )
    HtmlTag      ::= '<'  #'\\w'++ S* '>'
    STag         ::= '<'  #'\\w'++ S*
    ETag         ::= '</' #'\\w'++ S* '>'

    S ::= (' ' | '\t' | '\r\n' | '\n')+
"))

(def fool-tags "<p>sample</p>")

(defn fool-sample []
  (println (as-and-bs fool-tags)))

出力

• sampleのデータがきっちり構造化されて戻ってきた

lein test html-template.test
[:HtmlDocument [:Root [:ElementHtml [:STag < p] > s a m p l e [:ETag </ p >]]]]

後はこれに対して指定されたキーを使ってデータを取得したりすればいいのである。