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

この本を、折角の無職期間なのでじっくり進めた。

AOJ の設問が題材なので、タイポや勘違いを正しながら理解を深められる。初見でないものもあったが最初から1問ずつ解いた。印象に残ったものを幾つか挙げる。

コッホ曲線

与えられた2頂点を元に、コッホ曲線の頂点を算出して出力する。三角関数のよい復習になったが、これを書いている今、また頭から抜け落ちてる。

動的計画法の典型的な問題。動的計画法は得意でも不得意でもないけど、久々に手を付けようとすると何から進めればよいか分からない状態になってしまう。つまり何も分かっていないということ。仕事に復帰したら活用できるところを意識的に探るようにする。

初めてのプリム法。ダイクストラ法共々優先度付きキューを使うと高速化できる。C++のpriority_queueの優先度付きキューの並び順どっちだったかなとなるのは私だけだろうか。ダイクストラと併せて基本的な形から手に染みこませておきたい。

互いに素な集合の構築。初見だったがシンプルに実装できたので感心した。

ベクトルで位置関係を確認しながらアンドリューのアルゴリズムを使う。素でできる気がしない一品。

IDA*, A*の理解に約1日掛けた。8パズルだと素でも解けたが流石にこれは厳しかった。再帰やスタックよりもキューを使う解き方を好むが、優先度付きキューを使うとメモリ制限を超えてしまった。

今確認すると3月〜6月に掛けて本を進めていた。

タイトルに「終えた」と付けたが、今後は書いたコードを整理しつつ自分のコレクションとしていく作業を続ける。