2020年5月19日その他二次元, 座標圧縮

座標圧縮は、座標の情報から、位置関係や大小関係だけ抽出するテクニックです。

仮に座標の範囲が非常に広い場合、以下のような不都合が生じてしまいます。

例:\(0\) ~ \(10^9\) の数直線はメモリにのらない

その他, その他競プロ, LCA, ダブリング, 繰り返し二乗法

ダブリングは、全体の要素数がN個あって1回移動した時にどの要素に到達するのか定まっているとき、「K個先の要素を求めるのに \(O(K)\) かかる」ような状況において

前処理:\(O(N \log K)\) 時間, \(O(N ...

探索

forループを用いた全探索などは比較的簡単な内容なので直感的にもわかりやすいですが、簡単なものしか全探索できません。

複雑な条件や構造を持つものを全探索したい場合には、再帰関数を用いた深さ優先探索(DFS)を用いる必要があ ...

その他圧縮, 復元, ランレングス圧縮

ランレングス圧縮(ランレングス符号化)とは、データの圧縮方法の一つで、圧縮前に正確に復元することができる可逆圧縮の一種です。

同じ文字が連続して何文字出現するかに変換します。

例:

In: aaal ...

グラフグラフ, 有向グラフ, 閉路, 最小値, BFS, ベルマンフォード法, ダイクストラ法

アルゴリズム

最小コストの閉路:

任意の辺 e = (u,v) について以下を繰り返すグラフ G から e を取り除く
v から u への最短経路 d を求める(ダイクストラ/BFS など)
d+cost(u, ...

2020年4月3日動的計画法動的計画法, , テーマ記事, 競プロ, モノイド, 結合則, 木DP, 部分木, 全方位木DP, 単位元

競技プログラミングでよく出題される木DPについての説明と、それを同じ計算量で全頂点について求められるように応用した全方位木DPについて解説します。

木DP基本的な考え方とイメージ

木DP とは、根を一つ固定した木について、以 ...

2020年3月30日グラフグラフ, 重み付きグラフ

任意の2頂点間の最短距離を求める問題を全点対最短経路問題といいます。

ワーシャル・フロイド法は、動的計画法を用いて全点対最短経路を求める有名なアルゴリズムです。

負の辺が含まれていても動作する
負の閉路がある場 ...

数学全探索, 素因数分解, 約数の個数, 平方数, 平方根

Nが自然数の2乗で表現できるとき、平方数と言います。

平方数の例4 (= 2×2)
9 (= 3×3)
16 (= 4×4)
25 (= 5×5)
アルゴリズム

全探索でのアルゴリズム ...

数学約数, 素因数分解, 約数の個数

素因数分解を用いることで、約数の個数を簡単に求めることができます。

アルゴリズム

Nの約数の個数:

N を素因数分解する
それぞれの指数に1を足す
「2.」で得られたものを全てかけ合わせる

グラフグラフ, 貪欲法, 最小全域木, プリム法

無向グラフ \(G=(V,E)\) について、\(G\) の部分グラフ \(T\) が以下を満たす時、\(T\) は全域木(Spanning Tree) と言います。

\(T\) は木
\(T\) では\(V\) の任意の ...