noshi91 が書いた AtCoder のユーザー解説一覧

Increasing Prefix XOR

https://atcoder.jp/contests/arc141/editorial/4048

$f(x)$ と $f(2x)$ を比較することで、答えの具体的な形を FPS を使って導出する。q-binomial coefficient と関係がある。

Stonks

https://atcoder.jp/contests/abc250/editorial/3945

離散凸解析の言葉で解法を機械的に導出。infimal convolution など。

Trespassing Takahashi

https://atcoder.jp/contests/abc250/editorial/3939

完全グラフの辺の重みが、別のグラフにおける距離になっているとき、その最小全域木は高速に計算できる。

Endless Walk

https://atcoder.jp/contests/abc245/editorial/3667

ゲームの後退解析やトポロジカルソートっぽい方法で閉路を検出。

Minimum Coloring

https://atcoder.jp/contests/abc231/editorial/3095

流量下限付きの最小費用流で、二部グラフの最小重み辺被覆を解く。

Bullion

https://atcoder.jp/contests/abc230/editorial/3036

ある種の分割統治 FFT を relaxed multiplication で定式化する。

Linear Probing

https://atcoder.jp/contests/abc228/editorial/2962

要素が $\lbrace 1, 2, \dots, N \rbrace$ で削除しかされない状況では、predecessor クエリが高速に処理できる。

Count Multiset

https://atcoder.jp/contests/abc221/editorial/2738

分割数の DP を工夫して、同じ数が $M$ 個を超えて出現できない分割を数え上げる。

Red and Blue Lamps

https://atcoder.jp/contests/abc218/editorial/2638

Monge グラフ上の $d$ 辺最短路。連続部分列に分解する問題で Alien's trick を使おうとすると Monge くらいしか凸性の保証ができないのではないかと思う。

Colorful Candies 2

https://atcoder.jp/contests/abc215/editorial/2531

多項式の Taylor Shift を使った数え上げの処理。

No Need

https://atcoder.jp/contests/abc056/editorial/2092

存在判定を数え上げにすることで戻す DP を可能にするテクニック。

ボディーガード (Bodyguard)

https://atcoder.jp/contests/joisc2021/editorial/1233

傾きではなく切片の方に単調性がある CHT の高速化。

2022-07-09

ICPC 2022 国内予選参加記

potato167, noshi91, tatyam で参加しました。

tatyam 視点 → ICPC 2022/23 国内予選参加記 (tatyam 視点) | 東京工業大学デジタル創作同好会traP

初手

A: potato, B: tatyam, C: noshi で担当。noshi は実装が遅いので序盤の速度ゲーに触りたくないため、この位置に入れてもらった。

C

休息と練習を連長圧縮したときにどうなるかで場合分けして書こうとするが、始まりと終わりがそれぞれ休息/練習のパターンを全て考慮するとうんざりするため手が止まる。練習をいくつに分割するかを固定すればサクッと解けることに気付き、通す。

D

C を通して状況を聞くと、potato が D を読んでとりあえず飛ばして E を読んでいるらしいので D を見る。作りたい列の部分列が 1 本の列として成立するかどうかの必要条件を列挙するといかにも十分条件になっていそうで、証明できた。これをもとに DP を書き始めるのだが、素朴にやると 3 乗なので逆から読んで累積和を使うと 2 乗になり、通る。後で解説を読むとあまりにも簡潔で反省。

F

tatyam が E と格闘しているらしいので、F を見る。構文解析した後は木 DP するしかないように見え、先頭から l 文字末尾から r 文字追加で t 文字消すみたいな DP で計算は出来そう。落ち着いて考えると t は持たない方が良い。あまり詰めてなくて正当性も時間計算量も怪しいが、noshi は後半の問題の方が得意そうなので F を potato に任せて逃げる。

H

読んで 1 分くらいで考察が終わる。体感時間なのでもっと掛かってるかも、とりあえず考察で詰まる場所は無し。実装も結構軽そうなので F に戻らずに実装開始を宣言。通る。

G

