載ってないテクニックを募集しています。 前提 と置く。 以降 と書いたらそれは虚数単位ではなく添え字である。 数列 に対し、その DFT を で定義する。 基本事項 以下の事実は式変形で確認できる。 関係式 に対し、 を で定義する。 このとき \begin{align}…

概要 最初空の数列 があり、以下のクエリを処理するアルゴリズムを説明する。 が与えられ、 の末尾に を追加する。 が与えられ、 の xor に関する基底 を出力する。 ただし の highest set bit を と定義したとき は について単調減少である。 時間計算量は…

概要 頂点の木の各頂点にモノイド の元 が乗っているとして、指定されたパス上の値の総積を計算するクエリが、前計算 、クエリ で処理できる。 アルゴリズム 重心分解を行う。 木の重心を とし、各 に対して、 パスから を除いたものに対するクエリ結果を計…

リハーサル MLE を見ようとして大量にメモリを取ったら PC が落ちたりして面白かった。 本番 ある程度関わった問題を何となく時系列っぽく並べる 問題文と解説: Regional | ICPC 2023 Asia Yokohama Regional B 親の顔より見た平均の式変形。 の小ささを利用…

とにかく使いたい人向け スコアとペナルティがどちらも整数とする。 *1 ペナルティを にしたときの最適値を と置く。 事実 ペナルティが の時の最適解がペナルティを受ける回数としてあり得るものは、区間 になっている。 事実 最小化 (ペナルティの度にスコ…

概要 長さ の数列 に対する区間 add と区間 min を時間計算量 で処理する、空間計算量 のデータ構造を説明する。 ただし、一連の操作における の最大値を としたとき、 の範囲の数を管理するために必要な空間計算量を としている。 例: 長さ の数列に の加算…

概要 長さ の広義単調増加な整数列 が与えられたとき、 を満たす広義単調増加な整数列 の個数 を の時間計算量で計算できる。 上記の設定に加えて の下限も与えられる場合も、同じ計算量で計算できる。 (, ), ? からなる長さ の文字列が与えられたとき、? を…

q-二項係数や Gaussian binomial coefficient などと呼ばれる概念がある。 q-Binomial Coefficient -- from Wolfram MathWorld Gaussian binomial coefficient - Wikipedia Q-analogs, q-Lucas theorem and q-Catalan numbers 詳細は上記のページなどを参照…

概要 項間の線形漸化式を持つ数列の第 項から 項までを の時間計算量で計算するアルゴリズムを説明する。 繰り返し二乗法と多項式の余り付き除算を用いる方法と比べると、定数倍が良いと思われる。 問題設定 が を満たすとする。 この記事内で多項式の除算を…

と定義する。 は中心二項係数と呼ばれていて、 である。これは天下りに与えられたものをテイラー展開で確認する以外の導出方法を知らない。 パスカルの三角形を思い浮かべると、 を つ足し合わせて が作れることに気付く。すなわち であり、ここから である…

Bostan, A., & Schost, É. (2005). Polynomial evaluation and interpolation on special sets of points. Journal of Complexity, 21(4), 420-446. の内容と、FFT で計算したときの計算量のメモ 2023/12/13: 計算量の定数倍を一部訂正(改善)しました Questi…

概要 [1] において解説されている、Newton 基底から Monomial 基底への変換のアルゴリズムを、転置原理無しで説明する。 問題は以下の通り。 体 上の 次未満の多項式 と、 個の値 が与えられる。 を満たす を求めよ *1。 これを の時間計算量で解く *2。 と…

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

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

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

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

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

\begin{align} \frac{P(x)}{Q(x)} &= \frac{P(x) Q(-x)}{Q(x) Q(-x)} \cr &= \frac{E(x ^ 2) + x O(x ^ 2)}{V(x ^ 2)} \end{align} であるから、 \begin{align} \left \lbrack x ^ k \right \rbrack \frac{P(x)}{Q(x)} &= \begin{cases} \displaystyle \left…

解法の説明は公式解説に任せるとして、いくつかの事実についての証明を書きます。 公式解説を見れてないのでどこが証明されてどこが証明されてないか分からない (もしかすると方針自体違うかも)。 治安が低いほど が大きいのが混乱の元なので、治安という言…

概要 問題の解法と、巧妙な (当社比) 定数倍高速化の方法を書く。 この高速化の方法は、heno239 さんに教えてもらった方法を式変形で導出しようとしていたら思いついた。 heno239 さんの手法は理解できていないので説明できないが、恐らく最終的に得られる式…

を長さ の文字列とする。 の部分列が何種類あるか数え上げる。 DP 定義 の部分列であって で終わるものの種類数 の部分列の種類数 (空列含む) DP 遷移 \begin{align} \text{dp} \lbrack i + 1 \rbrack \lbrack c \rbrack &= \begin{cases} \text{sum} \lbrac…

概要 LARSCH Algorithm の簡易版を思いついたので説明する。 時間計算量 だが実装や仕組みが単純で、コスト関数が sliding window でしか計算できない場合にも有用。 2024/03/13 追記: もっと簡単なアルゴリズムがあったのでこの記事はコストがスライドでし…