えびちゃんの日記

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

Toyota Programming Contest 2023 Spring Final など参加記

参加してきました。 えびちゃんです pic.twitter.com/thrbw3oZYB— えびちゃん (@rsk0315_h4x) 2023年3月18日 「参加記に載せる用の画像を載せておくと、参加記に載せるのが楽になる」というのを思い出したので撮っていました。 予選 B で G を解いていい感じ…

コンパイラの警告を無視してバグらせる人かわいそう

無視されるコンパイラちゃんもかわいそうです。 とはいえ、「ここのコードこうなってるよ」という警告の仕方だけされても(特に初心者が)困ってしまうのは当然かなという気もします。 コンパイラが気にしてくれている理由や、実際にバグっているコードでそ…

ある種の無限級数を DP で求める

これなんで〜〜〜 pic.twitter.com/vy1XiRcw9o— えびちゃん (@rsk0315_h4x) 2023年2月8日 天下り的でカスなんですが、ランベルトのW関数がΣ(-n)^(n-1)/n!x^nなことを思い出すと、n^n(0^0=0として)の指数型母関数はf(x)=xW'(-x)=-W(-x)/(1+W(-x))になり、f(1/…

順列の LIS を O(n log(log(n))) 時間で求めてみようかな

え、[0, n) の整数からなる順列の LIS って O(n log(log(n))) 時間でできるの— えびちゃん (@rsk0315_h4x) 2022年12月27日 これの解説みたいなのを書きます。 前提知識 方針 手法 実装例 その他 おわり rsk0315.hatenablog.com この記事の参考文献にある “Bo…

期待 O(n) 時間の前処理で、クエリごと最悪 O(1) 時間で座標圧縮しようかな

ハッシュを使います。 導入 紹介 それ以外の紹介 ハッシュについての話 +perfect +minimal +monotone 文献 実測 おきもち おわり 導入 ある程度の仮定は欲しいです。 というのも、これが一般の型でできたら期待 $O(n)$ 時間でソートができることになるためで…

はてなブログで KaTeX を使う

まとめておいた方がいいかなと思ったので。 導入方法 はてな記法の tex 記法との比較 キーワードリンクに関して 衝突する例と ad hoc な回避策 解決方法 1 解決方法 2 マクロなど コピペ用 参考 おきもち おわり 導入方法 $\KaTeX$ の JavaScript を読み込む…

今年のえびちゃん 2022

今年もやってみます rsk0315.hatenablog.com 今年お勉強したもの その他書いたもの 開発環境関連とか AZIK プログラミング側 今年あったこと 買ったものとか 実体がある 実体がない その他 おいしい おわり 今年お勉強したもの 実装したものや記事を書いたも…

入力長に対して線形時間 + 編集距離に対して二乗時間で LCS を求めるよ

前提知識 文字列関連の定義 アルゴリズム関連 簡単な事実 お詫び 準備 Edit graph $D$-path $(D, k)$-furthest path 添字の記法 Longest common prefix 考察 アルゴリズム 方針 高速化 復元 実測 おきもち おためし 下界との関連 参考文献 おわり 前提知識 …

サムネイル画像用

記事中に画像を入れるとサムネイル画像としていつものタイトルのやつを使えなくなるの、なんとかなりませんでしょうか サムネイル画像を作るためのダミー記事を使って用意しています

Montgomery 乗算について

Montgomery(モンゴメリ) 乗算の話をします。 Barrett reduction について前に 紹介したことがある のですが、それと同じように除算命令を避けて剰余演算をする手法の一つです。 前提 以下では、法を $N$ とします。また、以下の条件を満たすような $R$ を用…

log をつけずに解くのが好きな人向けの記事

\(\Theta(n \polylog(n))\) 時間で解くのは簡単だけど、実際には \(\Theta(n)\) 時間で解けるよーという問題はちょくちょくあります。 競プロ界隈では log を削ることに意欲的な人は一部だけな気がします*1が、話として知っておいても損はあまりない気がする…

大まかな方針はわかっているはずなのに細かい実装でバグらせるのかわいそう

えびちゃんかわいそう。 \(O(1)\) 階差分を取ると imos 法で書ける形になるような区間加算クエリ*1を一生バグらせました。 特に、DP をしながら on-the-fly で imos 法の遅延を解消していくやつを毎回バグらせている気がします。 こういうのはコンテストで出…

ワードサイズの転倒数を O(log(w)²) 時間で求めるよ

これいる? 問題設定 \(w\)-bit 整数を 0/1 配列として見たときの転倒数を考えます。 すなわち、\(x = b_0 \cdot 2^0 + b_1 \cdot 2^1 + \dots + b_{w-1} \cdot 2^{w-1} = b_{w-1}\ldots b_1 {b_0}_{(2)}\) (\(b_i \in \{0, 1\}\)) として、\(i\lt j\) かつ …

ビット並列手法の基礎と基礎以外など

思い立ったので書いてみます。 導入 前提 基礎演算 単項マイナス 最も右の諸々に関する演算 その他簡単な演算 典型的な発想の紹介 にこにこで合わせるやつ(分割統治) count ones reverse suffix parity 二分探索 most-significant set bit (msb) least-sig…

リアクティブ問題のデバッグに関して

ABC 269 E や ABC 244 C など、リアクティブ・インタラクティブ形式の問題は ABC でもたまに出題されます。典型 90 :: 53 にもありますね。 普通の形式の問題であれば、oj などを使ってデバッグしている人でも、リアクティブ形式だと手作業で実行する人は多…

