2021-06-02

3 次元空間のクエリを処理する Wavelet Matrix

概要

Wavelet Matrix は 2 次元空間の点群に関するクエリを処理するデータ構造と見ることが出来ます。これを発展させて 3 次元空間の点群に関するクエリを $\Theta ( ( \log ( \sigma ) ) ^ 2 )$ で処理するデータ構造が存在します。

出来ること

- $A$ を非負整数の $2$ つ組の列として、データ構造を構築する。
- 時間計算量 $\Theta ( \lvert A \rvert ( \log ( \sigma ) ) ^ 2 )$
- 空間計算量 $\Theta ( \lvert A \rvert ( \log ( \sigma ) ) ^ 2 / w )$
- $\sigma$ は各成分の最大値
- $A \lbrack l , r )$ で第 $0$ 成分が $\lbrack d , u )$ かつ第 $1$ 成分が $\lbrack s , t )$ のものの個数を出力する。
- 時間計算量 $\Theta ( ( \log ( \sigma ) ) ^ 2 )$
- $A \lbrack l , r )$ で第 $0$ 成分が $\lbrack d , u )$ のもののうち、第 $1$ 成分が $k$ 番目に小さいものを出力する。
- 時間計算量 $\Theta ( ( \log ( \sigma ) ) ^ 2 )$

アルゴリズム

通常の Wavelet Matrix における $\mathtt { quantile } ( l , r , k )$ の処理は以下のような具合でした。

int ret = 0;
for (int p = matrix.size(); p-- != 0;) {
    bit_vector &vec = matrix[p];
    int zeros = vec.rank0(l, r); // この段の [l, r) における 0 の個数
    if (zeros <= k) { // 答えの p bit 目は 1
        ret |= 1 << p;
        k -= zeros;
        l = vec.rank0(0, n) + vec.rank1(0, l);
        r = vec.rank0(0, n) + vec.rank1(0, r);
    } else {
        l = vec.rank0(0, l);
        r = vec.rank0(0, r);
    }
}
return ret;

第 $1$ 成分についての Wavelet Matrix を構築して、 $\mathtt { quantile } ( l , r , d , u , k )$ のクエリを処理することを考えます。 $\mathtt { quantile } ( l , r , k )$ と異なるのは、zeros を計算する部分のみです。この部分を、第 $0$ 成分が $\lbrack d , u )$ の要素に限定して数えることが出来れば、全く同様の処理を行うことが出来ます。格段について、bitvector が 0 の成分だけ抜き出して第 $0$ 成分についての Wavelet Matrix を構築すれば、求める値を計算することが可能です。

$\mathtt { count } ( l , r , d , u , s , t )$ もほとんど同様です: 第 $1$ 成分について通常の処理をしながら、答えに加算する時だけ第 $0$ 成分を考慮した値を足し上げます。

実装例

Submission #23120967 - AtCoder Beginner Contest 203（Sponsored by Panasonic）

ABC203 D - Pond に提出して TLE したものです。

2021-05-05

区間を 2 次元平面にプロットする

概要

区間 $\lbrack l , r )$ を $l, r$ のそれぞれを軸とする $2$ 次元平面にプロットするという方法を紹介します。

図

f:id:noshi91:20210505141442j:plain:w500

まず、 $1$ つの区間を置いた図がこれです。赤い点がプロットされた区間であり、斜めの対角線を $\lbrack 0 , n )$ と思うと $\lbrace$ で示した部分がその区間に該当します。点線によって領域が $6$ つに分けられており、区間と他の区間との位置関係が $6$ 通りあることがすぐに分かります。別の区間 (青) を置いてみると以下のようになります。

f:id:noshi91:20210505142051j:plain:w500

この場合、青の区間と赤の区間は overlap しており、青が左側にあります。他の領域はそれぞれ包含や非交に対応しています。この図示によって、例えば $2$ つの区間の位置関係を判定したいときにどのような条件式を書けばよいかなどを素早く確実に導出することができます。また、区間が関わる動的計画法などのイメージにも便利です。*1

*1:効果には個人差があります

2021-04-06

Monge 性が関係する問題リスト

アルゴリズム

概要

