カタラン数を鏡像法で理解する

概要

この記事の内容は [1] の解説の一部を抜き出して説明したものです。カタラン数 $C(N)$ が $\displaystyle \binom{2N}{N} - \binom{2N}{N - 1}$ と等しいことを、鏡像法 *1 で説明します。

本文

$C(N)$ は、グリッド上を右上方向に、 $(0, 0)$ から $(N, N)$ まで、 $x \geq y$ を満たすように移動する方法の数と一致します。

f:id:noshi91:20210710163922j:plain

$x \geq y$ の条件を一旦忘れて、 $(0, 0)$ から $(N, N)$ までの経路の本数を数えることを考えます。これは以下のような動的計画法で計算できます。

\begin{align} \mathrm{dp}(i, j) = \begin{cases} 1 &\quad ( (i, j) = (0, 0) ) \cr \mathrm{dp}(i - 1, j) + \mathrm{dp}(i, j - 1) &\quad (\mathrm{otherwise}) \end{cases} \end{align}

f:id:noshi91:20210710164327j:plain

$x \geq y$ を、 $x + 1 = y$ を通らない、と言い換えます。するとカタラン数は、先ほどの例において $x + 1 = y$ 上で $\mathrm{dp} = 0$ にするような動的計画法で計算できます。

\begin{align} \mathrm{dp}(i, j) = \begin{cases} 1 &\quad ( (i, j) = (0, 0) ) \cr 0 &\quad ( i + 1 = j ) \cr \mathrm{dp}(i - 1, j) + \mathrm{dp}(i, j - 1) &\quad (\mathrm{otherwise}) \end{cases} \end{align}

f:id:noshi91:20210710164812j:plain

この $x + 1 = y$ 上で $\mathrm{dp} = 0$ にする操作を陽に行わずに表現する方法として、 $x + 1 = y$ に対して $(0, 0)$ と対称な位置に $-1$ の重みをもつスタート地点を置くという方法があります。

\begin{align} \mathrm{dp}(i, j) = \begin{cases} 1 &\quad ( (i, j) = (0, 0) ) \cr -1 &\quad ( (i, j) = (-1, 1) ) \cr \mathrm{dp}(i - 1, j) + \mathrm{dp}(i, j - 1) &\quad (\mathrm{otherwise}) \end{cases} \end{align}

f:id:noshi91:20210710170014j:plain

対称性から、対称軸上では $\mathrm{dp} = 0$ となることが分かるので、普通の経路数の動的計画法の更新式で、上手くカタラン数が求まっています。一方で $(0, 0)$ を始点とする経路の数と $(-1, 1)$ を始点とする経路の数は独立ですから、単に足し合わせれば

\begin{align} \text{カタラン数} &= \lbrace (0, 0) \text{から} (N, N) \text{への経路の数} \rbrace + (-1) \cdot \lbrace (-1, 1) \text{から} (N, N) \text{への経路の数} \rbrace \cr C(N) &= \binom{2N}{N} - \binom{2N}{N-1} \end{align}

が従います。

参考文献

[1]
ネタバレ注意
yukicoder 1241 Eternal Tours

*1:鏡像法は物理学の用語のようですが、発想が非常に似ているので、名前を借りています。

2021-06-29

最小カット問題の k 値への一般化

アルゴリズム

概要

最小カットを用いると、 $\alpha \in \mathbb{R},\ \theta _ i : \lbrace 0, 1 \rbrace \to \mathbb{R}$ 及び劣モジュラな $\phi _ {i, j} : \lbrace 0, 1 \rbrace ^ 2 \to \mathbb{R}$ について

\begin{align} \text{Minimize}&\quad \alpha + \sum _ i \theta _ i (x _ i) + \sum _ {i \lt j} \phi _ {i, j}(x _ i, x _ j) \cr \text{subject to}&\quad x \in \lbrace 0, 1 \rbrace ^ n \end{align}

という問題が解けます。[2]

これを一般化して、 $\alpha \in \mathbb{R},\ \theta _ i : k \to \mathbb{R}$ 及び Monge な $\phi _ {i, j} : k ^ 2 \to \mathbb{R}$ について

\begin{align} \text{Minimize}&\quad \alpha + \sum _ i \theta _ i (x _ i) + \sum _ {i \lt j} \phi _ {i, j}(x _ i, x _ j) \cr \text{subject to}&\quad x \in k ^ n \end{align}

は最小カットを用いて解けます。

本記事は [1] の内容を定式化し、表現可能な条件を明示的に記述します。