まず、後戻りが必要な場合が存在するかを考え始める。すると普通に必要そうということになり、状況が複雑すぎるので解法の選択肢があまり多くないように思える。とりあえず二分探索することにすると、エージェント A が進んだ距離と B が進んだ距離を 2 軸とする平面において、距離 D 以下の点を考える。これで (1, 1) と (n, m) が連結になっていればよい。平面を格子状に細切れにして、双方のエージェントが線分上を移動するような長方形領域に分ける。すると距離 D 以下の点は楕円になり、特に凸集合なので連結。後は隣り合う長方形に移動できるか調べて連結性を判定すればよい。

ここまで考えたあたりで tatyam が E を通していた気がする。 tatyam に G を説明しつつ、そもそも二分探索しない方が 100 倍簡潔であることに気付き説明し直したりグダっている間に tatyam が理解。 G を通せば勝てると思ったので、2 人で並列実装して出力をそろえてから提出することにする。

ほとんど同時に書き終わるが、出力が合わない。合わないケースにおいて常に noshi の方が出力が大きいことから、始点と終点の処理を忘れているだろうとエスパーしたところ、成功。 tatyam が修正をして AC。

F

この時点で残り 30 分くらいだったと思う。 potato が F で苦戦していて WA が出ていた。とりあえず説明してもらいながらコードを眺めるが、そもそも構文解析の時点で読解に苦戦。 tatyam にデバッグしてもらいつつ、noshi は新たに書き始めることにする。

とりあえず構文解析を書こうとして、LL(k) でないことに気付く。こういうときどうすればいいか分からず構文解析のコードが滅茶苦茶になり (反省)、時間を浪費。のこり 10 分ほどになりこちらは無理ですと謝罪していたら、バグが直ったらしく通る。

全体の感想

今日は解法がすぐに出てきた。多少裏目に出た部分はあったが、立ち回りは悪くなかった気がする。勝って非常に気分が良いので、何でもいい (本音)

2022-07-05

競プロにおける約数の個数の見積もり

概要

$n \leq N$ を満たす $n$ の正整数の約数の個数の最大値は $N ^ {1/ 3}$ 程度と思っておけば競プロの計算量の見積もりで便利そう。

実験

$d(n)$ を $n$ の正の約数の個数として、 $\displaystyle r = \frac{\max _ {1 \leq n \leq N} d(n)}{N ^ {1 / 3}}$ と定義し、 $N$ と $r$ の関係を見る。

つまり、 $N ^ {1 / 3}$ と見積もると実際 *1 にはその $0.1$ 倍から $3.5$ 倍程度に収まることになる。

例えば、 $n \leq 10 ^ {12}$ なら $n$ の約数の個数の $2$ 乗が $10 ^ {8}$ より小さいくらいになって $1$ sec に間に合いそうと分かる。

*1:競プロだと $N \leq 10 ^ {18}$ がほとんどだろうという仮定の下

2022-04-29

アフィン部分空間の共通部分の計算

2022/05/02 記事中の記号の使い方やその他の軽微な修正をしました。

概要

$\mathbb{F} _ p ^ d$ のアフィン部分空間が $\mathrm{span}\lbrace a _ 1, a _ 2, \dots, a _ n \rbrace + b$ の形で与えられるとき、 $2$ つのアフィン部分空間の共通部分を時間計算量 $\Theta( (n + d) d ^ 2 + d \log(p) )$ で計算する。

アフィン部分空間

ベクトル空間 $V$ の部分集合 $S$ は、部分空間 $U \subseteq V$ と $b \in V$ によって $S = \lbrace u + b \mid u \in U \rbrace$ と表現できるとき、アフィン部分空間であると言う。アフィン部分空間は部分空間の一般化になっており、後述するが競プロでも出現する概念である。 $S$ に対して $U$ は一意だが $b$ は一般には一意でない。

アフィン部分空間の $2$ 通りの表現

