アルゴリズムと計算量の問題

文字列 $X$ に次の $3$ 種類の操作をくり返し行って、文字列 $Y$ に変換することを考える。

• 挿入: 任意の位置に $1$ 文字を挿入する。コストは $1$
• 削除: $1$ 文字を削除する。コストは $1$
• 置換: $1$ 文字を別の $1$ 文字に置き換える。コストは $3$

操作のコストの合計の最小値を、$X$ から $Y$ への重み付き編集距離という。
$$X=\mathtt{CATGACT},Y=\mathtt{ACGTCAGT}$$
のとき、$X$ から $Y$ への重み付き編集距離を求めよ。

$n$ を正の整数とし、$i=1,\dots ,n$ に対して実数 $l_i\le r_i$ と閉区間 $I_i=[l_i,r_i]$ が与えられている（区間の長さ $r_i-l_i$ は区間ごとに異なってよい）。実数の有限集合 $S$ が、すべての $i$ について $S\cap I_i\ne \varnothing$ を満たすとき、$S$ を「刺し集合」と呼ぶ。刺し集合の要素の個数の最小値を $\mathrm{OPT}$ とする。

次の貪欲アルゴリズムを考える。
- $U=\{1,2,\dots ,n\}$, $S=\varnothing$, $k=0$ とする。
- $U\ne \varnothing$ である間、次を繰り返す：$k$ を $1$ 増やし、$U$ の中で $r_i$ が最小となる添字 $i$ を 1 つ選んで $j_k$ とし（最小となる添字が複数あるときはそのうち最小の添字とする）、$p_k=r_{j_k}$ として $S$ に $p_k$ を加え、$U$ から $l_i\le p_k\le r_i$ を満たす添字 $i$ をすべて取り除く。
- $U=\varnothing$ となったときの $k$ の値を $g$ として、$S=\{p_1,\dots ,p_g\}$ を出力する。

このアルゴリズムは必ず停止し、出力 $S$ は刺し集合であり、$S$ の要素の個数は $g$ で、$g=\mathrm{OPT}$ が成り立つことを証明せよ。

$n$ を正の整数とする。文字列 $s$ からいくつかの文字を取り除き（$0$ 個でもよい）、残りの文字を順序を変えずに並べた文字列を $s$ の部分列という。$2$ つの文字列の両方の部分列であるものを共通部分列といい、共通部分列のうち長さが最大のものを最長共通部分列という。

文字 $\mathrm{a},\mathrm{b},\mathrm{c}$ からなる次の $2$ つの文字列を考える。
$$X=\underset{\mathrm{abc}\text{を}n\text{回}}{\underbrace{\mathrm{abc}\mathrm{abc}\cdots \mathrm{abc}}},Y=\underset{n\text{個}}{\underbrace{\mathrm{c}\cdots \mathrm{c}}}\underset{n\text{個}}{\underbrace{\mathrm{b}\cdots \mathrm{b}}}\underset{n\text{個}}{\underbrace{\mathrm{a}\cdots \mathrm{a}}}$$
（$X$, $Y$ の長さはどちらも $3n$）

$X$ と $Y$ の最長共通部分列は、文字列として何通りあるか。$n$ の式で表せ（異なる位置から取り出しても同じ文字列になるものは $1$ 通りと数える）。

互いに異なる $6$ 個の実数を並べた配列 $A[1],A[2],\dots ,A[6]$ から、最大値と最小値の両方を次のアルゴリズムで求める。

• 最初に $mx=A[1]$、$mn=A[1]$ とする。
• $i=2,3,\dots ,6$ の順に、次の操作を行う。
• まず $A[i]$ と $mx$ を比較する。$A[i]>mx$ であれば $mx=A[i]$ とし、この $i$ についての操作を終える。
• そうでなければ、$A[i]$ と $mn$ を比較し、$A[i]<mn$ であれば $mn=A[i]$ とする。

$6$ 個の数の並び方は $6!$ 通りすべてが等確率 $\frac{1}{6!}$ で起こるとする。このアルゴリズムで行われる要素どうしの比較の回数の期待値を求めよ。

$p$ を素数、$r$ を正の整数とし、${\mathbb{F}}_p=\{0,1,\dots ,p-1\}$ を $p$ を法とする剰余体とする。キーの集合を $U={\mathbb{F}}_p^r$ とし、$\mathbf{a}=(a_1,\dots ,a_r)\in {\mathbb{F}}_p^r$ に対してハッシュ関数 $h_{\mathbf{a}}:U\to {\mathbb{F}}_p$ を
$$h_{\mathbf{a}}(\mathbf{x})=a_1{x}_1+a_2{x}_2+\cdots +a_r{x}_r({\mathbb{F}}_p\text{での計算})$$
で定める。ただし $\mathbf{x}=(x_1,\dots ,x_r)$ である。

$n$ 個の相異なるキーからなる集合 $S\subseteq U$ を固定し、$\mathbf{a}$ を ${\mathbb{F}}_p^r$ の $p^r$ 個の元から一様ランダムに選ぶ。各 $j\in {\mathbb{F}}_p$ について、バケット $j$ に入るキーの個数を
$$N_j=\left|\{\mathbf{x}\in S:h_{\mathbf{a}}(\mathbf{x})=j\}\right|$$
とおく。このとき
$$E\left[\sum _{j\in {\mathbb{F}}_p}{N}_j^2\right]=n+\frac{n(n-1)}{p}$$
が成り立つことを証明せよ。