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

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

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

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

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

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

これいる？ 問題設定 \(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 などを使ってデバッグしている人でも、リアクティブ形式だと手作業で実行する人は多…

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

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

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

言語さんサイドにも問題があるというのはそうかも。 とはいえ、理解が足りないまま「わかりにくい」と言っている人はかわいそうなので、解説をします。 名前について なんで「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日…

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

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

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

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

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

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

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

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

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

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