2800 到達時の記録 AtCoder で rating が 2800 に到達しました - noshi91のメモ AtCoder Performances, AtCoder Scores, rating-history などがサービス終了しており寂しさを感じました。 AtCoder AtCoder Charts AtCoder Problems
関連記事 Lagrange inversion theorem - Codeforces [Tutorial] Generating Functions in Competitive Programming (Part 2) - Codeforces 公式集 注意: 一応証明したつもりですが、係数環を一般の可換環に取るところが怪しいです : 可換環 逆関数の係数 \be…
単調増加な正実数列 によって定義される関数 は Monge であることを示せ。 てんぷらによる証明 https://x.com/tempuracpp/status/1854498278190285099 区間の平均値 を定義すると、 である。 \begin{align} & & f(l _ 0, r _ 0) + f(l _ 1 , r _ 1) & \leq f…
グラフ理論ではないしグラフですらない。列。 解法 両端にダミーの頂点を追加すると、操作 は操作 で表現できる。 よって操作 だけを考えればよい。 最初の頂点も操作 で作ることにすれば、問題は以下のように言い換えられる。 頂点 つが辺で結ばれている。 …
問題設定 無向グラフ , 非負の辺重み , 始点 , 終点 が与えられる。 各 について、 上での 最短路長を求めよ。 この問題を の時間計算量で解くアルゴリズムを説明する。 本質的に同じ問題が https://codeforces.com/contest/1163/problem/F で出題されており…
概要 要素の集合を つに分割することを 回行って、どの 要素もどこかで分離されているようにすることができる。 向きの付いた分割についても同様の問題を考え、それぞれの構成法と最適性を示す。 向きの無い分割 問題例 無向グラフ があり、各辺には正の重み…
問題 文字集合を とする文字列 と がある。 の長さ の連続部分列のそれぞれについて、 にマッチするか判定せよ。 ただし文字列がマッチするとは、それぞれの文字列中の を好きな文字に置き換えたときに両文字列が一致することを指す。 解法 (Clifford & Clif…
概要 半順序集合の最大反鎖の計算は通常、Dilworth の定理を用いて最小パス被覆に帰着し、そこから更に二部マッチングへの帰着を行う。 本記事では (最終的にかなり近いアルゴリズムにはなるものの) 直接最小カットに帰着する手法を説明する。 また関連する…
次元遅延セグ木は (かなり制限した設定でも) 実現不能と考えられている (以下の資料を参照せよ)。 勉強会をしました。今日のテーマは「2次元セグメント木」です。スライドを公開します。https://t.co/tL8fMsdBv3— こたつがめ (@kotatsugame_t) 2024年3月18日…
概要 cp-unspoiler この問題の公式解説にある補題群を冪級数を用いて証明する。 定義 この記事内では以下のように定義する。 また、列の大小関係を辞書順で定める。 辞書順関連 を十分小さい正の実数とし、 を で定める。 このとき について となる。 定理 :…
概要 温めておいたのですが、ABC で似た問題が出題されてしまったので (想定解は違いましたが) 起源が問題になる前に公開しようと思います。 問題 標数の十分大きい体 上の形式的冪級数 の 次までの項が与えられる。 を求めよ。 ただし、 を係数とする次数 …
から一様ランダムに素数 を選ぶ *1 。 となる 組の を固定し、誤判定する、すなわち となる確率を求める。 これは が で割り切れることと同値である。 の範囲に素数は 個存在する *2 。 一方、 であるから、 は範囲内の素因数を 個以下しか持たない。 よって…
載ってないテクニックを募集しています。 前提 と置く。 以降 と書いたらそれは虚数単位ではなく添え字である。 数列 に対し、その 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…