$\mathbb{K}$ を体として、 $S$ を $\mathbb{K} ^ d$ のアフィン部分空間とする。定義から明らかに、 $A \in \mathbb{K} ^ {d \times n}, b \in \mathbb{K} ^ d$ によって $S = \lbrace Ax + b \mid x \in \mathbb{K} ^ n \rbrace$ と表現できる。ここで $n$ は $S = \lbrace u + b \mid u \in U \rbrace$ としたときの $U \subseteq \mathbb{K} ^ d$ の次元である。

(ドット積についての) 直交補空間を考えると、 $\lbrace Ax \mid x \in \mathbb{K} ^ n \rbrace = \lbrace y \mid y \in \mathbb{K} ^ d , Cy = 0 \rbrace$ となる $C \in \mathbb{K} ^ {(d - n) \times d}$ が存在する。すると、 $S = \lbrace y + b \mid y \in \mathbb{K} ^ d, Cy = 0 \rbrace = \lbrace y + b \mid (y + b) \in \mathbb{K} ^ d, C(y + b) = Cb \rbrace$ であり、諸々の記号を置きなおすと結局 $S = \lbrace y \in \mathbb{K} ^ d \mid Cy = d \rbrace$ という表現を得る*1。逆に、 $\lbrace y \in \mathbb{K} ^ d \mid Cy = d \rbrace$ と表現される集合は、空であるかアフィン部分空間であることもすぐに確かめられる。

アフィン部分空間の共通部分の計算

$S _ 1, S _ 2$ をアフィン部分空間として、 $S _ 1 = \lbrace y \in \mathbb{K} ^ d \mid C _ 1 y = d _ 1 \rbrace, S _ 2 = \lbrace y \in \mathbb{K} ^ d \mid C _ 2 y = d _ 2 \rbrace$ と表現できるとする。すると $\displaystyle S _ 1 \cap S _ 2 = \left \lbrace y \in \mathbb{K} ^ d ~ \middle | \pmatrix{C _ 1 \cr C _ 2} y = \pmatrix{d _ 1 \cr d _ 2} \right \rbrace$ であり、容易に共通部分の表現が得られる。この式から分かるように、これらのアフィン部分空間の共通部分は空であるかアフィン部分空間となる。 $\lbrace Ax + b \mid x \in \mathbb{K} ^ n \rbrace$ と $\lbrace y \in \mathbb{K} ^ d \mid Cy = d \rbrace$ の表現の相互の変換は、直交補空間の計算と同様に行うことができる (参考: Parity-check matrix - Wikipedia)。

実用例

注意: cp-unspoiler この問題のネタバレを含みます。

G - Xor Cards

$C _ i$ を、 $A _ i, B _ i$ を $\mathbb {F} _ 2 ^ {30}$ の元として見てこの順に連結したベクトルと定義する。問題は以下のように整理される。

長さ $N$ の非負整数列 $(C _ i)$ と、非負整数 $K$ が与えられる。 $C$ から $1$ つ以上選んで xor を計算し、前半 $30$ bit が $K$ 以下になるようにしつつ、後半 $30$ bit を最大化せよ。

$K$ 以下の非負整数全体は、「下位 $t$ bit は自由で、残りは決まっている」という形の集合の高々 $\log _ 2(K) + 1$ 個の直和に分解される。この分解のそれぞれについて独立に計算し、最後に最大値を取ればよい。

$1$ つ以上選ぶという条件を一旦 $0$ 個以上に緩和すると、「 $C$ から $0$ 個以上選んで xor を取ることで得られる数全体」と「下位 $t$ bit は自由で、残りは決まっている数全体」はいずれも ( $\mathbb{F} _ 2 ^ {60}$ の) アフィン部分空間になっている。したがって、これらの共通部分 $S$ を計算した後、 $S$ の元で後半 $30$ bit が最大となるものを計算すればよい。実際には、 $C _ i$ の定義を $B _ i, A _ i$ の順に連結することにして、単に $\max S$ を求めるのが簡単だろう。 $\max S = 0$ かつ $(C _ i)$ が線形独立である場合に限り最大値を $-1$ に修正することで、 $1$ つ以上選ぶ条件をカバーする。

$\max \lbrace Ax + b \mid x \in V \rbrace$ は、 $A$ の列ベクトルを掃き出して簡約化し、 $b$ に対して基底を貪欲に足していけばよい。

