概要
を満たす
の正整数の約数の個数の最大値は
程度と思っておけば競プロの計算量の見積もりで便利そう。
実験
を
の正の約数の個数として、
と定義し、
と
の関係を見る。
つまり、 と見積もると実際 *1 にはその
倍から
倍程度に収まることになる。
例えば、 なら
の約数の個数の
乗が
より小さいくらいになって
sec に間に合いそうと分かる。
*1:競プロだと がほとんどだろうという仮定の下
2022/05/02 記事中の記号の使い方やその他の軽微な修正をしました。
のアフィン部分空間が
の形で与えられるとき、
つのアフィン部分空間の共通部分を時間計算量
で計算する。
ベクトル空間 の部分集合
は、部分空間
と
によって
と表現できるとき、アフィン部分空間であると言う。
アフィン部分空間は部分空間の一般化になっており、後述するが競プロでも出現する概念である。
に対して
は一意だが
は一般には一意でない。
を体として、
を
のアフィン部分空間とする。
定義から明らかに、
によって
と表現できる。
ここで
は
としたときの
の次元である。
(ドット積についての) 直交補空間を考えると、 となる
が存在する。
すると、
であり、諸々の記号を置きなおすと結局
という表現を得る*1。
逆に、
と表現される集合は、空であるかアフィン部分空間であることもすぐに確かめられる。
をアフィン部分空間として、
と表現できるとする。
すると
であり、容易に共通部分の表現が得られる。
この式から分かるように、これらのアフィン部分空間の共通部分は空であるかアフィン部分空間となる。
と
の表現の相互の変換は、直交補空間の計算と同様に行うことができる (参考: Parity-check matrix - Wikipedia)。
注意: cp-unspoiler この問題のネタバレを含みます。
を、
を
の元として見てこの順に連結したベクトルと定義する。
問題は以下のように整理される。
長さ
の非負整数列
と、非負整数
が与えられる。
から
つ以上選んで xor を計算し、前半
bit が
以下になるようにしつつ、後半
bit を最大化せよ。
以下の非負整数全体は、「下位
bit は自由で、残りは決まっている」という形の集合の高々
個の直和に分解される。
この分解のそれぞれについて独立に計算し、最後に最大値を取ればよい。
つ以上選ぶという条件を一旦
個以上に緩和すると、「
から
個以上選んで xor を取ることで得られる数全体」と「下位
bit は自由で、残りは決まっている数全体」はいずれも (
の) アフィン部分空間になっている。
したがって、これらの共通部分
を計算した後、
の元で後半
bit が最大となるものを計算すればよい。
実際には、
の定義を
の順に連結することにして、単に
を求めるのが簡単だろう。
かつ
が線形独立である場合に限り最大値を
に修正することで、
つ以上選ぶ条件をカバーする。
は、
の列ベクトルを掃き出して簡約化し、
に対して基底を貪欲に足していけばよい。
簡略化のため、 として以下を未満に言い換えている。
Submission #31329771 - Monoxer Programming Contest 2022(AtCoder Beginner Contest 249)
*1: の形式とどちらが綺麗なのかは分からない。
Xorshift によって生成された乱数列について、いくつかの場所の xor を取ると seed に依存せずに になる。
説明は Wikipedia に丸投げする。
本記事では簡略化のため、実装例の一番上にある周期 の実装について議論する。
個の要素があるとして、要素
に乱数
を割り当てる。
このとき、集合
の hash
を
で定める。
ただし
は bitwise xor とする。
この hashing の方法を Zobrist hashing と呼ぶ。
異なる集合 について
となることを衝突と呼ぶ。
Zobrist hashing の場合
であるから、
かつ
となるような
が分かれば衝突を引き起こすことができる。
結論から言うと、 を Xorshift が
番目に出力した値として設定した場合、seed に依存せず
となるような
が存在する。
Xorshift の乱数列は途中から切り出しても何らかの seed を与えた Xorshift の乱数列であるから、
の設定が行われるまでに何度か乱数生成されていても衝突することになる。
思いつく回避方法を挙げる
32 bit 整数をベクトル空間 の元として解釈する。
整数の xor が
における
に対応することに注意せよ。
このとき、Xorshift における演算は全て
上の線形変換となっている。
従って、線形写像
によって Xorshift は以下のように表現できる (酷く厳密性に欠ける表現ではあるが)。
V Xorshift() { static V y = seed; y = A(y); return y; }
つまり、Xorshift の乱数列は初項を として
と表現される。
の最小多項式を
とすると、定義より
である。
とすると、
は求める集合になっている。
Cayley-Hamilton の定理より、 として最小多項式ではなく固有多項式を用いても良い。
周期
の実装例を用いた場合でも、全く同様の議論で衝突を起こすことができる。
固有多項式を用いて、 を得た。
seed を自由に変えて実行してみると、毎回 hash が衝突していることが分かる。
における
乗は
の指数を
倍したものに等しいため、Xorshift を
つ飛ばしにしてもそのまま衝突する。
また、
は reverse について不変なので、Xorshift を逆から読んでも衝突する。
*1:この変化は役に立たない。追記を参照せよ。
木上の等高線集約クエリ - suisen のブログ
この記事で未解決になっていた変種 を解決する。
を可換モノイドとし、
頂点の木
の各頂点には
の元が書き込まれているとする。
以上のクエリを前計算 、
クエリ
の時間計算量で処理できる。
ただし
の演算は
で可能とする。
また、同様の手法によって区間作用 点取得も処理できる。
JOI 2021/2022 春合宿 day3-2 がこの問題だが、時間計算量的に通るかどうかはよく分からない。
距離が辺の重み付きで定義される場合も前計算が かかるものの同様に処理できる。
概要で述べた記事の内容を概ね理解していることを前提とする。
から重心を取り除いたときに分かれる部分木たちを
とする。
従来の手法で問題となっていたのは、重心の次数が
になってしまい、ここの処理に時間がかかるという点である。
そこで、
を一度に重心に付ける
分木ではなく、
と対応しないノードを間に挟み二分木を作る。
上図において実線の三角形は の元であり、点線の長方形は
に対応しない新たに追加されたノードである。
書き込まれた数は後述するアルゴリズムにおける重みである。
新たに追加されたノードについても、その子孫の頂点たちを深さ順に並べて Segment Tree で管理する。
また、 の元については従来の重心分解同様、再帰的に重心を取り除き木構造を作成し、得られた根付き木を
とする。
この状態で更新クエリを処理することを考えると、
において
から根に至るのパスの長さが
になっているかどうかが問題となる。
の元の重みをその部分木の頂点数として
を葉とする Huffman coding の木を作ることで、それが達成される。
具体的には以下のアルゴリズムを実行する。
において
から根に至るパス
の長さを考える。
の重み
を、
において
の子孫である
の頂点の個数と定義する。
において
の次に現れる
の頂点を
とすると、
-
パスの長さは
以下である。
これは
の親を
つ辿ると
が
倍以上になるためであり、Huffman coding の木を作るアルゴリズムから証明できる。
において
の頂点が現れる回数は重心分解自体の性質により
であり、
の第
項の和は
となる。
の第
項の和は telescoping sum の形であるから
となる。
厳密な定式化はできていないが、領域木でできるクエリは全部できるのではないかと思う (形が同じなので)。 裏を返すと、一般の区間更新区間取得は難しそうに見える。
チームメイトに投げる場面が多く自分の実力の低下を感じた。 K を検索したのが一番の貢献だったはずだが通せなかったため無に 来年度どうするかあまり考えていない (参加はしたい)
今年は特に問題が面白いと感じたので upsolve 予定
が
を満たすとする。
を与えると
を
の時間計算量で取得できるとして、
を満たす
を
の時間計算量で求めるアルゴリズムが存在する。
一般の数列を三分探索すると極小点が求まるとは限らない - noshi91のメモ
上記の記事の後半で紹介しているアルゴリズムを、 で初期化して、
に対して適用すればよい。
次元平面上に点群があり、ベクトル
の方向に最も遠い点を求めることを考える。
点群の凸包を
、その頂点を順に
として
と定義する。
は
の頂点数を周期とする関数であり、
の極大点が求める点である。
三分探索を行うと極小点が つも求まらないような数列を構成した。
また、一般の数列に対して
の時間計算量で極小点を
つ求めるアルゴリズムを説明する。
を実数列とする。
整数
が
の極小点であることを、
を満たすことと定義する。
ただし仮想的に
とする。
が丁度
つの極小点を持つとき、三分探索を用いると
に
回アクセスすることでその極小点を求めることができる。
三分探索は以下のようなアルゴリズムである。
最初、 とする。
「
の極小点
が
を満たす」という条件を維持したまま
を狭めていく。
の場合
が極小点であり、アルゴリズムを終了する。
の場合
とする。
は隣接項の差が
以上であるから、それぞれに floor 関数を適用した
は狭義単調増加列になることに注意。
の場合
と更新して繰り返す。
の場合
と更新して繰り返す。
が起こるたびに
は
以下になるから、時間計算量は
である。
の例を図示した。
数列ではなく関数のグラフになっているが、適当に離散化して考えて欲しい。
回のイテレーションの後
となり、極小点が存在しないことが分かる。
黄金分割探索は、一般の数列に対しても つ極小点を求めることができる (詳細略)。
本記事では、黄金分割探索とは異なるアルゴリズムを説明する。
最初 とする *1。
「
かつ
」を満たすという条件を保ちつつ、
を狭めていく。
の場合
であり、不変条件から
が極小点である。アルゴリズムを終了する。
の場合
とする。
である。
の場合
不変条件と併せて である。
特に
より
も満たされるため、
と更新して繰り返す。
の場合
の場合と対称である。
と更新して繰り返す。
の場合
と更新して繰り返す。
と定義すると、
が起こるたびに
は
以下になるから、時間計算量は
である。
*1:実は としてもほとんど問題ないが、イメージのしやすさのため
は中央付近に取った