概要 LIbrary Checker のジャッジをお借りして、次の 3 種類の強連結成分分解アルゴリズムそれぞれの、いくつかのバージョンの速度を比較します。 Kosaraju's algorithm Tarjan's algorithm Gabow's algorithm その結果、Vec<Vec<usize>> を構築して行う Kosaraju's alg</vec<usize>…

問題 ARC 164 E - Segment-Tree Optimization 解法 mark がひとつもないとき（つまりすべてのクエリが全体クエリのとき）は特別で、答えは $(0, q)$ となりますが、そうでないときを考えましょう。 区間 $[l, r[$ に対するクエリが来るたびに、$[l - 1, l + …

カービィの空下コンボを確定させるのにとても苦労したので、その過程でわかったことを書きます。 結論 ポイントは「空下の着地隙を発生させないこと」で、そのためには 大ジャンプの離陸から 1 ～ 6 F 後（ジャンプボタンの 4 〜 9 F 後）に空下を入力する …

ここ（スマブラSP フレームデータ by検証窓 - Google スプレッドシート ）に大体書いてあるのですが、コンボ検証等のため、もっと細かいことが知りたくなったためです。 小ジャンプの出し方 ジャンプボタンを押す長さが 3F 以下なら小ジャンプになります。ま…

カービィちゃんと言えば、下強転倒確認からのダッシュつかみ or 横スマッシュですね。 どれくらい急いで転倒確認をしないといけないのかが気になったので、詳しく研究してみました。 状況 トレーニングモードで、カービィ 0%、サムス 30%、OP 相殺なしです。…

概要 ダッシュから反転空後を打とうとすると、なぜか逆向きの空後に化けることがあるためその条件を調べました。 空前に化けならまだわかるのですが、逆向きの空後に化けることあります？ 詳細 右向きダッシュ想定でお話します。また C ステ強攻撃想定です。…

$ \newcommand{\F}{\mathrm{\,F}} \newcommand{\Jump}{\mathrm{}} \newcommand{\Stick}{\mathrm{️}} \newcommand{\Atack}{\mathrm{}} $カービィさんにお願いして、トレーニングモードで調べた結果の備忘録です。 シールドキャンセル小ジャンプ空中攻撃 シー…

概要 円環上の DP が問題は、DP を行列積で書くことで行列のトレースになることが多いのですが、立て続けに 2 問お見かけしたため共有です。 両方とも辺被覆の話題でしたが、たまたまでしょうかね。 本文 ABC 247 F - Cards 問題リンク 長さ $n ( \ge 1)$ の…

逐次更新です。該当する問題を見つけたら @ngtkana_kyopro までお知らせいただけると幸いです。 問題リスト 問題 container description ARC 181 D - Prefix Bubble Sort heap pop_while ARC 001 D - レースゲーム stack これも pop_while 系ですがライブラ…

概要 人によって実装が大きく分かれることに定評のある全方位木DPですが、私のスタイルの内容と、その背景をご紹介します。なおプログラミング言語特有の設計のお話は、好みが分かれるところだと思いますためこの記事では敢えて省いております。 内容 次のコ…

概要 $\pm 1$-RMQ 問題に代表されるように、桁数付きのビットパターンをキーにした前計算テーブルが必要なことがよくありますが、そのまま整数の $2$ 進展開と解釈してしまうと長さの違いが同一視されてしまいます。これを回避するキレイな方法をご紹介し、…

概要 HL 分解（重軽分解, HL Decomposition, Heavy-Light Decomposition）には、与えられたパスを heavy path に含まれる path に分解する機能を付けると便利ですが、LCA を含むかどうか（いわゆる節点/辺イテレータ）、非可換なことをしたいときのパスの方…

概要 負の添字を持つ対称な解配列と対称な遷移を持つ 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$ 冪の枠に当てはめる…

問題 問題１ $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 } } $$ 毎回同じ形で出るのになんか混乱するので纏めました。 ※ 「補遺 ～ 執筆後に思ったのですが」にある…

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

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

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