えびちゃんの AtCoder ユーザ解説まとめ

振り返りたくなったのでついでに書きます。 新しくなる順。 J - 長い長い文字列/Long Long String ほぼ愚直にシミュレートするのが、解析すると妥当な計算量とわかって面白かったので書いた \(x \bmod y\) が \(x\) の半分になるので高々 \(\log(x)\) 回で \…

「任意の」を「全ての」と読み替えさせる風潮に対するお気持ち表明

「任意の」の気持ちがわかっていないまま、そういう文を読まされるのもつらいと思うので書きます。 言葉の意味に関して 空の場合に関して 別の例 英語に関して 関連? おまけ おわり 言葉の意味に関して 「任意の \(x\in S\) に対して \(P(x)\) が成り立つ」…

初心者が陥りがちな嘘貪欲やコーナーケースやその他諸々に関して

「初心者が貪欲法を覚えて、全てそれで解こうとしている」のかな?と思い込んでいたのですが、そうではないような気がしてきました。 諸々のコーナーケース(off-by-one 系の境界条件とか)についても同じような背景がある気がするので書きます。 やや厳しい…

lower_bound で混乱している人かわいそう

言語さんサイドにも問題があるというのはそうかも。 とはいえ、理解が足りないまま「わかりにくい」と言っている人はかわいそうなので、解説をします。 名前について なんで「x 以上の最小値を得る関数」が lower_bound と呼ばれているのかわからん*1 まず、…

「区間更新と言えば遅延セグ木」で思考停止している人向けの記事

指示された「区間更新 + 何かのクエリ」を遅延セグ木で解ける状況で、思考停止で遅延セグ木を貼って AC できる人に対するお気持ち表明ではないです。 「区間更新」の部分だけを見て「どうやら遅延セグ木というので解けるらしいが自分はよく知らない。だから …

データ構造の操作に関する動詞

人には人の直感。 データ構造同士をくっつけるとき、なんでも「マージ」と呼んでしまう人がいる気がします。 それはそれでいい気もしますが、どういう性質を持つデータ構造か・どういうくっつけ方かによって適切に感じる動詞は異なる気がします。 マージ以外…

ならし計算量のよくある誤解について

ならし計算量 (amortized complexity) というのがありますが、競プロ初心者層には誤解されがちな概念なので、誤解を解くためのことを書きたくなりました。 以下で「よくある誤解」と称して架空の人物がしゃべりますが、複数回見てきた事例であり、特定個人に…

素数の数え上げのスライドについて

最近スライドを公開しました: 素数の数え上げを O(n^{2/3}/log(n)^{1/3}) time でしたり、乗法的関数の和を O(n^{2/3}) time で求める話の勉強会スライドですhttps://t.co/IzybtPOkJu pic.twitter.com/gtFOPZM4kZ— えびちゃん (@rsk0315_h4x) 2022年6月29日…

不必要に浮動小数点数を使うの怖い

競プロにおいて、「何かしらの整数を大小比較して、左辺が大きければどうのこうの」みたいなことをしたい局面はそれなりにあります。 特に、境界付近でも正確に評価できる必要がある状況も多いです。 そうした状況で浮動小数点数を使うのはできるだけ避けた…

α(m, n) のお勉強 + 定数時間 decremental neighbor query

\(\alpha(n)\) や \(\alpha(m, n)\) というのがありますね。union-find の計算量解析で出てくる?らしい、ほぼ定数?みたいな関数?だと思われていがちなやつです。 一度お勉強したつもりですが、実はなにもわかっていなかったのでまたやりました(別にリン…

遅延セグ木を思いつく流れを追う用の記事

敬遠されがちみたいな印象がある[要出典]*1ので、書いてみます。 問題 観察 1 欲しい性質まとめ 観察 2 本題 成り立ってほしい性質 その他 参考文献 おわりねこ 問題 以下のような問題設定を考えます。 集合 \(S\), \(T\) と、それに関する演算 \(\circ: S\t…

クエリ先読みなし任意順序 CHT

あまり知られていないような気がするので書きます。欲しくなる状況自体が珍しいという話かも。 適当に調べると、傾きの単調性を使って deque で処理するやつか、先読みして Li-Chao tree で処理するやつがたくさん見つかる気がします。 先読みなし・単調性の…

Re: 浮動小数点数の二分探索

rsk0315.hatenablog.com こういう記事を過去に書いたんですが、どうにもなんだかな〜という気がします。 導入 というのも、64 bit の浮動小数点数を使うとして 90 回もチェックするのはうれしくなさそうです。 (IEEE 754 準拠というのを仮定するとして)dou…

オフラインの線形時間 LCA

クエリ先読みする場合の LCA を線形時間で解きます。何日か前に TL で話していたら思いついたので。 まずそのときのツイートをいくつか貼ります。 LCA ってクエリ先読みして DFS とかの方針で線形で解ける? わかりません— えびちゃん (@rsk0315_h4x) 2022年…

要素の追加・削除と mex を対数時間で処理するよ (2) + 区間 mex クエリ

rsk0315.hatenablog.com エゴサしたらこの記事がわりと読まれているっぽかったものの、やや実装が重い気がしたので*1別の解法を書きます。 tl; dr セグ木。 定義 有限集合 \(S\subseteq \N\) における mex というのは、\(S\) に含まれない最小の自然数 \(\mi…