【まとめ】アルゴリズム的思考力が身につく！Atcoder ①
アルゴリズムの勉強のために以下の本を読んだので、読んでいた時のメモ
中級編
バケット・連想配列
バケット
num[v]← 配列Aの中の値のvの個数 vは正の整数に限られる！
配列Aから直接数えてもいいけど、setにAの値入れて行って要素数数えると楽 計算量O(1)
連想配列
num[s] ←文字列sが何個あるか
添え字が文字列でも使える便利
Python3ではcollections.defaultdict型を使う
(一般的にはdict使うけど、競技プログラミングでは存在しないキーの値も定義してた方が便利らしいので)
Python3では、度数分布を作るのに特化したcollections.Counterもある。これ使うと楽(p180)
区間分割・連長圧縮
区間分割は、N個の要素を区間で分割すること。高校数学のp+q+r＝Nの組み合わせ問題みたいなやつ？
連長圧縮は、AAABBBBAACDD→(A,3), (B,5),(C,1),(D,2)みたいに変換すること
実装上はj<N, i<Nにおいて、初めて文字S[j] != S[i]になるiを探せば良い
グラフ
向きがついてないグラフ：無向グラフ
矢印がついてるグラフ：有向グラフ
プログラムにおいてグラフは、
無向グラフ 頂点vと結ばれた頂点のlist
有向グラフ 頂点vから矢印→が伸びた頂点のlist
として扱う。
これらvを縦に並べると、二次元配列として扱える。
グラフの問題では、以下のフォーマットが入力になる。
N M 頂点数, 辺の数
u[0] v[0]
・ i番目の辺が頂点uiとviを結んでる
・
・
u[M-1] v[M-1]
グラフを表す二次元配列Gの頂点xに隣接する頂点の配列はG[x]と表せる
累積和
いわゆる数Bに出てくる数列S(n)(PythonではS[n], A[1]〜A[n]の和)
区間クエリはS[p]-S[q]みたいに計算すればいい
区間クエリをN個計算するためには、
各クエリで区間内の値を単純に足すとO(NQ)
累積和使うと、累積和(いわゆる一般化したもの)計算するのにO(N)、クエリ一回あたりはO(1)なので、トータルはO(N+Q)
Discussion