えびちゃんの日記

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

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…

区間 LIS クエリを書きました

去年末にやると言っていたんですが、やっと終わりました。 クエリで与えられた区間の最長増加部分列の長さを答えるやつで、計算量は \(\langle O(n\log(n)^2), O(\log(n))\rangle\) です。 実装前にイメージがつきにくかったのと、あったら楽しいかなと思っ…

直近 k 回以内に挿入された要素の最大値を出せる優先度つきキュー他いろいろ

次の操作ができる優先度つきキューのおはなしです。 push(x):x を挿入する pop_newest(k):挿入順が新しい方から k 以内の要素の最大値を取得・削除 pop_oldest(k):挿入順が古い方から k 以内の要素の最大値を取得・削除 取得だけする peek_newest(k), pee…

区間 k-最小値いろいろ

ここで区間 \(k\)-最小値と呼んでいるのは以下のような問題です。 最初に配列 \(a = (a_0, a_1, \dots, a_{n-1})\) が与えられるよ。 次にクエリ処理を \(q\) 回してね。 クエリは \( ([l, r), k)\) の形式で与えられるので、\(a_l, a_{l+1}, \dots, a_{r-1}…

今年のえびちゃん 2021

自分語り記事です。 えびちゃんの一年を振り返る記事をうっかり書きそうになったけど、冷静になったので却下した— えびちゃん (@rsk0315_h4x) 2021年12月16日 うっかりし直しました。 今年お勉強したもの 数学関連のものをいくつか学んだり、昔わかった気に…

二分探索の上限を適切に決められずに失敗する人かわいそう

競プロ er の間では、(主に実生活で)最適値を探そうと二分探索をして、上限を大きく取りすぎたために破滅するという定番ネタがあります*1。 あるいは、実際のコンテストでも「上限が小さすぎた」「上限を大きくしすぎたため判定関数内でオーバーフローした…

最近夢で見た問題

夢に出てくる競プロの問題、自明か既出か #P-complete がち— えびちゃん (@rsk0315_h4x) 2021年11月23日 今回はわりと面白いやつ出たか?と思って考えてたんだけど、寝起きで頭がついてなかっただけで自明枠だったことが判明しつつある— えびちゃん (@rsk031…

Python でも set::lower_bound っぽいことがしたい

したくない人は読まなくていいです。 TL; DR vEB やりたいこと Python の set は「x 以上の最小値は?」「x より大きい最小値は?」といったクエリに答えられないので困ります。それをしたいです。x は整数としちゃいます。 特に競プロの文脈の話なので、外…

無限回思いついた嘘考察まとめ

思いついたら書きます。 これはなに なにかを思いついたときに、指摘される前に「あー嘘じゃんこれ」というのに気づく用のノートです。あと他人の嘘考察を見るのはたのしい。 嘘考察 嘘考察たちです。 \(n^{1/2}-n^{1/3}=O(n^{1/3})\) \(n^{1/2}-n^{1/3} = n…

できるだけ嘘を書かずに計算量やオーダーの説明をしようとした記事

計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。 数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれ…