ベルマンフォード法とは 蟻本によれば、「重み付き有向グラフにおける単一始点最短路アルゴリズム」 つまり、「始点s から各頂点i までの最短コストを求める」アルゴリズムです。 以下の条件で使えます。 DAG（有向グラフで閉路を持たない）である 負のコス…

今の所の個人的なベストプラクティス 行き詰まっているとき 誰かに相談する 独り言を言う やりすぎるとクビが飛ぶらしい 歩行運動しながら考える（とにかく席を立つ） やる気が起きないとき さっさと家を出る（家にいる場合、最優先でこれをすること。家以外…

Union-Find木とは Union-FindまたはDisjoint Setとは、蟻本の言葉を借りると「グループ管理のためのデータ構造」。 ・要素aと要素bが同じグループかどうか ・aが属するグループと、bが属するグループを併合(unite)する ということをしたいときに使います。 U…

散々語り尽くされていますが、リストの先頭に対する要素の挿入（insert）や要素の削除（pop）の計算コストはO(N)かかります。このことは公式ドキュメントのcolections.dequeの説明に記載されていているのでその該当箇所を引用すると、 docs.python.org list …