なんとな～くしあわせ？の日記

「そしてそれゆえ、知識そのものが力である」 (Nam et ipsa scientia potestas est.) 〜 フランシス・ベーコン

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

AtCoder アルゴリズム 競技プログラミング

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という関数に以下のような処理を加えます。

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

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でパーサジェネレータ

プログラミング Clojure

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 >]]]]

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

パーサジェネレータについて調べた

技術論 雑記

パーサジェネレータの位置づけ

少しだけパーサジェネレータについて書く。パーサジェネレータとはパーサを生成できるソフトウェアのことである。

そもそもパーサとはなんだったか確認しよう。

パーサ（＝構文解析器）

パーサとは 構文解析器 - Wikipedia である。

XMLを読み取るパーサの例としては Document Object Model - Wikipedia や Simple API for XML - Wikipedia。要はDOMやSaxである。Javaを書いたことがあればちょっとは使ったことがあるはず。最近はXMLからJavaに変換する時は Java Architecture for XML Binding - Wikipedia を使うかもしれない。

構造を持った入力テキストの処理をおこなうものはすべてパーサだと言える。

なぜテキストに構造を持たせなければいけないのか？それは データ記述言語 - Wikipedia に書かれている以下のような理由による：

データ記述言語は、以下の点に主眼を置いて作られた。
　　１．複雑なデータ構造をもつデータを格納する。
　　２．データの記述方法や個々のデータ要素へのアクセス方法の共通化をはかる。
　　３．データをテキスト形式で格納する。

ただのテキストファイルだと、日付や誰によって更新されたか、どの部分が列でどの部分が行か？わからない。そういったデータの格納の仕方を定めたXML, JSON, HTML, そしてCSVやTSVすべてデータ記述言語と言える。XMLがまどろっこしいのは別にプログラマーがマゾだからではなく、付与したい情報が多いからである。

パーサジェネレータの利点

パーサがデータ記述言語によって構造化されたデータを読み取れることはわかった。では、パーサジェネレータは何ができるのか？

パーサジェネレータは、なんとこのデータ記述言語のルールを記述するだけでパーサを作ってくれる。スゴイ！

次の記事でそれを実践していく：


パーサジェネレータの実装の種類

Wikipediaを見ると、以下のような手法があるようだ