pythonで競技プログラミングの問題を解くのをやり始めたんですが、個人的によくコピペするやつをまとめました（TBD） 書いた人はPythonも競プロもハイハイ始めたくらいの初心者です。 １行に１つの入力を受け取る １行に複数の入力を受け取る 複数行に複数の…

pythonでのグラフとその探索の実装の仕方が分からず，悲しい思いをしたのでまとめました． グラフの入力 グラフの表現 グラフの入力 ノードとエッジに関する情報は，競技プログラミングでよくあるように以下の形式で与えられるとします． ノード（頂点）数は…

たまに見るウソつき問題にGW法という名前の万能の解法があることを知ったので，納得できるまで考えてみました． はじめに GW法の概要 GW法 まとめ 余談 はじめに ウソつき問題とは以下のようなタイプの問題です． 誰しも小学生の頃にクイズ本やテレビのクイ…

python3での再帰関数とメモ化についてまとめました． はじめに 例１：階乗 例２：ユークリッドの互除法を用いた最大公約数 本題：フィボナッチ数列 単純 末尾再帰 繰り返し 行列 メモ化 実行時間の比較 はじめに 再帰関数とは． 定義の中に，自分自身を呼び…

最小木問題を解くアルゴリズムのうち，プリム法をPython3で実装したのでメモ． プリム法の実装の理解だけでなく，matplotlibを使ったので良い練習になりました．wikipedia:プリム法 import matplotlib.pyplot as plt import random import numpy as np impor…