noshi91のメモ

データ構造のある風景

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

概要

この記事の内容は [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:鏡像法は物理学の用語のようですが、発想が非常に似ているので、名前を借りています。

最小カット問題の 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 の値は変数ごとに異なっても構いません。

参考文献

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

概要

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

出来ること

  •  \mathtt { new } ( A )
    •  A を非負整数の  2 つ組の列として、データ構造を構築する。
    • 時間計算量  \Theta ( \lvert A \rvert ( \log ( \sigma ) ) ^ 2 )
    • 空間計算量  \Theta ( \lvert A \rvert ( \log ( \sigma ) ) ^ 2 / w )
    •  \sigma は各成分の最大値
  •  \mathtt { count } ( l , r , d , u , s , t )
    •  A \lbrack l , r ) で第  0 成分が  \lbrack d , u ) かつ第  1 成分が  \lbrack s , t ) のものの個数を出力する。
    • 時間計算量  \Theta ( ( \log ( \sigma ) ) ^ 2 )
  •  \mathtt { quantile } ( l , r , d , u , k )
    •  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 したものです。

区間を 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:効果には個人差があります

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

概要

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

リスト

ネタバレ防止のため、その問題の属性を部分的に確認できるようにしました。 クリックすると表示されます。 追加して欲しい属性がある場合も noshi91 に提案してください。

難易度は noshi91 の体感で、AtCoder の得点換算です。 Monge 性に関するアルゴリズムは知っているものとします。

出題場所 コンテスト名 難易度 問題名
0
IOI
IOI 2016 day2
700
Aliens
1
ICPC 2020 Yokohama
900
Solar Car
2
HUPC
HUPC 2020 Day2
600
Partition
3
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 (有志)
700
NPCの家
8
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 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

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 の折れ線の本数をポテンシャルにすると償却できて、線形です。

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