ブログ名

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

負の添字を持つ対称な 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$)を計算するアルゴリズムです。これの出力要件とアルゴリズムを少し変えることで、実装の複雑さはほとんど変…

マージテクで、いわゆる auxiliary tree を構築する方法

参考問題: ABC340-G Leaf Color (鹿島建設プログラミングコンテスト2024) 参考文献: 指定された頂点たちの最小共通祖先関係を保って木を圧縮してできる補助的な木 | Kyopro Encyclopedia of Algorithms LCAをベースに構築するAuxiliary Treeのメモ - 日…

初めてのスタジオレコーディング体験記

まずはこれを再生しましょう! www.youtube.com 再生しましたね。ありがとうございます。では本日はここまでということで、ありがとうございました 以下あとがきになります。 あとがき 前提(私がライブ苦手なお話) 私はいわゆるちゃんとした歌枠をしたこと…

2023年振り返り&2024年の目標

例年通り、旧念の目標の達成状況を見て反省をし、また新年の過ごし方、目標を立てていきます。 とりあえず過去記事おいておきます。 2023: 2023年の目標と、旧年の振り返り - ブログ名 2021: 2021 年の目標について - ブログ名 2020: 2020 年の抱負 - ブログ…

2次元累積和の4つの形と8つの構築方法、4種類の長方形和クエリ、そして閃光のごとく現れた1人の天才こと私です。オススメ実装もあります!

どもども~~ こんにちは。ながたでございます。 先日の ABC 331 D - Tile Pattern を見て、執筆したくなりました。 この記事は、2次元累積和の亜種や実装方針などを網羅的に検討して回った結果、結局「コレ」でよいですよねという感じの記事になっておりま…

全ての AVL 木が赤黒木になるような彩色をもつこと

AVL 木を赤黒木になるように彩色する方法をご紹介します。

Hopcroft–Karp の Rust による短くて易しい実装

Hopcroft–Karp のアルゴリズムは、二部グラフ $G = (V (= L \cup R), E)$ の最大マッチングを $O (E \sqrt V)$ で計算します。(ただし、$E = \Omega(V)$ を仮定します。)詳しくは Wikipedia へどうぞです…! この記事の方法は行数でいうと全部で 40 行以下…

長方形に割られた漫画のコマの読む順序の定義

マンガ初心者の方に向けて、コマをどのような順序で読んでいけばよいのかをレクチャーしていく記事です。 こちらの問題を解いていきましょう! 図みたいな漫画のコマ割りを見て「読む順序として正しいものを答えなさい」って言われたら大体みんな正解すると…

2023年の目標と、旧年の振り返り

旧年の振り返り 目標とその達成 去年は、(人気がどうというよりも)お歌が「上手になりたい!」を圧倒的第一に掲げ、活動してきました。それに最も資する定量目標は何かと考えたところ、投稿頻度でしょうかになりました。 歌ってみた動画を1年間で 保守的目…

世田谷区脱出ゲームに1年以上掛かったお話(お引越し体験記)

こんにちは、ながたです。 私は長らく世田谷区に住んでいました。旧居には不満も様々ですが、3.9 万円のお家賃を考えるとあまりに良いお部屋でした。しかしそんなお子様な私もいつしか、高級マンションに住みたいお年頃となってくるわけです。というわけでこ…

年収 1000 万円未満のみなさまに贈る、よりよい人生を送るための道標、ないし戦略についてです。

個人的におすすめな戦略 年収 1000 万円がいただけるお仕事につくとよいです。

最高に魂を揺さぶるおすすめ歌動画 10 選

隠していたのですが私は YouTube が大好きでして、多いときには一日に 40 時間くらい動画を観ていたりします。 みなさま、お歌の動画などご覧になりますでしょうか。私は多いときには一日に 4 億時間くらい観させていただいております。そんな私の「最高に魂…

ベル数でお馴染みの指数型母関数の exp がどのような数え上げに対応しているのか、どのようなタイプの問題が解けるのかを解説していきます。

$$ \newcommand {\braced} [1] {\left \lbrace #1 \right \rbrace} \newcommand {\bracked} [1] {\left \lbrack #1 \right \rbrack} $$ 指数型母関数といえば、添字のシフトが微分になったり、二項係数で重み付けられたコンボリューションが積になったりなど…

Convex hull trick などの実装に応用のある、Rust の BTreeSet / BTreeMap 1本だけで、2通り以上の二分探索を実現する方法

イントロ Convex hull trick では直線の列を、傾きに関して単調増加になるように管理するのですが、二分探索の検索クエリは傾きだけでは足りません。次のように2種類の二分探索が欲しくなります。 傾きに関して二分探索 最小を達成する区間に関して二分探索…

[暫定]Rust の `Box` を使った易しい平衡二分木の実装

イントロ 平衡二分木は、いろんな意味で難しいです。アルゴリズム自体は(難しくはあるもののお)そこまで長大とまではならないのですが、細かい機能を整備していくとどんどんコードが長くなっていく印象です。 そこでこの記事では、「挿入・削除・併合・分…

歌ってみたの機運について

みなさま ABC 229 お疲れ様です。決意表明の流行する今日このごろです。 さて、実は私の趣味は競技プログラミングだけではありません。たとえば最近はお歌にお熱です。長らく一人で楽しんでいたのですが最近は、やはりみなさまにも聴いていただきたい!人気…