ブログ名

競技プログラミングやお歌のお話をする高菜です。

負の添字を持つ対称な DP 配列を「半分だけ」管理する方法($x ^ i + x ^ { -i }$ で表す) 

概要 負の添字を持つ対称な解配列と対称な遷移を持つ DP を行うにあたって、解配列の上半分だけを管理する方法とその注意点をご紹介します。 要するに DP 配列の母関数が $x \mapsto x ^ {-1}$ で不変な Laurent 多項式であるときです。 結論 $i \to i + j, …

proconio を使わない Rust の標準入力(Rust 1.61 ~ Rust 1.65 の一連のアップデートについて)

概要 Rust は標準入力が難しめの言語と言われがちです。たしかに競技プログラミング文脈に限れば C++ や Python に比べてややややこしいことは否めませんが、今の嫌煙され方は過剰だと思っております。そこ私が標準入力の「今」をご紹介して、コワクナイヨというこ…

yukicoder No.417 チューリップバブル の $O(NM)$ 時間解法

問題 No.417 チューリップバブル - yukicoder 解法 この解法は 木上のナップサック問題 #アルゴリズム - Qiita の「応用」で言及されているものと全く同じだと思います。↓でご指摘いただきました。 参考文献の応用のところに同じことが言及されていませんか…

Splay 木ベースの Link-Cut 木の計算量解析

Splay 木の計算量解析 - ブログ名 の続編的な記事です。数年ブログをやっていて、続編が実際に出たのは初めてですね。(あの?) Link-Cut 木概論 Link-Cut 木は根付き森を管理するデータ構造です。 Link-Cut 木は内部的に、preferred path と呼ばれる節点素…

Karatsuba 法を非再帰かつ一列に並んだ $O(n)$ サイズのメモリで実装する試み

概要 この記事では特に断りがない限り $n$ は常に $2$ 冪であるとします。 Karatsuba 法と呼ばれる長さ $n$(つまり次数 $n - 1$ 以下)の多項式同士の積を $O(n ^ { \log _ 2 (3) })$ time で計算するアルゴリズムが知られています。本記事では係数のサイズ…

セグメント木を図示する7つの方法

概要 セグメント木を図示する方法を、有名なものを中心にマイナーバリエーションをいくつかご紹介します。ほとんど大喜利のような記事ですが暖かい目でぜひです。 以下、特に断りが無い限りすべて $n = 11$ の場合の図です。 方法1 $2$ 冪の枠に当てはめる…

【図解】$0 ≤ L < R < N$ なる整数の組 $(L, R)$ を一様ランダムに生成する方法

問題 問題1 $2 ≤ N$ なる整数 $N$ が与えられます。$0 ≤ L < R < N$ なる整数の組 $(L, R)$ なる $(L, R)$ を一様ランダムに生成する方法を示せ 問題2 $1 ≤ N$ なる整数 $N$ が与えられます。$0 ≤ L ≤ R < N$ なる整数の組 $(L, R)$ なる $(L, R)$ を一様…

Splay 木の計算量解析

Splay 木概論 Splay 木の基本操作 $\newcommand {\rank}{\mathtt{rank}}$Splay 木 $T$ は $0 ≤ Φ(T) ≤ n \log(n)$(ただし $n$ は節点数)なるポテンシャル $Φ(T)$ のもと、次の操作ができる二分木です。 クエリ 引数 事前条件 効果 ポテンシャル増分 最悪時…

【関数方程式】算術平均と可換な関数

問題 連続関数 $f: \mathbb{R} \to \mathbb{R}$ であって、次の条件を満たすものを特徴づけてください。 $$ f \left ( \frac { x + y } { 2 } \right ) = \frac { f(x) + f(y) } { 2 } \ (x, y \in \mathbb{R}) $$ 答え 答えは一次以下の多項式関数、つまり …

置換同士の転倒距離のご紹介と、転倒距離に関する三角形の周長の上界の評価

$\newcommand \dist { \mathrm{dist} }$$n$ を自然数として $[n] = \{ 0, \dots, n - 1 \}$ の置換全体の集合を $\mathcal{S} _ n$ と表します。置換 $σ ∈ \mathcal{S} _ n$ の転倒数を $ι(σ)$ で表します。 置換 $σ, τ \in \mathcal{S} _ n$ の間の距離 $\d…

区間ヒープのバグらせない実装だと思っているものを公開します

区間ヒープってバグりますよね。わかります。 概略は簡単なのですけれども長さを $4$ で割った余りで謎の場合分けが入ってつらい印象です。 この記事では私が簡単かつ高速であると思っている実装をご紹介していきます。 データ表現 この辺りは基本的にご存じ…

平面内にの pairwise disjoint な長方形3個の配置の分類(品目定理)とそのグラフ理論的証明

変な用語を普及させてしまってまた怒られそうなので、後世の方が「品目定理ってなんですか!?」になったときのために一応残しておきましょう。 主張 平面内にの pairwise disjoint な長方形3個の配置 が与えられているとします。このときこれは垂直な直線ま…

忘れがちな公式

負の二項定理みたいなやつ $$ \frac 1 { (1 - x ) ^ { 1 + n } } = \sum _ { i \ge 0 } \binom { n + i } i x ^ i $$ 重複組み合わせ $$ \left \lbrace x \in \mathbb{N}^k \ \middle \vert \ x _ 1 + \dots + x _ k = n \right \rbrace = \binom { n + k - …

[工事中]いわゆる期待値 DP の考え方

$$ \newcommand \id { \mathrm { id }} \newcommand \src { \mathrm { src }} \newcommand \tar { \mathrm { tar }} \newcommand \pid { p _ { \id } } $$ 毎回同じ形で出るのになんか混乱するので纏めました。 ※ 「補遺 ~ 執筆後に思ったのですが」にある…

Manacher's algorithm でダミー文字を使わなくて済む方法

概要 Mancher のアルゴリズムは与えられた長さ $n$ の文字列 $s$ に対して、各文字の回文半径(その文字を中心とした回文の長さ引く $1$ 割る $2$)を計算するアルゴリズムです。これの出力要件とアルゴリズムを少し変えることで、実装の複雑さはほとんど変…