エゴサしたらこの記事がわりと読まれているっぽかったものの、やや実装が重い気がしたので*1別の解法を書きます。

tl; dr

セグ木。

定義

有限集合 \(S\subseteq \N\) における mex というのは、\(S\) に含まれない最小の自然数 \(\min_{i\in \N\setminus S} i \) です。

やりたいこと

追加：\(S\gets S\cup\{i\}\) で更新
削除：\(S\gets S\setminus\{i\}\) で更新
mex：\(\min_{i\in \N\setminus S} i\) を出力

これを (amortized) \(O(\log(|S|))\) 時間とかで。

アイディア

クエリ数が \(n\) のときのことを考えます。このとき、mex が \(n\) を超えることはないことに注意します。 \(S = \{0, 1, \dots, n-1\}\) のとき最大値 \(n\) になります。

そこで、bool の配列 \(a = (a_0, a_1, \dots, a_{n-1})\) を \(a_i = (i\in S)\) が保たれるように管理します。

求めたい mex は、\(\wedge_{i\in[0, x)} a_i\) が true になる最大の \(x\) です（このとき \(a_x\) が false となり、定義から \(x\notin S\) となるので）。よって、\(a\) をセグ木で管理し、この \(x\) を二分探索（ACL で言うところの max_right）で求めればよいです。

\(n\) 以上の値を \(S\) に入れると（クエリ数 \(n\) の下で）mex は \(n\) 未満になることに注意すると、\(n\) 以上の値の更新クエリは無視してよいです。

クエリ数の仮定の除去

クエリ先読みができないときとか、そういう仮定が気に食わないとかで、\(n\) の決め打ちをしたくないことはあります。そこで、いつものテクを使います。

まず、\(n = 1\) と思って処理します。 \(|S| = n\) になったら \(n\gets 2\cdot n\) で更新し、今までの \(|S|\) に基づいて \(a\) を再構築します。無視されていたもののうち \([n, 2n)\) の値が新しく考慮されることになります。

再構築は \(O(n)\) 時間でできるので、（償却）計算量を悪化させません。

あるいは、mex が \(|S|\) になる限り倍々に増やすとかでもよいです。

実装例：Rust, C++

あ

冷静になると、（\(n\) を倍々にできるので）\(\{0, 1, \dots, n\}\setminus S\) を std::set で管理して upper_bound とかすればよくないですか？

セグ木を使う場合でも、\( (i\in S\cap\{0, 1, \dots, n-1\}, i)\) の pair を持って全体の \(\min\) を計算する手もあります。

発展編

ひとつめ

もう少しリッチなクエリを処理したくなるときもあります。 \(S\) を集合ではなく配列とします。

初期化：\(S \gets ()\)
末尾への追加：\(S \gets S \concat\, (x)\)
- \(\concat\) は [1,2,3] ++ [4,5] == [1,2,3,4,5] のイメージ。
- \( (x)\) は 1 要素の配列のこと。
区間 mex：\(\mex\,\{ S_i \mid i\in[l, r) \}\)
- さっきのは \(l=0\) と見なせる。

さっきと同様にとりあえずクエリ数を \(n\) とします。また、一旦は \(r = |S|\) として考えます。 \(a = (a_0, a_1, \dots, a_{n-1})\) を管理し、\(S\) における \(i\) の最後の出現位置を \(a_i\) とします。出現していないときは \(-\infty\) とします*2。

mex クエリの答えは、\(\wedge_{i\in[0, x)} (a_i \ge l)\) となる最大の \(x\) で、\( (\min_{[0, x)} a_i) \ge l\) となる最大の \(x\) を求めればよいです。セグ木でにぶたんです。

\(n\) の仮定の除去はさっきと同様にします。 \(r\) に関してはちょっと大変です。セグ木に対して「\(|S| = r\) だったときの値は？」という質問をする必要があるので、永続セグ木を使えばよいです。

37zigen.com

書きながら思い出したのですが、検索したら見つかりました。

プチ問題
データ構造を設計してください

・construct(A)
長さ N の数列 A からデータ構造を構築
O(N log(N))

・mex(l, r)
mex{A_i | l ≤ i < r} を出力
O(log(N))
— 寝る (@noshi91) 2020年9月17日

例題：

atcoder.jp

解法（ネタバレ）

考察の過程で、以下で定まる配列 \(g\) を求めたくなります。

