スライド・録画はこちらからどうぞ。

第零回

• level ancestor problem の〈O(N), O(1)〉アルゴリズム（37zigen）
  • long-path decomposition やダブリングなど色々なテクニックが詰まっています。
• SMAWK Algorithm とナップザック（熨斗袋）
  • 重みの種類数が小さいとき、SMAWK アルゴリズムによって高速にナップザック問題を解く Axiotis–Tzamos　のアルゴリズムを解説。
• O(1) RMQ（ながたかな）
  • Range Minimum Query をクエリ当たりO(1)で解くアルゴリズムを解説。
• Incidence algebra and Mobius inversion（maspy）
  • 隣接代数入門。ゼータ／メビウス変換などがより高い視点から見れるようになります。
• Dominator Tree（けんしん）
  • Dominator Tree の定義からそれを求めるアルゴリズムまで丁寧に解説。

第一回

概要

• 最大独立集合（37zigen）
  • 最大独立集合のアルゴリズムの設計や計算量解析のテクニックを紹介。
• 爆速 multipoint evaluation（tko919）
  • 転置写像を経由して multipoint evaluation を高速化。
• 数え上げと解析学（maspy）
  • 複素解析を駆使して数え上げた通り数がどのぐらいに大きさになるのか評価。発表者によるアブストラクトも。