実装例

簡略化のため、 $K \leftarrow K + 1$ として以下を未満に言い換えている。

Submission #31329771 - Monoxer Programming Contest 2022（AtCoder Beginner Contest 249）

*1: $Cy + d = 0$ の形式とどちらが綺麗なのかは分からない。

2022-04-18

Xorshift を用いた Zobrist hashing を衝突させる方法

概要

Xorshift によって生成された乱数列について、いくつかの場所の xor を取ると seed に依存せずに $0$ になる。

Xorshift

Xorshift - Wikipedia

説明は Wikipedia に丸投げする。本記事では簡略化のため、実装例の一番上にある周期 $2 ^ {32} - 1$ の実装について議論する。

Zobrist hashing

$N$ 個の要素があるとして、要素 $i$ に乱数 $r _ i \in \mathbb{Z} _ {\geq 0}$ を割り当てる。このとき、集合 $S$ の hash $h(S)$ を $\displaystyle \bigoplus _ {i \in S} r _ i$ で定める。ただし $\oplus$ は bitwise xor とする。この hashing の方法を Zobrist hashing と呼ぶ。

hash の衝突

異なる集合 $T _ 1, T _ 2$ について $h(T _ 1) = h(T _ 2)$ となることを衝突と呼ぶ。 Zobrist hashing の場合 $h(T _ 1) = h(T _ 2) \Leftrightarrow h(T _ 1 \mathbin{\triangle} T _ 2) = 0$ であるから、 $S \neq \emptyset$ かつ $h(S) = 0$ となるような $S$ が分かれば衝突を引き起こすことができる。

結論から言うと、 $r _ i$ を Xorshift が $i$ 番目に出力した値として設定した場合、seed に依存せず $h(S) = 0$ となるような $S \subseteq \lbrace 0, 1, \dots, 32 \rbrace$ が存在する。 Xorshift の乱数列は途中から切り出しても何らかの seed を与えた Xorshift の乱数列であるから、 $r _ i$ の設定が行われるまでに何度か乱数生成されていても衝突することになる。思いつく回避方法を挙げる

$r _ i$ の設定を行う際に ~~1 つ飛ばしや逆順にするなどの~~ *1 変化を加える。ソースコードを読まれた場合対応される可能性がある。
Xorshift における shift の幅などを変える。ソースコードを読まれると対応される上、パラメータを間違えると乱数の質が落ちる。
Xorshift 以外の乱数生成アルゴリズムを用いる。

$S$ の存在の証明、及び構成方法

32 bit 整数をベクトル空間 $V := \mathbb{F} _ 2 ^ {32}$ の元として解釈する。整数の xor が $V$ における $+$ に対応することに注意せよ。このとき、Xorshift における演算は全て $V$ 上の線形変換となっている。従って、線形写像 $A: V \to V$ によって Xorshift は以下のように表現できる (酷く厳密性に欠ける表現ではあるが)。

V Xorshift() {
    static V y = seed;
    y = A(y);
    return y;
}

つまり、Xorshift の乱数列は初項を $t$ として $t, A(t), A ^ 2(t), \dots$ と表現される。 $A$ の最小多項式を $p(X) \in \mathbb{F} _ 2 \lbrack X \rbrack$ とすると、定義より $p(A)(t) = 0$ である。 $S := \lbrace i \mid \lbrack X ^ i \rbrack p(X) = 1 \rbrace$ とすると、 $S$ は求める集合になっている。

Cayley-Hamilton の定理より、 $p$ として最小多項式ではなく固有多項式を用いても良い。周期 $2 ^ {128} - 1$ の実装例を用いた場合でも、全く同様の議論で衝突を起こすことができる。

Wikipedia の 32 bit の実装を衝突させる例

固有多項式を用いて、 $S = \lbrace 0, 6, 9, 14, 15, 17, 18, 19, 20, 21, 32 \rbrace$ を得た。 seed を自由に変えて実行してみると、毎回 hash が衝突していることが分かる。

[C++] gcc 11.1.0 - Wandbox

