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

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

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

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

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

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