以前二分探索の正当性をCoqで証明しましたが，この証明スクリプトからOCamlのコードを抽出して実際に競プロに用いようとすると，添字の動く範囲が保証されていないので添字エラーを起こすこともしばしばでした． そこで，依存型を活用して添字の動く範囲も保…

遥か昔にもOCamlでダイクストラ法を実装したことはあったんですが， 最も近い頂点を線形探索で求めている手抜き実装なので，O(V2)の計算時間を要する（a.k.a. 疎なグラフに対しては遅い）ものでした． 競プロだと入力が疎なグラフに限定されている場面が多々…