AlpacaHack Round 7 (Web) に参加しました。えびちゃん的には初めての CTF のコンテストです。 自分語り 今回のコンテストの話 Treasure Hunt Alpaca Poll minimal-waf・disconnection コンテスト後 おしゃべり おわり 自分語り シェルスクリプトでごにょご…

線形篩と呼ばれているアルゴリズム・データ構造があります。 「線形時間で前計算できる何々」を「線形何々」と呼ぶのは不適切ですか、もしかして？*1 ざっくり紹介 構築に関して 発展編 実装 練習問題 おわり $\gdef\lpf{\operatorname{lpf}}$ ざっくり紹介 …

「競プロライブラリにおける抽象化と言えばセグ木」みたいな風潮ができてから久しいですが、二分探索に関してそうした抽象化を意識している人はあまり多くない気がしています。 おきもち 整理・設計 実装 その他 実装に関して 中間値に関して お気持ちに関し…

C なんだけど、答えをベタ書きした Python のコードを gzip で圧縮して Base64 でエンコードしたやつを、復元して実行することで AC できる pic.twitter.com/xsPaFGoi0u— えびちゃん (@rsk0315_h4x) June 8, 2024 「埋め込みするにあたってもちゃんとしたコ…

rsk0315.hatenablog.com B-tree が書けたらまた自慢しに来ます。 書けました。一旦は append*1/split と添字でのアクセスと bisect*2 ができる列としての B-tree です。セグ木のような区間 fold 演算ができた方がいいのかもという気持ちもあります。 一応実…

導入 配列 $a = (a_0, a_1, \dots, a_{n-1})$ に対して適当な区間 $[l\lldot r)$ が与えられて、そこでの平均値 $f_a(l, r) = \tfrac1{r-l}\sum_{i=l}^{r-1} a_i$ を考えます。 たとえば $[l\lldot r)$ がたくさん与えられて平均値を求めるだけなら、累積和…

ポインタ系データ構造（未定義お気持ち用語）を書きましょう。 まえがき やりたいね 基礎パート ツールの紹介 練習パート 実践パート データ構造に関して補足 勉強パート あとがき おわり まえがき ここでポインタ系データ構造と呼んでいるのは、配列や二分…

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

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

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

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

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

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

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

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

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>…

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.…

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

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 しそう」といった具合で下から抑えることもしばし…

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

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

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

より正確には、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$, …

動的計画法 (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] として考えられるものの中央値 (…

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