ブログ名

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

2024-03-01から1ヶ月間の記事一覧

平面内にの 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のメモ - 日…