概要 端の移動回数が 以下の Mo's Algorithm を思いついたので紹介する。 通常の Mo's Algorithm Mo's Algorithm の問題設定は以下のように言い換えられる。 を満たす格子点 が 個与えられる。 から始めて全ての点を通る経路を構成せよ。 経路の長さはマンハ…

昔の記事で Disjoint Sparse Table には半群が乗るという思想を言ったのですが、使う上ではモノイドにして空の区間に対応した方が嬉しいし、そもそも実装を変えると自然に長さ の区間に対応できることに気付きました。 お騒がせして申し訳ありません。 ACL …

転置原理の競プロでの使い方について考えたことを雑に並べた。 普段なら Twitter に書いているような内容だが、長かったので。 転置原理 非常に雑に言うと、以下のような定理である。 を 行列とする。「任意の 次元ベクトル を入力とし、 を計算する」ことが…

概要 std::priority_queue (binary heap) を つ持って、片方には削除待ちの要素を入れることで、実質的に削除ができるようにするテクニックがある。 ただし、これは invalid な削除も可能になってしまう。 つまり、存在しない要素 を削除する操作をした後に …

公式解説と違う方法で解いたのだが、その時に使った式変形が面白かったので紹介。 いくらかの計算をすると、次の問題に帰着される。 個の非負整数組 が与えられる。 これらは全て を満たす。 の先頭 項を で計算せよ。 追記 もっと簡単な方法が紹介されてい…