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

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個の配置 が与えられているとします。このときこれは垂直な直線ま…

負の二項定理みたいなやつ $$ \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 - …

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

参考文献：文字列の頭良い感じの線形アルゴリズムたち２ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ 普通の Manacher のアルゴリズム 入力 $s$ の長さが $n$ のとき、普通の Mancher のアルゴリズムは、$A_i$ が $s$ の場所 $s_i$ を中心とし…

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

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