AOJ - ALDS1_7_A, B, C (木構造) を解いてみた

勝手に解いてろとか言わないで…

ALDS1_7_A, B, Cは、木構造（根付き木、二分木）です

根付き木 | アルゴリズムとデータ構造 | Aizu Online Judge
二分木 | アルゴリズムとデータ構造 | Aizu Online Judge
木の巡回 | アルゴリズムとデータ構造 | Aizu Online Judge
木の復元 | アルゴリズムとデータ構造 | Aizu Online Judge

木構造を使うときの基本

まあ、木構造単体でプログラミングコンテストの問題が出されることはほとんど無さそうなのですが…*1

• とりあえず、構造体 or クラスで以下のような型を作る
• 木構造の１要素を１つのNodeというクラスで表現します。中には親要素のid、左と右の要素のidを持ちます。
• Rubyの場合はStructを使うと楽にそういうのが作れる、Generics無しにそれを配列型にできるし

Node = Struct.new(:parent, :left, :right)
nodes = Array.new(N) { Node.new }

ALDS1_7_A - 根付き木

１つの節（ノード）に複数の子がくっつく場合の構造。

自分の回答

用意した関数を紹介しておく

get_depth ( id, nodes )

その接点の深さを求める

get_children ( id, nodes )

その接点の直下の子ノードを求める

ALDS1_7_B - 二分木

１つの節（ノード）に２つの子しかつかない場合の構造。

自分の回答

用意した関数を紹介しておく

get_depth ( id, nodes )

その接点の深さを求める

get_height ( id, nodes )

その接点の高さを求める、深さと逆のため再帰的にノードを求める必要がある(Finding height in Binary Search Tree - Stack Overflow)

get_sibling ( id, nodes )

その接点と同じ階層にあるノードを求める、二分木の場合隣接するものはあるかないか２択になる

ALDS1_7_C - 木の巡回

木の巡回には３種類あるという話。

• 根節点、左部分木、右部分木の順で節点の番号を出力する。これを木の先行順巡回 (preorder tree walk) と呼びます。
• 左部分木、根節点、右部分木の順で節点の番号を出力する。これを木の中間順巡回 (inorder tree walk) と呼びます。
• 左部分木、右部分木、根節点の順で節点の番号を出力する。これを木の後行順巡回 (postorder tree walk) と呼びます。

自分の回答

用意した関数を紹介しておく

pre_parse ( root, nodes )

根節点、左部分木、右部分木の順で節点の番号を出力する

in_parse ( root, nodes )

左部分木、根節点、右部分木の順で節点の番号を出力する

post_parse ( root, nodes )

左部分木、右部分木、根節点の順で節点の番号を出力する

使用例？

単純な木構造って、実務でも競プロでも使うことが稀な気がする。すごい単純なデータが問題で、なおかつ階層がキーになる場合に使えばいいのかな？いい問題があれば追記します。

追記：　木構造の問題です

A Rational Sequence 2 – Kattis, Kattis

*1:木構造よりも、それの発展系のグラフアルゴリズムの出題が多そう

MyBatisエラー別対応とか

Wikiの方に書いた記事によくアクセスがあるようなので、はてなに移しておく。

MyBatisのエラー別対応

エラーメッセージ："Mapped Statements collection does not contain value for クラス名"

原因

• ディレクトリ構成が変
• Mapperファイルに対応するソースファイルを用意していない、またはその逆

ここのサイトに詳しいトラブルシュートが書いてある

ameblo.jp

引用

たぶん設定で変えられると思うのですが、Mavenではリソースの配置場所が最初からあらかじめ決められています。javaのソースファイルはsrc/main/java配下に、それ以外のリソースはsrc/main/resources配下に。他にもいろいろ決まっているので、気になる方はここ(Introduction to the Standard Directory Layout)を参照してください。つまり、classファイル出力先でjavaとxmlを一緒にしたい場合、src/main/java配下にHogeMapper.javaを作成したら、src/main/resources配下にHogeMapper.xmlを置く必要があったわけでした。

• 上記の場合は、Mavenで決められてるソースファイルやリソースファイルのディレクトリ仕様に従っていないから出るエラーでした。
• あとはおそらく、Mapperファイルに対応するソースファイルを用意していない、またはその逆をやらかした時に出るエラー

このディレクトリ仕様に関する話はどうやらMyBatisのドキュメントの方には書いてないようです。まあMyBatisのデベロッパーたちもまさかそんな間違いをされるとは思ってなかったのかも（そうしないでも動くことは動く）

エラーメッセージ："Mapped Statements collection already contains value for クラス名"

原因

• Mapperファイルの二重読み込み

上とは逆の話

stackoverflow.com

MyBatisは実行時にクラスパス上にあるすべてのXMLファイル(Mapper)を見ようとする。eclipseなどのIDEを使っている場合、生成された余計なクラスファイルを見に行った結果、２重にXMLを読み込んでいることがある。

XMLファイルの指定は様々だが、MyBatis+Springならば例えばこう

<bean id="sqlSessionFactory" class="org.mybatis.spring.SqlSessionFactoryBean">
    <property name="configLocation" value="/WEB-INF/config/mybatis-config.xml" />
    <property name="mapperLocations" value="/WEB-INF/classes/your/package/name/*.xml" />
</bean>

Mapper用のXMLファイルがMavenのsrc/main/resources以下に配置されていたものとする。その場合、Mavenビルドのシーケンス上 compileフェイズで target/classes 以下にクラスファイルとXMLファイルが吐かれる。同様にして、{生成されたアプリ名}/WEB-INF/classes/your/package/name/*.xml上にもマッパーファイルが吐きだされる。eclipseのJettyプラグインなどでこれを実行すると、本来は後者のXMLファイルのみを読み込むことを想定しているのだが、前者のXMLも後から読み込まれるのでこのエラーが出る。どちらかというとeclipseが余計なおせっかいをしている印象だ。とりあえずclassesディレクトリを削除してアプリを動かすと問題なく動くようになる。

まとめ

• Mavenのビルドファイルは開発の本筋とは関係ないけど、知っておくといろいろ便利なのでXML、書こう！

アルゴリズム学びフローを作成してみる

AOJの本

この本を買ってみた。プログラミングコンテスト攻略のためのアルゴリズムとデータ構造…

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

本の内容とレビュー

知識ゼロからはじめてもわかるように、アルゴリズムがだいたい順番に問題とともに紹介されている。昔paizaでA問題が解けないと悩んでいたが、それはこの本に載っているような、計算量を減らすためのアルゴリズムが組めていないことが原因であったと思う。

書籍の中ではAOJの例題が一緒に載っているので、文章を読んで理解した後に問題を実際に解いて腕試しすることができる。

見通しを立ててみる

書籍の中では、「このアルゴリズムを学んだら、次はこれに進めます」という情報が書いてある。ちょっとその情報をdraw.ioというサービスで絵にしてみた。（こういう風に、構造化していけば雑然とした概念がまとまるかなあという願望…）

図を書いていて思ったこと。

• 業務プログラミングでは、緑の線を出るか出ないかぐらいの知識しか使わない
• 自分は木構造とグラフと動的計画法の知識が足りない感じなので、そこをマスターしていく必要がある

高解像度版

プロコンで解いた問題を格納

今日は何か新しいことをやる気力が無くなったので、今まで解いた問題のコードを格納するリポジトリを作ってみた

github.com