Atcoder Python便利技集
出力
リストを半角スペース区切りで一行で出力
リストを指定した区切り文字で出力(半角、カンマ)
この場合最後もカンマがついてしまうのでif文使うなどで調整が必要ですね。
内包表記
後日記載
順列・組み合わせ
順列の...
アルゴリズム
Atcoder Atcoder 【Python】ユークリッドの互除法で最大公約数を求める【アルゴリズム】
ユークリッドの互除法について
概要
最大公約数を求めるアルゴリズム
greatest common divisorの頭文字をとってgcdと表記されることがある
コード
yが0の時
yが0の時、xを返します。す...
Atcoder 【Python】AtCoder Beginner Contest214 A,B問題 解答
A - Bitwise Exclusive Or
Pythonは a^bとすることでXOR演算が可能です。
B - Booby Prize
list2のブービー値からリストのインデックスを取得
list2は並べ替え後の...
Atcoder 【Atcoder】競プロ典型90問に挑戦
競プロ典型問題90問に挑戦していきます
002 - Encyclopedia of Parentheses（★3）
方針
Nの数が小さく、制約が小さいので全探索を考える
bit全探索で考える
解答
007 -...
Python 【Python】ベルマン・フォード法【アルゴリズム】
ベルマン・フォード法について
概要
最短経路問題を解くために使われる
頂点を結んだ辺の重みを更新しながら解いていく
辺の値が負の値でも使える
流れ
辺を選ぶ
辺の両端にあるコストを更新する
...
Python 謎ソート
minとかpopとか使って良いのか？
Python 【Python】クイックソート【アルゴリズム】
クイックソートについて
概要
分割統治法に分類される
計算量はO(nlogn)〜O(n^2)
計算量はピボットの選択により変動する
ちょうど半分になるような値をピボットとして選ぶと効率が良い
他のソートア...
Python 【Python】マージソート【アルゴリズム】
マージソートについて
計算量はO(nlogn)
大容量のデータにも使える
リストの各要素を新しいリストとしてバラバラにした後で統合していく
統合は2つのリストを使って行うことを繰り返す
統合時は各リストの先...
Python 【Python】バブルソート【アルゴリズム】
バブルソートについて
計算量はO(n^2)
リストの先頭から順に2つの要素の大小比較し、大きい方の要素がリストの先頭に近ければその2つの要素の位置を入れ替える
先頭から前述の比較と入れ替えを繰り返す
最大の要素が...
Python 【Python】挿入ソート【アルゴリズム】
挿入ソートについて
始めに先頭の要素はソート済みとする
2つ目の要素から順に並べ替えを行い、ソート済みとしていく
ソート対象の要素に対して、ソート済みの要素を後ろから順に大小比較して並べ替え先を調べる
並べ替え先...