\[ g_i = \begin{cases} 0, & \text{if }i = 0; \\ \mex_{j\in[1, c_i]} g_{i-j}, & \text{otherwise}. \end{cases} \]

\(g_i = x\) を \(g \gets g \concat\, (x)\) だと見なせて、\(l = i - c_i\) に対応します。

最終的な答えは、以下により定まります（\(\oplus\) は xor）。

\[ \bigoplus_{i\in[0, n)} g_i\cdot (a_i \bmod 2). \]

atcoder.jp

ふたつめ

次に、更新クエリ \(S_i \gets x\) を考えます。これはわかりません。

\(S_i\gets x\) というのは「過去に遡り、\(|S| = i\) のときに \(S\gets S\concat\,(S_i)\) ではなく \(S\gets S\concat\, (x)\) をしたことにする」というのに対応します。

この形式の「過去に遡り、これこれの操作をしたことにする」というクエリを処理するデータ構造は retroactive data structure と呼ばれています*3。

なので、セグ木を retroactive にすればよいのですが、これってできるんですかね。

なんかこのポスターの General Approach のところを見ると、non-retroactive DS を retroactive にするような話があるような気がするのですが、一般的なテクはなかったような気がする (https://erikdemaine.org/papers/Retroactive_TALG/paper.pdf :: Theorem 2) ので、わかりません。何らかの文脈があるのかも。

ねむいので今日はここまでです。あとでまた読みます。

めも

他のアプローチとして、更新できる WM でなんとかなったりしない？んーむずかしいかも。

更新できる方の Mo は使えそう。ちなみにまだ理解してません。

おわり

ねこ。

*1:昔の実装を見たら気のせいでした。

*2:実装上は、最後の出現位置が \(j\) のとき \(a_i = j+1\)、出現しないとき \(a_i = 0\) とかにするといいかもしれません。人によるかも。

*3:より正確には「操作列に対する操作の insert/delete を行える」データ構造な気もします。

2022-01-23

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

去年末にやると言っていたんですが、やっと終わりました。クエリで与えられた区間の最長増加部分列の長さを答えるやつで、計算量は \(\langle O(n\log(n)^2), O(\log(n))\rangle\) です。

実装前にイメージがつきにくかったのと、あったら楽しいかなと思ったので、ブラウザ上で可視化するおもちゃを作りました。

Range LIS Query を触って遊べるやつを公開しましたhttps://t.co/q4X7Oecddn pic.twitter.com/Hrw8Eq1wN5
— えびちゃん (@rsk0315_h4x) 2022年1月23日

rsk0315.github.io

ざっくりとした概要の解説も書きました。実装の詳細などは書いていませんが、実装するために必要となるものの大まかな道筋を書きました。

rsk0315.github.io

ブラウザ上のおもちゃについては、どうせ描画パートが律速になるだろうと思ったので、計算量は \(\langle \Omega(n^2 \log(n)), \Omega(n^2)\rangle\) とかで動いていると思います。

2022-01-13

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

次の操作ができる優先度つきキューのおはなしです。

push(x)：x を挿入する
pop_newest(k)：挿入順が新しい方から k 以内の要素の最大値を取得・削除
pop_oldest(k)：挿入順が古い方から k 以内の要素の最大値を取得・削除
- 取得だけする peek_newest(k), peek_oldest(k) もできる
pop()：最大値を取得・削除
- これは pop_newest(oo) でできる
- oo は \(\infty\) のこと

計算量は amortized \(O(\log(n))\) time です。\(n\) はその時点での要素数です。

記事の構成は以下の流れになります。

優先度つきキューを実装してみる
- よくある二分ヒープとは異なるアプローチ
1. の実装から自然に pop_newest(k) などを捌けるので、その説明をする
同じアイディアで他のデータ構造も作れるので、その紹介をする

優先度つきキューの実装

区間最大値を取得できるデータ構造としてセグ木がありますね。セグ木を使って優先度つきキューを作ります。

大まかなアイディアとしては次の通りです。

長さ \(m\) のセグ木 \(a\) を用意し、添字 \(i \gets 0\) で初期化する。
push(x) の際は、\(a_i \gets x\), \(i\gets i+1\) で更新する。
pop() の際は、全体の最大値 \(a_j\) を取得し、\(a_j\gets-\infty\) で更新する。

\(a_j\) を更新するために \(j\) が必要になりますが、以下のふたつの方法があります。

まず最大値 \(x\) を求めて、\([0, j+1)\) の最大値が \(x\) になるような \(j\) の最小値を二分探索で求める
\( (a_i, i)\) のペアの辞書順 max を返す演算をセグ木に乗せる

ほぼできていますが、次の問題点があります*1。

\(m+1\) 回の挿入をしようとするとこわれる
要素数 \(n\) に対する log ではなく、決め打ちしたサイズ \(m\) に対する log の時間になる

これは適当に解決できます。 \(i=m\) で挿入しようとした場合と、\(n\le m/4\) で削除しようとした場合*2に、再構築します。

セグ木のサイズを \(m\gets 2n\) で更新し、元々の \(-\infty\) 以外の要素を前半に詰め直します。残りは \(-\infty\) でうめます*3。

ならし計算量解析のよくある議論（vector を適切なタイミングで伸縮させるやつ）と同じような議論で、再構築のコストが \(O(1)\) 時間であることが言えるはずです。再構築のおかげで \(m=O(n)\) になるので、amortized \(O(\log(n))\) time となります。

古い方から \(k\) 個以内のやつの処理

区間和のセグ木を用意します。これを \(b\) とします。各 \(i\) に対して、\(a_i \gt -\infty\) のとき \(b_i = 1\)、そうでないとき \(b_i = 0\) とします。

セグ木 \(b\) 上の二分探索で「\([0, i)\) が区間和が \(k\) となる最小の \(i\)」を求め、その \(i\) に対して \(a\) で \([0, i)\) の区間 max を求めます。

新しい方から \(k\) 個以内についても似た感じです。 \(b\) 上の二分探索を 2 回やれば、挿入順が \([k_L, k_R)\) の max とかもできます。

他のデータ構造

上記と同様のアイディアで、次の操作が amortized \(O(\log(n))\) time でできます。

push(x)：末尾に x を追加
remove(i)：i 番目の要素を削除
fold(l..r)：区間 l..r のモノイド積を求める
- あるいは [i]：添字 i の要素の取得

上記で \(-\infty\) を詰めていた箇所の代わりには、単位元 \(e\) を使えばよいです。こっちの方がむしろよく見るかもしれませんね。

あとがき

なんか疲れていて、直近 \(k\) 個以内の最大値を取得できるヒープがあれば面白そうでは？と思った日があったので書きました。応用例があるのかはわかりません。

区間モノイド積を求められる平衡木でも当然できます。

おわり

お粗末さまでした。

*1:ないと思う人もいます。

*2:\(n\le m/2\) を条件にすると、連続で削除するときにたくさん再構築されてこわれますね。

*3:\(n=0\) で挿入しようとした場合などはよしなに処理します。

2022-01-09

区間 k-最小値いろいろ

ここで区間 \(k\)-最小値と呼んでいるのは以下のような問題です。

最初に配列 \(a = (a_0, a_1, \dots, a_{n-1})\) が与えられるよ。次にクエリ処理を \(q\) 回してね。クエリは \( ([l, r), k)\) の形式で与えられるので、\(a_l, a_{l+1}, \dots, a_{r-1}\) を昇順ソートしたときに 0-indexed で先頭から \(k\) 番目に来る値を答えてね。ただし \(0\le k \lt r-l\) が保証されるので、答えがなくなることはないから安心してね。

昨日の ABC-D は、これに \(l = 0\) の追加制約が与えられたものと見ることができます。

座標圧縮などをすれば帰着できるので、以下では \(0\le a_i \lt n\) とします。値の重複も \( (a_i, i)\) などで tie-break することにすればよいので、distinct であるとします（つまり、\(0, 1, \dots, n-1\) の順列が与えられるものとします*1）。

この記事では次のことを紹介します。

wavelet matrix での解法（の概要）
- 前処理 \(O(n\log(n))\) time、クエリ \(O(\log(n))\) time
- クエリ先読みがいらない
  - \(i\) 個目のクエリに答えたら \(i+1\) 個目のクエリが与えられる、などの状況でもいける
並列二分探索での解法
- バッチ処理 \(O( (n+q)\log(n)^2)\) time
- クエリ先読み

並列二分探索の方が計算量では劣っているのですが、並列二分探索の導入や実装の練習（あるいはライブラリの verify）として使えそうだな〜と思ったので、書こうと思い至った次第です。自分の中ではこのアプローチにさっき初めて思い至った（気がする）のと、あまり言及されているのを見た記憶がない（気がする）ので。

二つの解法は各々別物なので、片方だけ読みたいなら他方は飛ばして問題ないはずです。

wavelet matrix での解法

wavelet matrix というデータ構造があります。以下では WM と書きます。

競プロ界隈ではセグ木ほどの知名度はない印象ですが、整数に関するいろいろな区間クエリを処理できて強力です。たとえば、区間 \(k\)-最小値クエリなどを処理できるので、そのまま使って終わりです。

ここでは WM 自体の詳細には立ち入らないですが、このクエリを処理する際に WM がしていることの概要を説明します。

まず、\(n \lt 2^m\) なる最小の \(m\) を求めておきます。答えは \(b = b_{m-1}\dots b_1 b_0\) (\(b_i \in \{0, 1\}\)) の形で表せます。

さて、\(j\gets m-1, \dots, 1, 0\) に対して順に以下の処理をします。

区間 \([l, r)\) にある要素で上位 bit が \(b_{m-1}\dots b_{j+1}\) であるもののうち、\(j\) 番目の bit が \(0\) であるものの個数 \(c\) を数える。
\(c\gt k\) であれば、\(b_j = 0\) で確定する。
- 下位 bit の並び方には影響されず、注目中の bit で決まるので。
- 注目中の bit に \(0\) が十分個あれば \(k\)-最小値の該当 bit が \(0\) とわかるということ。
\(c\le k\) であれば、\(b_j = 1\) で確定する。
- 小さい方から \(c\) 個は注目中の bit が \(0\) なので、注目中の bit が \(1\) のもののうち、\( (k-c)\)-最小値を求めればいいとわかる。
  - \(k\gets k-c\) で更新する。

以上により、\(b\) の全 bit が確定します。

よって、各 \(j\) について、「\(j\) 番目の bit が \(0\) であるものの個数の区間和クエリに答えられるデータ構造を、各 \(b_{m-1}\dots b_{j+1}\) ごとに持ったもの」があれば十分とわかります。これは（愚直には）\(b_{m-1}\dots b_{j+1}\) でソートして、その値ごとにグルーピングして各々累積和を管理するみたいなことをすれば実現できる気がします*2。

詳細は他に任せます。

並列二分探索での解法

まず並列二分探索のフレームワークを説明してから、区間 \(k\)-最小値への適用のしかたを説明します。

並列二分探索自体を知っている人は前半は斜め読みでいいと思います。

並列二分探索のフレームワーク

以下のような問題を考えます。

機械があり、初めは状態 \(0\) です。状態 \(i\) (\(0\le i\lt m\)) のとき、状態 \(i+1\) に遷移させることができます。また、いつでも状態 \(0\) に戻すことができます。

ある \(0\le i^{\star}\le m+1\) が存在して、状態 \(i\lt i^{\star}\) のとき、機械はあなたの質問に対して true と返します。状態 \(i\ge i^{\star}\) のときは false と返します。

常に true を返すケースや、常に false を返すケースも存在することに注意してください。

あなたは、なるべく少ない質問回数で \(i^{\star}\) を特定したいです。

二分探索すればよいです。

let mut machine = Machine::new();
if !machine.query() { return 0; }

let mut yes = 0;
let mut no = m + 1;
while no - yes > 1 {
    let mid = yes + (no - yes) / 2; // 0 <= mid <= m
    machine.reset_state();
    for _ in 0..mid {
        machine.next_state();
    } // 状態 mid になっている
    *(if machine.query() { &mut yes } else { &mut no }) = mid;
}
no // no == i_star

これでは、質問ごとに状態をリセットして mid まで遷移させ直しているのがもったいなく見えます。状態の遷移を \(O(m\log(m))\) 回と、質問を \(O(\log(m))\) 回しています。

そこで、質問の種類を増やしてみます。

機械があり、初めは状態 \(0\) です。状態 \(i\) (\(0\le i\lt m\)) のとき、状態 \(i+1\) に遷移させることができます。また、いつでも状態 \(0\) に戻すことができます。

ある \(0\le i^{\star}_j\le m+1\) が存在して、状態 \(i\lt i^{\star}_j\) のとき、機械はあなたの質問 \(j\) (\(0\le j\lt n)\) に対して true と返します。状態 \(i\ge i^{\star}_j\) のときは false と返します。

常に true を返すケースや、常に false を返すケースも存在することに注意してください。

あなたは、なるべく少ない質問回数で各 \(i^{\star}_j\) を特定したいです。

各 \(j\) について「状態なにのときに質問するか」を求め、機械がその状態になったら質問 \(j\) をすることにします。これにより、一度状態 \(0\) から状態 \(m\) に遷移させる間に \(n\) 回質問できます。 \(n\) 個の質問たちが必要とする遷移たちが共通なので、まとめられるわけですね。

これを \(\log(m)\) 回繰り返せば各 \(i^{\star}_j\) を特定できるので、全体で \(O(m \log(m))\) 回の遷移と \(O(n\log(m))\) 回の質問をしたことになります。質問が \(n\) 個になったので質問回数は元々の \(n\) 倍になっていますが、遷移回数は悪化していません。

並列二分探索の適用

並列二分探索で \( (0, 1, \dots, n-1)\) の順列 \(a = (a_0, a_1, \dots, a_{n-1})\) の区間 \(k\)-最小値問題を解くためのやり方です。

上で言っていた機械を作ります。ここでは、機械は以下の配列 \(b = (b_0, b_1, \dots, b_{n-1})\) を管理します。配列は BIT かセグ木の形で持ちます。

状態 \(0\) においては、\(b\) の各要素は \(0\) とする。
状態 \(i\) (\(0\le i\lt n\))から状態 \(i+1\) に遷移するとき、\(a_j = i\) なる \(j\) に対して \(b_j \gets 1\) とする。
- \(a\) を値の小さい順に使っていくイメージ。
- 転倒数や LIS を求めるときと同じ、いわゆる平面走査。
質問 \( ([l, r), k)\) に対しては、\( (\sum_{j\in [l, r)} b_i) \le k\) を返す。
- 小さい順に値を入れていき、\(k+1\) 個目に入ったものが \(k\)-最小値であることに注意。

質問に対する true/false は、区間 \(k\)-最小値が未確定かどうかに対応しています。状態 \(i+1\) で初めて false になったのであれば、該当のクエリの答えは \(i\) ということになります。今回の状況設定では「常に true」「常に false」という事態は発生しません。

全体で \(O(n \log(n))\) 回の遷移と \(O(q\log(n))\) 回の質問で、各々一回あたり \(O(\log(n))\) 時間なので、全体では \(O( (n+q)\log(n)^2)\) 時間です。

実装例

コンテスト中の提出ですが、WM を用いた提出も一応貼っておきます。

あとがき

長くなってしまいました。

計算量などの兼ね合いからあまり使うことはなさそうですが、「セグ木しかないが区間 \(k\)-最小値を解く必要が出てきた」といった状況*3では役に立つことと思います。

「log 倍悪くなってしまうが手持ちのデータ構造を使えば解ける」といったものは、ライブラリの verify で役に立つことがそれなりにあるので、そうした観点では面白い気もします。

区間を BTreeSet<(int, int)> で管理するやつの verify に、区間代入クエリが使える話なども過去に書いたのですが、これもお気に入りです。

おわり

おつかれさまですにゃ。

*1:\( (\max_i a_i) \ll n\) の場合などはそれを利用して計算量が落ちたりしますが、ここでは割愛します。

*2:実際の WM では、こんな感じのことを暗に表現しています。実装もそこまで重くはないです。

*3:ある？

2021-12-26

今年のえびちゃん 2021

自分語り記事です。

えびちゃんの一年を振り返る記事をうっかり書きそうになったけど、冷静になったので却下した
— えびちゃん (@rsk0315_h4x) 2021年12月16日

うっかりし直しました。

今年お勉強したもの

数学関連のものをいくつか学んだり、昔わかった気になったものを学び直したりしました。

ACL math
- floor sum は去年だけど
  - ACL にマージされたのは今年
mod tetration
- \( (a\uparrow\uparrow b) \bmod n = \underbrace{a^{(a^{(\cdots ^a)})}}_{b\text{ many}} \bmod n\)
- 実装が悪いと \( (2\uparrow\uparrow 3)\bmod 32 = 16\) を \(0\) としてしまう
mod Ackermann
- \(A(a, b) \bmod n\)
離散対数
- \(a^x = b\pmod{n}\) なる最小の \(x\ge 0\)。なければないと言う
- 特に、法が合成数の場合
素数の数え上げ
- \(\pi(n)\)
- \(n\) 以下の素数の個数を \(O(n^{3/4}/\log(n))\) 時間で数える
\(n^2+1\) 型素数篩
- 特定の状況で必要になるやつ
- \(n^2+1\) 型の整数の素数判定をできる
- \(n^2+2n+1\) 型素数列挙というギャグもありました
Boyer–Moore majority algorithm
- 過半数を占める要素を deterministic \(O(n)\) 時間で探す
  - 「過半数を占めているとすればこれ！」というのを探す
  - 実際に占めているかの判定は、再度走査してそれの個数を数えれば可能
SA-IS
- 接尾辞配列を \(O(n)\) 時間で構築する
  - 入力アルファベットのサイズが \(O(n)\) だったりするのを仮定してそうだけど
van Emde Boas tree
- いわゆる lower_bound みたいなのと挿入・削除を \(O(\log(\log(u)))\) 時間でできる
- この記事は講義動画へのリンクがあるのだけが有用みたいなとこある
range LIS query
- これから大晦日までの間にやるつもり
DM 分解
- これは来年ということで...
ACL mcf slope や、それを使う系の問題も来年やります...
yosupo judge の問題もうめます...

他にも、全方位木 DP や遅延セグ木を実装したりしました。抽象化に納得がいかなくてもやもやしたりしています。

yosupo judge に hack case の PR を送ったり、ACL (AtCoder Library) に改善の PR を送ったりしてマージされたりしました。 floor sum に関しては、 yosupo さんが解説を書いてくださったりもしました。うれしい。

あ、計算量の記事を書いたりもしましたね。

あと、ふと思ったことを言ったら熨斗袋大先生がいい感じにしてくれたのも実はうれしかったです。

- A = {1, 2, ..., n} で初期化
- A ← A \ {i} を O(1) 時間
- A の要素の列挙を O(|A|) 時間

みたいなの、ふと思いついたけどそこまで用途ないねとなった
— えびちゃん (@rsk0315_h4x) 2021年5月2日

- A = {1, 2, ..., n} で初期化
- A ← A \ {i} を O(1)
- min { x ∈ A | x > i } を O(1)
ならギリ需要ありそう
— 熨斗袋 (@noshi91) 2021年5月2日

Z shell の man を読むのも始めたのですが、ここ数ヶ月は放置してしまっています。

社会堕ち？

えびちゃんも就職しました。陽には就職先を言っていませんが、適切にストーキングすれば公開情報から辿れるようになっています。あまり大々的には言わない方がいろいろ無難かなと思っているので、見つけてもツイートしたりはしないでもらえるとうれしい気がします。

職場では、特に競プロをしている人やえびちゃんをフォローしている人が「えびちゃん」と呼んでくれたりしてうれしいです。

環境関連とか

すっかり C++ を書く機会が減りました。整備していないが ACL にはあるライブラリを使いたいときに書くくらいになりました。ほとんど Rust ばかり書いています。

それから先月あたりに SKK を使い始めてしまい、SKK なしでの入力がおぼつかないようになってしまいました。

カーソル上の識別子の形式を変換するのを導入して、特定の場面で快適になったりしました。

キーバインド	変換後の形式
`C-c c`	lowerCamelCase
`C-c C`	UpperCamelCase
`C-c -`	kebab-case
`C-c _`	snake_case
`C-c =`	SCREAMING_SNAKE_CASE

C-c = はあまり気に入っていません。

ねこちゃん

フォロワーにねこ耳自撮りを送ったり送ってもらったりしました。たすかります。

その他

PAST がそろそろ 2 年経つのでまた受け直したりしました。

Advent of Code 2021 というのを解いたりしていました。数学系の考察は少なくて、実装がんばりましょう系が多めな気がします。実装が苦手な人はやってみるといいかもしれません。

えびちゃんのぬいを最近また買って、かわいがっています。

こんな感じで使われてる pic.twitter.com/7MOGnU5ZUK
— えびちゃん (@rsk0315_h4x) 2021年12月14日

書き忘れがまだあるかもしれません。

おわり

来年もよろしくおねがいします。

2021-12-19

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

競プロ er の間では、（主に実生活で）最適値を探そうと二分探索をして、上限を大きく取りすぎたために破滅するという定番ネタがあります*1。

あるいは、実際のコンテストでも「上限が小さすぎた」「上限を大きくしすぎたため判定関数内でオーバーフローした」などの失敗をする人はそれなりにいる印象です。後者は特に、上限を思考停止で 1e9 あるいは 1e18 にしている人にありがちです。

ここでは、「より成功率の高い思考停止の方法」として、指数探索 (exponential search) というのを紹介します。指数時間かけて全探索するというタイプのギャグではないです。

本題

以下のようなコードを考えます。

let mut ok = 0;
let mut bad = todo!();
while bad - ok > 1 {
    let mid = ok + (bad - ok) / 2;
    *(if pred(mid) { &mut ok } else { &mut bad }) = mid;
}

C++ なら以下のような感じです。

ll ok = 0;
ll bad = TODO();
while (bad - ok > 1) {
    auto mid = ok + (bad - ok) / 2;
    (pred(mid)? ok: bad) = mid;
}

mid = (ok + bad) / 2; でもいいですが、以下の理由からmid = ok + (bad - ok) / 2; を使っています：

bad がオーバーフローしなければ計算過程でオーバーフローしないこと
- （ok < 0 の場合は注意が必要です）
ループ条件で bad - ok を使っているので、それを使う方が直感的な（or 頭にやさしい）気がすること

また、その程度の最適化は人間ではなくコンパイラの役割だろうと考え、>> 1 ではなく / 2 を使っています。

さて、todo の部分を決めるために適当な値を考えるのではなく、次のようにしてみましょう。

let mut ok = 0;
let mut bad = 1;  // <- ! ここを
while pred(bad) { // <- ! 追加
    bad *= 2;     // <- ! する
}                 // <- ! だけ
while bad - ok > 1 {
    let mid = ok + (bad - ok) / 2;
    *(if pred(mid) { &mut ok } else { &mut bad }) = mid;
}

まず 1 で初期化しておき、上限が小さい限り倍々で（= 指数的に）増やしていくというものです。

答えを \(z\) としたとき、以下のうれしさがあります：

判定の回数が \(2\log_2(z)+O(1)\) 回になる
- 上限を決め打ちした場合に比べて最悪時でも高々 2 倍程度の回数にしかならない
判定関数の入力値が \(2z\) 以下にしかならない
- そこでオーバーフローしなければ問題ない
ふつうの二分探索と比べて追記の差分が小さい
- pred(mid) の形で呼び出せるものとしたときの話
- ループ内でベタ書きしていたらつらいけど、それは設計を見直していただいて...

例など

判定関数内で mid * x + y のような値を使うとき、ここがオーバーフローしないように、上限を 1e18 / x 程度にするなどが必要な場合があります。切り捨て切り上げなどの境界で間違えたり、y が大きかったりしてかわいそうになる場合もあります。

atcoder.jp

こうしたケースで上記の方法が有効になりえます。もちろん、オーバーフローに対して完全に思考停止したいなら多倍長整数を使うのがいいとは思いますが、その辺の見極めは各々に任せます。思考停止で 1e18 にするよりは、よっぽどマシな気はします。

また、思考停止以外の文脈でも有用で、たとえば「ランダム文字列が二つあり、一致する共通接頭辞の長さを二分探索したい」といった状況で、「ランダム文字列なのだから答えは小さいはずで、最初から文字列長を上限としなくてもよさそう」という推測から、高速化を図ったこともありました（若干ネタ記事としての色が強いですが...）。

rsk0315.hatenablog.com

（↑この記事は、ロリハから SA を作れるということ自体よりも、ロリハで辞書順比較も高速に行えるという部分が有用パートな気がします）

あとがき

グオーーのネタに対するマジレス記事のような感じにはしたくありませんでした。一方で、「にぶたんを実生活でやろうとするとどうしてもグオーーになってしまう」のように思っていそうな初心者の気配を感じることが何度かあったため、書きたくなってしまいました。

指数探索の欠点としては、ツイッター映えしないというのがありますね。

おわり

この記事は Advent Calendar とは一切関係ありません。

*1:いわゆる \ﾎﾞﾝｯ/グオーーーー。ほか多数。

2021-11-26

夢の内容（概要）

競プロ er がたくさんいる会社があります。各社員をレーティング順に並べたリストが公開されています。さらに、各社員を出身校ごとに分けたときの順位も公開されています。出身校自体は非公開です。次のような感じです。

名前	順位	出身校順位
A	1	1
B	2	1
C	3	2

このとき、同じ出身校である社員たちのグループ（同じグループ間の社員は出身校が同じ、そうでない社員はそうでない）は何通り作れるのか気になりました。この例では、[[A, C], [B]] と [[A], [B, C]] の 2 通りです。

問題

もう解けている人もいるかもなんですが、より形式的に書きます。

問題文

まず、集合 \(T\) の分割を、集合の集合 \(\mathcal{S} = \{S_1, S_2, \dots, S_m\}\) であって、次の条件を満たすものと定めます。

\(S_1 \cup S_2 \cup \dots \cup S_m = T\)
各 \(i\) (\(1\le i\le m\)) に対して \(S_i \ne \emptyset\)
各 \(i, j\) (\(1\le i\lt j\le m\)) に対して \(S_i \cap S_j = \emptyset\)

例（クリックで展開）

\(T=\{1, 2, 3, 4\}\) のときの分割の例：

\(\{\{1, 3\}, \{2\}, \{4\}\}\)
\(\{\{1, 2, 3, 4\}\}\)
\(\{\{1\}, \{2\}, \{3\}, \{4\}\}\)

\(T=\{1, 2, 3, 4\}\) のときの分割でない例：

\(\{\}\)
\(\{\{\}\}\)
\(\{\{1, 3\}, \{1, 4\}, \{2\}\}\)
\(\{\{1, 3\}, \{2\}\}\)
\(\{\{1, 2, 3, 4, 5\}\}\)

（クリックして展開部分おわり）

数列 \(A = (a_1, a_2, \dots, a_n)\) が与えられます。集合 \(\{1, 2, \dots, n\}\) の分割 \(\mathcal{S}\) であって、以下の条件を満たすものの個数を \(998244353\) で割ったあまりを求めてください。

各 \(S\in\mathcal{S}\) に対して、以下がすべて成り立つ
- ある \(i\in S\) に対して \(a_i = 1\)
- すべての \(i\in S\) (\(a_i \ne |S|\)) について、ある \(j\in S\) が存在して \(a_j = a_i + 1\)
- すべての \(i, j\in S\) に対して \(i\lt j \implies a_i \lt a_j\)

制約

\(1\le n\le 10^6\)
\(1\le a_i\le n\) (\(1\le i\le n\))

例

input 1

3
1 1 2

output 1

上記の例です。

input 2

4
1 2 2 3

output 2

input 3

12
1 1 1 2 1 2 2 3 2 3 3 3

output 3

解答

クリックして展開

とりあえず、愚直に \(A\) を先頭から見ていって valid な分割を全通り作ることを考えます。 \(\mathcal{S} = \{\}\) で初期化しておきます。

\(a_i = 1\) であれば、\(S\in\mathcal{S}\) に追加することはできないので、\(\mathcal{S} \gets \mathcal{S}\cup\{\{i\}\}\) で更新します。

\(a_i \gt 1\) であれば、\(S\in\mathcal{S}\) のうち \(|S|+1 = a_i\) であるものを選んで、\(\mathcal{S} \gets (\mathcal{S}\setminus S)\cup(S\cup\{i\})\) で更新します。ただし、そうした \(S\) が存在しなければ valid な分割は作れません。

クリックしてさらに展開

上記の手順を見ると、\(a_i\) を見たときに行える操作の通り数は、その時点での \(\mathcal{S}\) にサイズ \(a_i-1\) の集合がいくつあるかに依っていることがわかります。また、そこでどの \(S\) を選んで更新したとしても、各サイズの個数の変わり方は同じであることもわかります。

クリックしてさらに展開

なので、各サイズの個数を管理しながら答えを更新していけばよいです。\(O(n)\) 時間です。

use proconio::{input, marker::Usize1};

const MOD: u64 = 998244353;

fn main() {
    input! {
        n: usize,
        a: [Usize1; n],
    }
    let mut size_count = vec![0; n];
    let mut res = 1;
    for ai in a {
        if ai > 0 {
            if size_count[ai - 1] == 0 {
                println!("0");
                return;
            }
            res *= size_count[ai - 1];
            res %= MOD;
            size_count[ai - 1] -= 1;
        }
        size_count[ai] += 1;
    }
    println!("{}", res);
}

所感

区間クエリとかにできたりしないかなぁ。右を伸ばしたり縮めたりするのは簡単だけど、左をそうするのは難しそう。← Mo のことを考えています。

サイズが \(\sqrt{n}\) より大きい集合は高々 \(\sqrt{n}\) 個しか作れないこととかを使ってなんかできたりしないかなぁ。変な数列だとすぐ invalid になることとかも使えないかなぁ。

類題

これが似ている気がします。

宣伝

他にも夢由来の記事はあります。

rsk0315.hatenablog.com

おわり

お粗末さまでした。