追記

$\mathbb{F} _ 2 \lbrack X \rbrack$ における $2$ 乗は $X$ の指数を $2$ 倍したものに等しいため、Xorshift を $1$ つ飛ばしにしてもそのまま衝突する。また、 $\mathrm{rev}(p) p$ は reverse について不変なので、Xorshift を逆から読んでも衝突する。

*1:この変化は役に立たない。追記を参照せよ。

2022-03-27

重心分解で 1 点更新区間取得

概要

木上の等高線集約クエリ - suisen のブログこの記事で未解決になっていた変種 $1, 1'$ を解決する。

$M$ を可換モノイドとし、 $N$ 頂点の木 $T$ の各頂点には $M$ の元が書き込まれているとする。

$v \in V(T)$ に書かれている値を $x \in M$ に書き換える。
$v \in V(T)$ から距離 $a$ 以上 $b$ 未満の頂点に書かれた値の総和を出力する。

以上のクエリを前計算 $\Theta(N \log(N))$ 、 $1$ クエリ $\Theta( (\log(N) ) ^ 2)$ の時間計算量で処理できる。ただし $M$ の演算は $\mathrm{O}(1)$ で可能とする。

また、同様の手法によって区間作用 $1$ 点取得も処理できる。 JOI 2021/2022 春合宿 day3-2 がこの問題だが、時間計算量的に通るかどうかはよく分からない。

距離が辺の重み付きで定義される場合も前計算が $\Theta(N (\log(N) ) ^ 2)$ かかるものの同様に処理できる。

アルゴリズム

概要で述べた記事の内容を概ね理解していることを前提とする。

$T$ から重心を取り除いたときに分かれる部分木たちを $L$ とする。従来の手法で問題となっていたのは、重心の次数が $\lvert L \rvert$ になってしまい、ここの処理に時間がかかるという点である。そこで、 $L$ を一度に重心に付ける $\lvert L \rvert$ 分木ではなく、 $V(T)$ と対応しないノードを間に挟み二分木を作る。

f:id:noshi91:20220327041409j:plain

上図において実線の三角形は $L$ の元であり、点線の長方形は $V(T)$ に対応しない新たに追加されたノードである。書き込まれた数は後述するアルゴリズムにおける重みである。

新たに追加されたノードについても、その子孫の頂点たちを深さ順に並べて Segment Tree で管理する。また、 $L$ の元については従来の重心分解同様、再帰的に重心を取り除き木構造を作成し、得られた根付き木を $U$ とする。この状態で更新クエリを処理することを考えると、 $U$ において $v \in V(T)$ から根に至るのパスの長さが $\mathrm{O}(\log(N) )$ になっているかどうかが問題となる。 $L$ の元の重みをその部分木の頂点数として $L$ を葉とする Huffman coding の木を作ることで、それが達成される。具体的には以下のアルゴリズムを実行する。

$Q := L$ とする。
の間、以下を繰り返す。
- $Q$ から重みが最小及び $2$ 番目に小さい元を取り出し、それらを子とするノードを作成する。作成されたノードの重みを子の重みの和と定義し、 $Q$ に追加する。

$U$ において $v \in V(T)$ から根に至るパス $P$ の長さを考える。 $x \in V(U)$ の重み $w(x)$ を、 $U$ において $x$ の子孫である $T$ の頂点の個数と定義する。 $P$ において $v$ の次に現れる $T$ の頂点を $x$ とすると、 $v$ - $x$ パスの長さは $c + c \log(w(x) / w(v) ) \cdots \bigstar$ 以下である。これは $v$ の親を $2$ つ辿ると $w$ が $2$ 倍以上になるためであり、Huffman coding の木を作るアルゴリズムから証明できる。 $P$ において $T$ の頂点が現れる回数は重心分解自体の性質により $\mathrm{O}(\log(N) )$ であり、 $\bigstar$ の第 $1$ 項の和は $\mathrm{O}(\log(N) )$ となる。 $\bigstar$ の第 $2$ 項の和は telescoping sum の形であるから $\mathrm{O}(\log(N) )$ となる。