Monge 性が関係している問題のリストを作ります。 noshi91 は過去問をあまり埋めていないので、貧弱なリストになると思います。もし載っていないものがあったら教えてもらえると嬉しいです (noshi91 に対するネタバレを気にする必要はありません)。

	出題場所	コンテスト名	難易度	問題名
0	IOI	IOI 2016 day2	700	Aliens
1	ICPC	ICPC 2020 Yokohama	900	Solar Car
2	HUPC	HUPC 2020 Day2	600	Partition
3	ICPC	ICPC 2020 Seoul	700	Two Buildings
4	yukicoder	yukicoder contest 228	800	913 木の燃やし方
5	yukicoder	yukicoder Advent Calender Contest 2019	600	952 危険な火薬庫
6	yukicoder	yukicoder contest 193	700	705 ゴミ拾い Hard
7	AtCoder (有志)	技術室奥プログラミングコンテスト#2	700	NPCの家
8	AtCoder	AtCoder COLOCON 2018	600	すぬけそだて――トレーニング――
9	JOI	JOI 2018/2019 春合宿 Day4	800	ケーキの貼り合わせ
10	USACO	USACO 2007 November Gold	600	Telephone Wire
11	KUPC	KUPC 2012	400	刺身
12	ICPC	ICPC WF2014	700	Buffed Buffet
13	IOI	IOI 2013	800	Wombats
14	yukicoder	yukicoder contest 283	1100	ジグザグロボット
15	IOI	IOI 2014 day2	800	Holiday
16	JAG Summer Camp	JAG Summer Camp 2013 Day2	700	TiMe Table
17	JAG Winter Contest	JAG Winter Contest 2009	600	Tree Construction
18	JAG	JAG Practice Contest for ACM-ICPC Asia Regional 2015	700	Optimal Tournament

2021-04-02

yukicoder 1467 Selling Cars Θ((M + N) M + N log (N))

概要

No.1467 Selling Cars - yukicoder の非常に雑な解説

解法

$k$ を固定して最小費用流にエンコードすると以下のようになります。頂点の数値は湧き出しの量です。

f:id:noshi91:20210402231219j:plain

実際には適切に座標圧縮します。これは series-parallel graph なので最小費用流が効率的に計算できます。

tokoharupage/advent2019.pdf at master · tokoharu/tokoharupage · GitHub

この時点で $\mathrm{O} (M (M + N) \log (M + N))$ にはなりますが、log を落とすことができます。

区分線形凸関数に対して必要な操作をグラフに対する操作で雑に表現すると以下の 3 つです。

$c \lvert x \rvert$ の加算
$x$ 負の方向に 1 ずらす
最小値から $x$ 正の方向に長さ $k$ の $x$ 軸に平行な線分を差し込む

最小値を取る $x$ が常に非正なので、関数を $\lbrack \mathrm{argmin}, 0 \rbrack$ と $\lbrack 0, \infty )$ に分けて、線分の列として管理します。 $\lbrack \mathrm{argmin}, 0 \rbrack$ の折れ線の本数をポテンシャルにすると償却できて、線形です。

2021-04-01

競プロ C++ 部分集合走査ライブラリ

概要

for (auto t: subsets(s)) で s (の bit 列を集合と解釈したとき) の部分集合を走査できるようなライブラリを書きました。単純には std::vector<int> を返せばいいのですが、速度が少し気になるので、それを解決します。部分集合に限らず、多次元ループなども同様の方法で効率的に記述できると思います。

範囲 for ループの制限緩和 - cpprefjp C++日本語リファレンス

実装

#include <cstdint>
#include <variant>

struct subsets {
  using u64 = std::uint64_t;

  u64 s;

  subsets(u64 s_) : s(s_) {}

  struct itr {
    u64 s;
    u64 t;

    bool operator!=(std::monostate) { return t != -1; }
    void operator++() { t -= 1; }
    u64 operator*() { return t &= s; }
  };

  itr begin() { return {s, s}; }
  std::monostate end() { return {}; }
};

注意

