競技プログラミング/コツ・テク - projecthikky @ ウィキ

競技プログラミングにおけるコツやテクや注意点や勉強法や練習法などをここに書いていく

---

実行時間の制限(TL)やメモリの制限(ML)を確認する

問題文のページなどに実行時間の制限(TimeLimit)やメモリの制限(MemoryLimit)が書かれている
アルゴリズムに詳しくなってくると、これらの制限の大きさがアルゴリズムを選択するヒントになることがある
例えば

• 制限が十分に緩いので愚直な全探索で間に合う
• 制限が厳しいので愚直な全探索では間に合わない
• etc..

---

チラ裏やノートなどにメモしたり図示したりしながら問題を解く

紙などにアウトプットすることによって思考が整理しやすくなるらしい
例えば

• グラフ問題などでNの小さいケースを全部を図示してみたり
• 数学っぽい問題で数式を変形して漸化式などを求めたり
• Nの小さいケース全部の答えを並べて法則性を見つけ出したり
• 2人ゲームみたいなタイプの問題のパターンを列挙してみたり
• etc...

---

標準ライブラリを活用する

QueueやStackやHashSetやHashMapやPriorityQueueなどのデータ構造コレクション
sinやcosやlogやexpなどの数学系
任意精度整数(BigInteger)
こういったものは比較的よく使う

プログラミングの世界にはセキュリティ(暗号)の分野で
合同式(Mod Int)の計算や素数を扱うことがある
それに関係するものが標準ライブラリについてるプログラミング言語もある

例えばJavaはBigIntegerクラスは以下のメソッドが存在する

• GCD(最大公約数)の計算
• 素数判定
• ModPow (累乗の余り)　の計算
• ModInverse (逆数/逆元の余り)　の計算

例えばPythonでは
powは第３引数でModを指定で累乗や逆数の計算ができる
mathにはsin,logなどのほかにgcd計算や順列やユークリッド距離を求めるものもある
fractionsを使えば分数の形の計算もできる
cmathをの複素数を使って２次元平面を極座標で計算することもできる
itertoolsを使えば順列やコンビネーションの列挙もできる

例えばRubyには
https://docs.ruby-lang.org/ja/2.6.0/library/index.html#Math
素数を扱うPrimeライブラリは素因数分解や素数列挙や素数判定ができる
複素数や行列やベクトルを扱えるライブラリもある
Tarjanのアルゴリズムで実装されてるトポロジカルソートや強連結成分分解のライブラリもある

例えばHaskellにはグラフを扱うData.Graphライブラリがあって
深さ優先探索や強連結成分分解やトポロジカルソートなど他にも色々な関数がある

PythonでScipy等の外部ライブラリを使用できるオンラインジャッジでは
Scipyに実装されてるアルゴリズムやデータ構造なども利用できる(？)
https://docs.scipy.org/doc/scipy/reference/sparse.csgraph.html#module-scipy.sparse.csgraph

(連結成分？)
connected_components(csgraph[, directed, …]) Analyze the connected components of a sparse graph
laplacian(csgraph[, normed, return_diag, …]) Return the Laplacian matrix of a directed graph.
(最短距離のパス)
shortest_path(csgraph[, method, directed, …]) Perform a shortest-path graph search on a positive directed or undirected graph. 
(ダイクストラ)
dijkstra(csgraph[, directed, indices, …]) Dijkstra algorithm using Fibonacci Heaps 
(ワーシャルフロイド)
floyd_warshall(csgraph[, directed, …]) Compute the shortest path lengths using the Floyd-Warshall algorithm 
(ベルマンフォード法)
bellman_ford(csgraph[, directed, indices, …]) Compute the shortest path lengths using the Bellman-Ford algorithm. 
johnson(csgraph[, directed, indices, …]) Compute the shortest path lengths using Johnson’s algorithm.
(幅優先探索)
breadth_first_order(csgraph, i_start[, …]) Return a breadth-first ordering starting with specified node. 
 (深さ優先探索)
depth_first_order(csgraph, i_start[, …]) Return a depth-first ordering starting with specified node. 
(幅優先探索)
breadth_first_tree(csgraph, i_start[, directed]) Return the tree generated by a breadth-first search 
（深さ優先探索)
depth_first_tree(csgraph, i_start[, directed]) Return a tree generated by a depth-first search.　
(最小全域木)
minimum_spanning_tree(csgraph[, overwrite]) Return a minimum spanning tree of an undirected graph 
reverse_cuthill_mckee(graph[, symmetric_mode]) Returns the permutation array that orders a sparse CSR or CSC matrix in Reverse-Cuthill McKee ordering.
(最大流？)
maximum_flow(csgraph, source, sink) Maximize the flow between two vertices in a graph. 
（最大二部マッチング？)
maximum_bipartite_matching(graph[, perm_type]) Returns a matching of a bipartite graph whose  oardinality is as least that of any given matching of the graph.　
structural_rank(graph) Compute the structural rank of a graph (matrix) with a given sparsity pattern.

https://docs.scipy.org/doc/scipy/reference/spatial.html

Delaunay(points[, furthest_site, …])  Delaunay tessellation in N dimensions.
ConvexHull(points[, incremental, qhull_options]) Convex hulls in N dimensions.
(ボロノイ)
Voronoi(points[, furthest_site, …]) Voronoi diagrams in N dimensions. 
SphericalVoronoi(points[, radius, center, …]) Voronoi diagrams on the surface of a sphere.
HalfspaceIntersection(halfspaces, interior_point) Halfspace intersections in N dimensions.

Spatial algorithms and data structures (scipy.spatial)
Spatial Transformations
Nearest-neighbor Queries
Delaunay Triangulation, Convex Hulls and Voronoi Diagrams
Plotting Helpers
(シンプレックス法？)
Simplex representation