問題紹介 - 186 @ hatenablog

2004年くらいから毎年STOC, FOCS, SODAに名前を連ねるMihai Pătraşcuというすごい博士課程の学生が居る. Pătraşcuは加法的組み合わせ論をCSの方に上手く使っているらしい.
WebDiarios de Motocicleta: Bijective Combinatoricsに例とその問題があるので読んで解いてみた.
例2のデコードは分かったが, エンコードで諦めた. 誰かお願い.

以下, 問題.

ウォーミングアップ

俺が知っている問題から一つ. 暗号に使われるので知っている.
長さnのビット列の中でも1の個数がちょうどmのものを考える. $S(n,m)=\{x \in \{0,1\}^n | \sum_i x_i = m\}$ とする.
するとS(n,m)の要素数は $\left(\begin{array}{c}&n\\&m\end{array}\right)$ である.

問題:

以下の二つのプログラムを与えよ.

encode
- 入力: $x \in S(n,m)$
- 出力: $i \in \{1,...,\left(\begin{array}{c}&n\\&m\end{array}\right)\}$
decode
- 入力: $i \in \{1,...,\left(\begin{array}{c}&n\\&m\end{array}\right)\}$
- 出力: $x \in S(n,m)$

実装して分かったが問題を持ってきた論文に載っているアルゴリズムは間違ってる(;´Д｀)

問題1: Prüffer codes. (WebDiarios de Motocicleta: Bijective Combinatorics)

以下, nノードで各ノードに1-nまでの数字がラベル付されている木を考える. (ここで, 1-2-3と1-3-2は違う木. しかし1-2-3と3-2-1は同じ木.)
この木を配列A[1..n-2]に以下のように符号化する.

/* encode */
for i=1 to n-2:
 L = min {label(v) | v is a leaf}
 A[i] = label(unique neighbor of node labeled L)
 remove the node labeled L from the tree

問題.

以下のアルゴリズムを与えよ.

decode
- 入力: 配列A[1..n-2] (ただし各要素は1-nの整数)
- 出力: encode(T)=A[1..n-2]となる木T

ボーナス点: アルゴリズムの動作時間がO(n)であることを示す.
情報オリンピックで出た問題だそうで.

問題2: Balanced parentheses (WebDiarios de Motocicleta: Bijective Combinatorics)

n個の開き括弧と閉じ括弧が正しく対応している文字列を考える.
n=2のときは,

()()
(())

の二つである.
そのような文字列の数はカタラン数 $\mathrm{Cat}_n=\left(\begin{array}{c}&2n\\&n\end{array}\right)/(n+1)$ になる.
以下, $S_n$ をn個の開き括弧と閉じ括弧が正しく対応している文字列全体の集合とする.

問題

以下のアルゴリズムを与えよ

encode
- 入力: 集合S (集合{1,...,2n}の部分集合で要素数がn)
- 出力: $x \in S_n$ と $k \in \{0,...,n\}$ のペア
decode
- 入力: $x \in S_n$ と $k \in \{0,...,n\}$ のペア
- 出力: 集合S (集合{1,...,2n}の部分集合で要素数がn)