単純無向グラフ $G = (V, E)$ に対し、頂点と辺の個数を $n, m$ 、平均次数を $\Delta$ で表します。 このとき、グラフ $G$ にはサイズ $\Omega(n / \Delta)$ の独立集合が存在します。 そして、そのような独立集合を線形時間、すなわち $O(n + m)$ 時間で計算できます。 今回はそのアルゴリズムを紹介します。

出たコンテストで初めて見るタイプのDPがあって頑張って理解したのでゆるく証明します。

簡単に言うと、以下の形のDPに対して $\mathrm{dp} (n, k)$ を $O(n k^{\frac{3}{4}})$ 時間で求められるという主張です。

$$ \mathrm{dp} (i+1, j) = \max_{1 \leq d \leq j} \left\{ \bigcirc \cdot \mathrm{dp} \left(i, \left\lceil \frac{j}{d} \right\rceil \right) \right\}. $$

競プロ典型90問「017 - Crossing Segments（★7）」の別解になります。 本質的には同じことをやっていたらすみません。

一般的に、CPUにおける整数の除算（割り算）は遅いです。

そのため、コンパイル時定数で割る処理を書くと、コンパイラが「乗算とビットシフト」を用いた高速な処理へ変換します。

この記事では、その具体的な変換方法と正当性を示します。