noshi91のメモ

データ構造のある風景

ABC339-F Product Equality の確率を保証する

から一様ランダムに素数 を選ぶ *1 。 となる 組の を固定し、誤判定する、すなわち となる確率を求める。 これは が で割り切れることと同値である。 の範囲に素数は 個存在する *2 。 一方、 であるから、 は範囲内の素因数を 個以下しか持たない。 よって…

FFT の回数を削減するテクニック集

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

push_back / suffix の xor 基底クエリ Θ(log(A))

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

木上の Disjoint Sparse Table

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

ICPC Yokohama 2023 参加記

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

Aliens DP における二分探索の色々

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

省メモリな区間 add 区間 min

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

上限付き単調増加列の数え上げ

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

メモ: q-二項係数

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…

転置原理なしで Monomial 基底から Newton 基底への変換

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

定数倍が最適な Mo's Algorithm

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

Disjoint Sparse Table に乗るのはやはりモノイドかもしれない。

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

(雑) 転置原理について考えたこと

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

消せる priority queue で消し過ぎない方法

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

Universal Cup. Stage 10: Zhejiang. A Atcoder Problem

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

メモ: Bostan-Mori 法で計算できるものまとめ

\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…

JOI 2022/2023 春季トレーニング 警備員 (Security Guard)

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

Universal Cup. Stage 5: Osijek. D Distinct Subsequences

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

部分列 DP メモ

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

簡易版 LARSCH Algorithm

概要 LARSCH Algorithm の簡易版を思いついたので説明する。 時間計算量 だが実装や仕組みが単純で、コスト関数が sliding window でしか計算できない場合にも有用。 問題設定 を Monge なコスト関数として、 \begin{align} \text{dp} \lbrack i \rbrack = \…

和を積に変換するテクニック

右辺は で計算できるので、時間計算量は問題にならないことが多いです。 使う場面 この式を使って和の和を積の和に言い換えると、分配法則が使えてやりやすくなることがあります。 ただし和の和も和の順序の交換などの良い性質を持つので、どちらが良いかは…

ICPC 2022 Asia Yokohama Regional 参加記

優勝しました。すばらしい! チーム編成 tatyam tatyam - AtCoder potato167 potato167 - AtCoder noshi91 noshi91 - AtCoder goodbaton さんが引退し、potato167 に新たに入ってもらった。 to 要素があったためチーム名は tonosama で続投。 開催まで 12/5 …

noshi91 が書いた AtCoder のユーザー解説一覧

Increasing Prefix XOR https://atcoder.jp/contests/arc141/editorial/4048 と を比較することで、答えの具体的な形を FPS を使って導出する。q-binomial coefficient と関係がある。 Stonks https://atcoder.jp/contests/abc250/editorial/3945 離散凸解析…

ICPC 2022 国内予選 参加記

potato167, noshi91, tatyam で参加しました。 tatyam 視点 → ICPC 2022/23 国内予選参加記 (tatyam 視点) | 東京工業大学デジタル創作同好会traP 初手 A: potato, B: tatyam, C: noshi で担当。noshi は実装が遅いので序盤の速度ゲーに触りたくないため、こ…

競プロにおける約数の個数の見積もり

概要 を満たす の正整数の約数の個数の最大値は 程度と思っておけば競プロの計算量の見積もりで便利そう。 実験 を の正の約数の個数として、 と定義し、 と の関係を見る。 つまり、 と見積もると実際 *1 にはその 倍から 倍程度に収まることになる。 例え…

アフィン部分空間の共通部分の計算

2022/05/02 記事中の記号の使い方やその他の軽微な修正をしました。 概要 のアフィン部分空間が の形で与えられるとき、 つのアフィン部分空間の共通部分を時間計算量 で計算する。 アフィン部分空間 ベクトル空間 の部分集合 は、部分空間 と によって と表…

Xorshift を用いた Zobrist hashing を衝突させる方法

概要 Xorshift によって生成された乱数列について、いくつかの場所の xor を取ると seed に依存せずに になる。 Xorshift Xorshift - Wikipedia 説明は Wikipedia に丸投げする。 本記事では簡略化のため、実装例の一番上にある周期 の実装について議論する…