競プロ用の個人的なメモ

はじめに

この記事は個人的なメモです．
随時更新予定なので，内容が増えたり減ったりします．

競プロで押さえておくべきポイント？

AtCoderのABCに何度か挑戦してみたところ、300点以上の問題では必要とされる技能は3つに分解できそう．

1. 提示された問題文から真に行うべき操作を見出し，知っているアルゴリズムをどう適用するか
2. データ構造とアルゴリズムの知識
3. 実装する言語の計算量の理解

1.に関しては文書化する方法を見いだせていないため書かない．
そのため本記事では2.と3.を扱う．3.ではpython3について扱う．

データ構造とアルゴリズム，他

データ構造

List

ArrayListとLinkedListのものがある?

ArrayList

各要素を連続に配置しておき，途中の要素の位置を計算で割り出せる
ランダムアクセスが高速だが途中への要素の挿入，削除では不利？

LinkedList

各要素が次の要素の位置を持つことで鎖のようにつながるイメージのデータ構造
要素の挿入・削除は高速だがランダムアクセスは不利？

圧縮 / 符号化

ランレングス圧縮 / ランレングス符号化

データ列の同じ値が連続するものをまとめて表す圧縮/符号化手法．
0000111101といったデータの場合，[(0,4), (1,4), (0,1), (1,1)]といった形式に置き換える．

アルゴリズム

DP / 動的計画法

Dynamic Programmingの略，日本語では動的計画法．
理解しやすい説明がこちらにありました．
https://qiita.com/drken/items/dc53c683d6de8aeacf5a

Python3

list

他記事を参考にする限り，後方からの1方向LinkedList
listの先頭に対してのアクセスは計算時間が大きくなる．

collections.deque

競プロ系python記事でよく見かける
https://docs.python.org/ja/3/library/collections.html

heapq

pythonでPriority Queueを扱いたい場合に出番がある