読者です 読者をやめる 読者になる 読者になる

プログラミングコンテストでのデータ構造 2

情報オリンピックの春合宿で「プログラミングコンテストでのデータ構造 2」というタイトルで講義をさせてもらいました.スライドは以下になります.

平衡二分探索木の話と動的木の話をしました.アルゴリズム的な説明だけでなく,実際にコードにする際に楽に実装するためのポイントにも重きをおいています.実装に関する話は,アルゴリズム系の講義資料等にはあまり書かれることが無いため,珍しい資料になっているかと思います.(そもそもとして動的木の話は珍しいですが…)

プログラミングコンテストでの」というタイトルになっていますが,平衡二分探索木・動的木が本当に必要になる問題は少々稀で,プログラミングコンテストに関する話としてはかなり進んだ話になっています.一方,プログラミングコンテストに限らず,それらを実装したいと思っている人には少なからず役立つと思います.

タイトルの末尾に「2」がついているのは,同タイトルの講義を一度やっているからです.その時は,Union-Find 木,セグメント木,バケット法の話をしました.その時の資料も公開していますので,よければご覧下さい.