Atcoder Atcoderを解くときに意識すること
Atcoderを解くときに意識しておくことを箇条書きでまとめています。
問題の理解
問題文をよく読む
問題文が理解できなくても入力例を読む
複雑な問題は簡単な部分問題に分割する
簡単な例を挙げてみる
解法...
プログラミング
Atcoder Atcoder Python便利技集
出力
リストを半角スペース区切りで一行で出力
リストを指定した区切り文字で出力(半角、カンマ)
この場合最後もカンマがついてしまうのでif文使うなどで調整が必要ですね。
内包表記
後日記載
順列・組み合わせ
順列の...
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 -...
Atcoder AtCoder Beginners SelectionにPythonで挑戦
この記事では、AtCoder Beginners SelectionにPythonで挑戦します。
Atcoderに登録したものの、次に何をすれば良いのかわからない方に向けて、Atcoderから最初に解いてみると良いよということで用意し...
Python 【Python】ベルマン・フォード法【アルゴリズム】
ベルマン・フォード法について
概要
最短経路問題を解くために使われる
頂点を結んだ辺の重みを更新しながら解いていく
辺の値が負の値でも使える
流れ
辺を選ぶ
辺の両端にあるコストを更新する
...
Python 【Python】クイックソート【アルゴリズム】
クイックソートについて
概要
分割統治法に分類される
計算量はO(nlogn)〜O(n^2)
計算量はピボットの選択により変動する
ちょうど半分になるような値をピボットとして選ぶと効率が良い
他のソートア...
Python 【Python】マージソート【アルゴリズム】
マージソートについて
計算量はO(nlogn)
大容量のデータにも使える
リストの各要素を新しいリストとしてバラバラにした後で統合していく
統合は2つのリストを使って行うことを繰り返す
統合時は各リストの先...
Python 【Python】ヒープソート【アルゴリズム】
ヒープソートについて
計算量はOlog(n)
ヒープを構成する分を含めると計算量はO(nlogn)となる
ヒープは木構造で表される
2分木構造のヒープは2分ヒープと呼ばれる
ヒープの子ノードは常に親ノードと...