s 自身や 0 も走査されます。dp で使いたいときはこれらを含まないようにした方が良いかもしれません。
s = -1 のとき壊れます。
u64 を返しているので、必要なら適宜 int などに変えてください。
std::monostate は何でもいい (int でも char でも) ので、変えても良いです。C++14 だと begin と end で同じ型が返る必要があるので、itr({0,0}) とかにすると良いと思います。

2021-03-23

クエリが整数の Convex Hull Trick の凸判定

アルゴリズムデータ構造

概要

Convex Hull Trick で最小値取得クエリの $x$ が整数の時、アルゴリズム内で直線が不要かどうかチェックする部分を簡単に記述することが出来る。特に、傾きと切片を掛けることでオーバーフローする問題を発生させない。

本文

Convex Hull Trick で、最小値取得クエリの $x$ の値の全てが整数とします。簡単な下処理により、直線の傾きは distinct と仮定してよいです。 $3$ 本の直線 $\lbrace \text{line}\ i = a _ i x + b _ i \ | \ i = 0, 1, 2 \rbrace$ があり、 $a _ 0 > a _ 1 > a _ 2$ とします。ここで、 $a _ 1 x + b _ 1$ が不要かどうか判定することを考えます。 $3$ 本の直線が下図のような位置関係にあるとしましょう。座標軸の目盛りは整数の座標を表しています。

f:id:noshi91:20210323190912j:plain

Convex Hull の字面に従うならば、 $\text{line} \ 1$ は最小値を取り得る、すなわち必要な直線です。しかし、クエリが整数しかないという仮定の下、 $\text{line} 1$ は最小値を取り得ません。この条件を正確に記述します。

\begin{align} f(ax+b, cx+d) := \max \lbrace k \ | \ ak+b \leq ck+d \rbrace \end{align}

と定義すれば、

\begin{align} \text{line}\ 1 \text{が最小値を取り得る} \Leftrightarrow f(\text{line}\ 0, \text{line}\ 1) < f(\text{line}\ 1, \text{line}\ 2) \end{align}

です。ただし、 $2$ 直線が交わる $x$ 座標では傾きの大きい方が最小値を取るとしています。

ところで $a > c$ の仮定の下

\begin{align} f(ax+b, cx+d) :&= \max \lbrace k \ | \ ak+b \leq ck+d \rbrace \\ &= \left \lfloor \frac {d - b} {a - c} \right \rfloor \end{align}

であるため、 $f$ は整数除算で計算することが出来ます。これにより、分母を払って判定するアルゴリズムにおけるオーバーフローの問題が発生しなくなります。また、この条件はクエリが実数の場合の条件より強い条件なので、残された直線群の凸性が保たれ、最小値取得クエリのアルゴリズムは普通の物を使うことが出来ます。

2021-02-08

{x | b^x = a (mod m)} の構造

概要

$a, b, m$ が与えられて $\lbrace x \mid b^x \equiv a \pmod m \rbrace$ の構造を観察します。

結論

$S := \lbrace x \mid b^x \equiv a \pmod m \rbrace$ について、次のうちいずれかが成り立ちます。

$S = \emptyset$
$\exists\ 0 \le c \lt \log_2(m),\ S = \lbrace c \rbrace$
$\exists\ n \mid \lambda(m),\ \exists\ t,\ S = \lbrace x \mid x \equiv t \pmod n \rbrace$
$\exists\ 0 \le c \lt \log_2(m),\ \exists\ n \mid \lambda(m),\ \exists\ t,\ S = \lbrace x \mid x \gt c \land x \equiv t \pmod n \rbrace$

証明

$m = \prod_{i=1}^{k} p_i ^ {e_i}$ とすると、中国剰余定理から $\mathbb{Z} / m\mathbb{Z} \simeq \prod_{i=1}^{k} \mathbb{Z} / p_i ^ {e_i} \mathbb{Z}$ 。 $i$ を 1 つ固定して考えると、

$p \mid b, a \neq 0 \pmod {p^e}$ のとき、 $x$ は存在しないか、一意に定まる。
$p \mid b, a = 0 \pmod {p^e}$ のとき、 $x \gt c$ の形の条件が付く。
$p \nmid b$ のとき、 $x$ は存在しないか、 $x = t \pmod {n}$ の形の条件が付く (ただし $n \mid \lambda(p^e)$ )。