甲斐性のない男が機械学習とか最適化とかを綴るブログ

うどんくらいしか食べる気がしない

アルゴリズム

競プロとかに使うアルゴリズム実装メモ(幅優先・深さ優先探索、union-find、最小全域木)

はじめに 以前の記事にて最短経路問題を解くアルゴリズムの実装を書きましたが、今回はその続きとしてグラフアルゴリズムの中でも幅優先探索、深さ優先探索、union-find、最小全域木問題を解くアルゴリズム2種について実装を書いていきます。 例によって、自…

競プロとかに使うアルゴリズム実装メモ(最短経路探索系)

はじめに ここ1年くらい、ちまちまとatcoder中心に競技プログラミングに参加してたりします。ABCのD問題を解くのがやっとなのにAGCに突撃して爆死するってことを繰り返し続け、未だに緑コーダーです(パフォーマンスも1200前後がやっと)。こりゃまずいとい…

動的計画法でテキストセグメンテーション

いやいや、お久しぶりです。 実に半年以上も更新が滞ってました。 ちゃんと生きてます。以前、動的計画法によるシーケンシャルデータのセグメンテーションという記事を書きましたが、 今回はそれを応用して、テキストセグメンテーションを行おうと思います。…

【Python】動的計画法によるシーケンシャルデータのセグメンテーション

学生の頃、表題のアルゴリズムを研究に応用しようとしていましたが、すっかり忘れているので、思い出すために改めてPythonで実装してみました。当時は、matlabでfor文を回して実現していましたが、今回は、勉強がてらラムダ式やら再帰呼び出しやらを駆使して…