放送大学の問題解決の数理で学んだアルゴリズムの覚書。 ダイクストラ法とは 計算量 処理概要 ソースコード 定式化 定式化例題 参考 ダイクストラ法とは 2頂点間の最短距離を求める。 重みがマイナスだと使えない。 計算量 O(頂点数2) （オリジナルの場合） …

cmp_to_keyの実装 例題 参考サイト cmp_to_keyの実装 比較対象の2つの値を引数として、第一引数が第二引数よりも小さければ負の値、大きければ正の値、等しければ0を返すように実装します。 from functools import cmp_to_key def compare(arg1, arg2): #数…

幅優先探索（BFS）とは 使い所 ソースコード 参考サイト 例題 幅優先探索（BFS）とは 幅優先探索とは、グラフや木構造を探索するためのアルゴリズムの一つで、探索を開始する頂点から近い順に探索する方式。 幅優先探索（BFS / 横型探索）とは - 意味をわか…

グラフ問題の考察や解法でよく使いそうなものをメモ。 連結成分の個数を数える サンプルコード（無向グラフ） 例題 参考サイト 閉路検出 参考サイト 木構造 頂点の深さ計測 参考サイト 最短経路＆経路復元＆距離計測 連結成分の個数を数える 全ての頂点から…

C問題にめちゃくちゃ苦戦したのでメモ。 atcoder.jp 解法 解答コード 参考サイト 解法 約数列挙問題。 文字起こしがしんどいので、画像で許して。 とりあえず「ABの約数の個数×CDの約数の個数」が答え。 思考過程 解けたとき気持ちよかったｗ 解答コード # N…

約数の数を知りたいなあ、という時にすぐ使えるようにメモ。 ソースコード 参考サイト ソースコード # N の約数をすべて求める関数 def calc_divisors(N): # 答えを表す集合 res = [] # 各整数 i が N の約数かどうかを調べる for i in range(1, N + 1): # √…

AtCoderで試しにPythonを使ってみることにしたのでメモを。 主に競技プログラミングで必要になることを箇条書き。 標準出力 標準入力の受け取り 内包表記 演算子 データ型 listの操作一覧 dict型（連想配列）の操作 defaultdict set(集合）の操作 優先度付き…

itertoolsで全部いける！ Javaバージョン itertoolsで全部いける！ import itertools # 直積 ネストしたforループと同じ 0～3の数字の全通り。SQLで言うところのCROSS JOIN # repeat=for文のネスト数と同じ。つまり数列の桁数。3*3*3=27 for product in iter…