えびちゃんの日記

えびちゃん(競プロ)の日記です。

√w-bit の入力に対する定数時間 rank/select

これいる? 背景 本題 ビット並列 サブルーチン メイン 実装 サイズに関して 実測 雑記 あとがき おわり 背景 定数時間 rank/select をできる簡潔データ構造を作るときの基本戦略として、表引き (table lookup) というのがあります。 小さいサイズ(たとえば…

浮動小数点型の算術とお近づきになりたい人向けの記事

お近づきになりたい人向けシリーズです。 いろいろなトピックを詰め込みましたが、「これら全部を知らないといけない」のようなつもりではなく、いろいろなことを知るきっかけになったらいいなという気持ちなので、あまり身構えずにちょっとずつ読んでもらえ…

今年のえびちゃん 2023

今年もやってみます rsk0315.hatenablog.com 今年書いたもの カスの記事 はてなブログ関連 気まぐれアルゴリズム かわいそうシリーズ 振り返り DP 関連 数式がちゃがちゃ ブラックボックスのお勉強 浮動小数点数 今年買ったもの 来年に向けて 競プロ以外 う…

ポインタ木なしで償却 O(log(n)²) 時間の predecessor query

お風呂で思いついたシリーズです。 できる操作は次の通りです。 $\texttt{new}()$ $∅$ で初期化する $S.\texttt{insert}(x)$ $S ← S ∪ \{x\}$ で更新する $S.\texttt{remove}(x)$ $S ← S \smallsetminus \{x\}$ で更新する $S.\texttt{less}(a)$ $\max {\{x∈…

xx.yy を 100 倍したら xxyy にできる?

小数点以下が高々 2 桁まである値が十進表記で与えられたとき、「それを浮動小数点数型に parse してから 100 倍する」ことで、元の値の小数点を 2 つぶん動かしたものにできますか?という話です。 >>> print(f'{float("10.00")*100:.100g}') 1000 >>> prin…

u64 の平方根を f64 で計算するやつに関して

符号なしの 64-bit 整数型の値に関して平方根を計算したい局面はそこそこあります。 しかし、多くの言語ではそのための関数が用意されておらず、浮動小数点数型用のメソッドを使う人が多くいます。 今回は、そうした方針が妥当か?(誤差が出うることを踏ま…

(1.0 / 49.0) * 49.0 < 1.0 について

仮数部の精度が 53 bits の浮動小数点数型で計算すると下記のようになります。 >>> 1 / 49 * 49 0.9999999999999999 >>> f'{1/49*49:.100g}' '0.99999999999999988897769753748434595763683319091796875' 今回はこれについて掘り下げます。 記法・前提知識 …

floor(n / 10.0) と floor(n * 0.1) は等価?

これを double で計算したときに常に等しくなりますか?というクイズです。 n は double で表せる整数であることにします。 答え >>> 6755399441055749 / 10 675539944105574.9 >>> 6755399441055749 * 0.1 675539944105575.0 より、前者の floor と後者の f…

Sqrt Inequality の誤差評価

atcoder.jp 導入 これの long double 解法についての話です。下記のような解法です。 #include <cmath> #include <cstdio> constexpr long double eps = /* ??? */; bool ok(long double a, long double b, long double c) { return std::sqrt(a) + std::sqrt(b) + eps < st</cstdio></cmath>…

s-factorization を求めたり run enumerate を解いたり

judge.yosupo.jp こちらです。これを解くアルゴリズムの一つとして下記があります。 Kolpakov, Roman, and Gregory Kucherov. "Finding maximal repetitions in a word in linear time." In 40th Annual Symposium on Foundations of Computer Science (Cat.…

unsigned の exact division などをうまくやる

背景としては、こちらの記事です。 rsk0315.hatenablog.com 1431655766, 1717986920, 1431655782, 1431655768, 1840700272, 1431655966, -1431655056 などさまざまなマジックナンバーが登場します。 「$x$ が $3$ の倍数であることがわかっているとき、$1431…

Clang の k 乗和の最適化を眺める

Clang が $\sum_{i=0}^n i$ を $n(n+1)/2$ にしてくれることは有名です*1。 また、$\sum_{i=0}^n i^2$ も $n(n+1)(2n+1)/6$ にしてくれます。 その過程では、 unsigned v1 = n * (n - 1) * (n - 2) / 2 * 1431655766u; unsigned v2 = n * (n - 1) / 2; retur…

タイトル欄やカテゴリ欄で ⌃M を押すと、何らかの力がはたらいて記事が投稿されてしまう、あぶない(一敗)。 右下が「下書きを更新する」や(投稿後編集中の)「更新する」であってもそうなる。

ソースコードを見て計算量を下から抑えるのは怪しいという話

競プロ er はよく計算量の見積もりをします。「これこれの計算量は $O(\dots)$ なので十分高速である」といった具合で上から抑えることが多いです。 また、「これこれの計算量は $\Omega(\dots)$ なので TLE しそう」といった具合で下から抑えることもしばし…

JS や CSS のテスト

↓ ここが hello になっていれば勝ち zzz ↓ 擬似コードが render されていれば勝ち function $\textsc{Identity}(x)\colon$ return $x$

各種 DP を愚直な形で考えてみる

先日、下記の記事でナップサック問題の DP を愚直に眺めました。 rsk0315.hatenablog.com 今回は、ナップサック問題に限らず様々な DP を愚直に眺める回です。 「○○(何らかの集合)の最大値」のように計算せず、○○の部分について考えていきます。 もちろん …

配る DP・もらう DP の特徴づけに関して

典型的な DP の実装の属性の一つとして、配る DP・もらう DP と呼ばれているものがあります。 もらう DP を集める DP と呼ぶ派閥もあった気がしますが、ここでは名称についての議論はしません。 導入 主張 例 ナップサック問題 Eratosthenes の篩 回数の期待…

ABC-E をうめました

より正確には、ABC の A–E をうめました。 自己肯定感が低く、「何々をうめました」というときに「まだうめてなかったのか」という声が自分の中から聞こえてくるタイプの人もそれなりにいるのではないでしょうか。えびちゃんはそういう人です。 他の人がうめ…

平方根と整数除算まわりの性質メモ

ABC 204 E に関連します。 定義 表記 意味 例 $\floor{x}$ $x$ 以下の最大の整数 $\floor{3.1} = 3$, $\floor{2.7} = 2$, $\floor{-2.2} = -3$, $\floor{2} = 2$ $\ceil{x}$ $x$ 以上の最小の整数 $\ceil{3.1} = 4$, $\ceil{2.7} = 3$, $\ceil{-2.2} = -2$, …

DP のイメージ・メンタルモデルに関して

動的計画法 (dynamic programming, DP) はイメージ・メンタルモデルを掴むまでのハードルが中々高いような気がします。 一例を示しますが、必ずしも全部の問題を一貫して説明できるとは限らないので、いくつかのイメージを持っているといいかもしれません(…

形式的冪級数に関する一階常微分方程式を解く

最近話題の形式的冪級数 (FPS) です。最近と言いつつ 4 年くらい前から流行り始めていた気がします。当時は「母関数」と呼んでいる人が多かった気がします。 今回は、FPS で考察をしていて「$\frac{\dd}{\dd x}y = f(y)$ なる FPS $y(x)$ に対して $y(x)\bmo…

中央値関連のライブラリに関して

何らかの順序を持った型 T: Ord があって、それに関する何らかの(多重)集合の中央値を求めるライブラリを作りたいとします。 たとえば単に配列 a: [T] の中から中央値を探すだけだったり、a: [T], b: [T] から a[i] + b[j] として考えられるものの中央値 (…

カテゴリー機能のテスト

カテゴリー機能を使っていなかったので、使うと便利なのでは?と思いました。圏論とは関係がないかもしれません。

mod についてふんわりとしか理解していない競プロ er のみなさん

ちゃんと理解していない人が大半だと思っています。あるいは、法が素数の場合に過学習して、法が合成数になった途端に不安になる人も多いでしょう*1。 競プロ er の三大得意分野として「計算量削減」「mod なんとかの数え上げ」「なんか」があるはずなのに、…

素因数分解を <O(n), O(log(n)/log(log(n)))> で行う

もしかすると全人類知っていたかもしれません。 $\gdef\lpf{\operatorname{lpf}}$ $\gdef\ord{\operatorname{ord}}$ 導入 前計算 高速化 実装 おまけ Euler の totient 関数 約数列挙 おわり 導入 以下、整数 $i$ の最小素因数 (least prime factor; LPF) を…

rational reconstruction の解説をしようかな

クイズです。$p/q \equiv 714236805 \pmod{998244353}$ を満たす互いに素な整数のペア $(p, q)$ はなんでしょうか。 答えは $(113, 355)$ です*1。今日の話は、これを一般的に求める方法です。 裏話 $1/3 \equiv 332748118$ みたいなのだとパターンマッチで…

n²+2n+1 型の素数の列挙

$n^2+2n+1 = (n+1)^2$ です。$n = -1$, $n = 0$ のとき $0$, $1$ であり素数ではありません。$n \ge 1$ のとき素数二つ以上の積となるので素数ではありません。 また、$n \lt -1$ についても同様に素数でないことがわかります。 よって、$n^2+2n+1$ 型の素数…

バグらせやすい書き方をすれば当然バグは出やすい

導入 rsk0315.hatenablog.com こういう話はある*1んですが、最初からバグらせやすい書き方をしておいて「バグが出たー」と言われてもそれはそうとなってしまうので、そういうのを控えるくらいのことはするべきだと思います。 書き方が悪いせいで「十分に複雑…

【期間限定公開】絶対にバグらせないコツ教えます【競プロ er 必見】

期間が過ぎたので公開を終了しました。

有理数上の二分探索(ざっくり導入編)

詳しく解説編があるかはわかりません。 下記のような状況に対する別の策です。 rsk0315.hatenablog.com rsk0315.hatenablog.com 導入 今回は、浮動小数点数をそもそも使わない方針で考えます。 ある(自分で決める)上限 $b$ に対して、分母が $b$ 以下の(…