グラフの作り方

各変数 $x _ i$ に対して、 $\lbrace 0, 1 \rbrace$ の値を取る $k - 1$ 個の変数 $\lbrace x _ i ^ d \rbrace _ {d = 1} ^ {k - 1}$ を作ります。さらに、 $x _ i ^ d = 1 \land x _ i ^ {d + 1} = 0$ の場合 $+ \infty$ のコストが掛かることにします。これにより $\lbrace x _ i ^ d \rbrace _ {d = 1} ^ {k - 1}$ は丁度 $k$ 種類の状態を取るようになり、 $x _ i ^ d = 1 \leftrightarrow x _ i \lt d$ と対応させられます。

$\theta _ i : k \to \mathbb{R}$ が表現可能なことを示します。 $x _ i ^ d$ に対する $1$ 変数関数は常に表現可能であったことを思い出し、 $x _ i ^ d = 1$ のとき $\theta _ i (d - 1) - \theta _ i (d)$ のコストを掛けます。さらに無条件で $\theta _ i (k - 1)$ のコストを掛けると、 $\theta _ i$ が表現されます。

下図は上述の方法で表現した後、さらにグラフでの表現に直したものです。

f:id:noshi91:20210629043614j:plain

$\phi _ {i, j} : k ^ 2 \to \mathbb{R}$ が Monge ならば表現可能なことを示します。 $\alpha$ と $\theta _ i, \theta _ j$ を使うことで、 $\phi _ {i, j} (0, d) = \phi _ {i, j} (d, 0) = 0 \ (\forall \ d)$ としてよいです。 $x _ i ^ d = x _ j ^ e = 0$ のとき $\phi _ {i, j} (d, e) - \phi _ {i, j} (d, e - 1) - \phi _ {i, j} (d - 1, e) + \phi _ {i, j} (d - 1, e - 1)$ のコストを掛けます。 $\phi _ {i, j}$ の Monge 性から、このコストは劣モジュラです。

yukicoder No.119 旅行ツアーの問題

この節は [3] の内容を前節の内容を通して捉え直します。

各国 $i$ について $0:$ 国に行かない, $1:$ 国には行くがツアーに行かない, $2:$ ツアーに行く, の $3$ つの選択肢を選ぶ問題であり、 $k = 3$ とした場合の前節の問題の枠組みで解釈できます。 $B _ i, C _ i$ に関係する部分は $1$ 変数関数になるため、常に表現可能です ( $B _ i, C _ i$ が負であっても)。 $2$ 変数が関係する部分は、「国 $i$ のツアーに行き国 $j$ に行くならば、国 $j$ のツアーに行かなければならない」です。これを図示すると以下のようなコストになります。

f:id:noshi91:20210629043658j:plain

このままでは Monge でないので、 $0, 1, 2$ を $1, 0, 2$ の順に並び替えます。すると以下のようになります。

f:id:noshi91:20210629043940j:plain

これは Monge なので、最小カットで解くことができます。 $k = 2$ の場合 $0, 1$ を全ての変数で一斉に入れ替えても劣モジュラ性は変化しませんでしたが、 $k \geq 3$ の場合は Monge 性に影響を与えるということになります。

問題例

	出題場所	コンテスト名	問題名
0	KUPC	KUPC2019	123パズル
1	ARC	ARC 107	Sum of Abs

その他

グラフの作り方から明らかなように、 $k$ の値は変数ごとに異なっても構いません。

参考文献

[1] tokoharu-sakura. (2017). Project Selection (燃やす埋める) 周りの話についてもう少し考えた. とこはるのまとめ. https://tokoharuland.hateblo.jp/entry/2017/12/25/000003
[2] つる. (2020). 燃やす埋める問題と劣モジュラ関数のグラフ表現可能性その①. 私と理論. https://theory-and-me.hatenablog.com/entry/2020/03/13/180935
[3] ねぼこ. (2021). yukicoder No.119 旅行のツアーの問題解説. neboccoのブログ. https://nebocco.hatenablog.com/entry/2021/03/18/200000

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}) とかにすると良いと思います。

noshi91のメモ

データ構造のある風景

カタラン数を鏡像法で理解する

概要

本文

参考文献

最小カット問題の k 値への一般化

概要

グラフの作り方

yukicoder No.119 旅行ツアーの問題

問題例

その他

参考文献

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

概要

出来ること

アルゴリズム

実装例

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

概要

図

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

概要

リスト

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

概要

解法

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

概要

実装

注意