座標圧縮の解説（1次元から2次元の圧縮まで）

座標圧縮は、座標の情報から、位置関係や大小関係だけ抽出するテクニックです。 仮に座標の範囲が非常に広い場合、以下のような不都合が生じてしまいます。 例：\(0\) ~ \(10^9\) の数直線はメモリにのらない例：\(10^9 \times 10^9\) の領域はメモリにのらない このような状況では、情報を圧縮しなければ探索などを行うことができません。 情報のない空白部分が連続している場合、不要

ダブリングの基本概念とその応用

ダブリングは、全体の要素数がN個あって1回移動した時にどの要素に到達するのか定まっているとき、「K個先の要素を求めるのに \(O(K)\) かかる」ような状況において 前処理：\(O(N \log K)\) 時間, \(O(N \log K)\) 空間クエリ：\(O(\log K)\) で行うことができるようにするアルゴリズムです。 繰り返し二乗法もダブリングの一種と捉えることができ、最近共通祖先

D – Teleporter 解説 (AtCoder Beginner Contest 167)

問題へのリンク 問題概要 町が \(N\) 個ある。町 \(i\) から町 \(A_i\) に移動することを K 回繰り返す。町 1 から始めた時、最終的にどの町にたどり着くか？ 制約 \(2 \leq N \leq 2 \times 10^5\)\(1 \leq A_i \leq N\)\(1 \leq K \leq 10^{18}\) 考え方 単純にシミュレーションをしようとしても、\(K\)

再帰関数を用いた深さ優先探索(DFS)による全探索アルゴリズム

forループを用いた全探索などは比較的簡単な内容なので直感的にもわかりやすいですが、簡単なものしか全探索できません。 複雑な条件や構造を持つものを全探索したい場合には、再帰関数を用いた深さ優先探索(DFS)を用いる必要がある場合があり、競技プログラミングなどで良く出題されています。 前提知識 今回の内容を理解するために必要なことを簡単に説明しておきます。 再帰関数とは 再帰関数を詳しく考えようとす