アルゴリズムと計算量

ある分割統治アルゴリズムは、大きさ $n$ の入力を大きさ $n/2$ の $2$ つの部分問題に分けて再帰的に解き、分割と統合に $n$ の手間をかける。その計算時間 $T(n)$ は、$0$ 以上の整数 $k$ に対して $n=2^k$ のとき、次の漸化式で与えられる。
$$T(1)=1,T(n)=2T\left(\frac{n}{2}\right)+n(n\geqq 2)$$
$T(2^k)$ を $k$ の式で表せ。

ある分割統治アルゴリズム（マージソートの型）は、大きさ $n$ の入力を大きさ $n/2$ の $2$ つの部分問題に分けて再帰的に解き、分割と統合に $n$ の手間をかける。その計算時間 $T(n)$ は、$0$ 以上の整数 $k$ に対して $n=2^k$ のとき、次の漸化式で与えられる。
$$T(1)=1,T(n)=2T\left(\frac{n}{2}\right)+n(n\geqq 2)$$
$T(2^k)$ を $k$ の式で求めよ。

ある分割統治アルゴリズムは、大きさ $n$ の入力を大きさ $n/2$ の $2$ つの部分問題に分けて再帰的に解き、分割と統合に $2n$ の手間をかける。その計算時間 $T(n)$ は、$0$ 以上の整数 $k$ に対して $n=2^k$ のとき、次の漸化式で与えられる。
$$T(1)=3,T(n)=2T\left(\frac{n}{2}\right)+2n(n\geqq 2)$$
$T(2^k)$ を $k$ の式で求めよ。

互いに異なる $5$ 個の実数 $a_1,a_2,a_3,a_4,a_5$ を昇順に並べかえる。使える操作は「$2$ つの要素を比べて、どちらが小さいかを知る」比較だけとし、$1$ 回の比較の結果は $2$ 通りであるとする。このような比較にもとづくソートの手順を決定木で表すと、葉はそれぞれ $1$ つの並べ方（順列）に対応し、すべての並べ方が葉として現れる必要がある。この考え方から得られる「最悪の場合の比較回数の下界」$\lceil {\log }_{2}5!\rceil$ の値を求めよ。

互いに異なる $5$ 個の実数 $a_1,a_2,a_3,a_4,a_5$ を、比較ソートで昇順に並べかえる。比較ソートとは、$2$ つの要素の大小を比べる操作（結果は「$<$」か「$>$」の $2$ 通り）だけを用いて並べ方を決めるアルゴリズムのことである。

どの比較ソートも、最悪の場合には少なくとも $\lceil {\log }_{2}5!\rceil$ 回の比較を行う。これは決定木の考え方から得られる下界である。この下界 $\lceil {\log }_{2}5!\rceil$ の値を求めよ。ただし、$\lceil x\rceil$ は $x$ 以上の最小の整数を表す。

互いに異なる $6$ 個の実数 $a_1,a_2,\dots ,a_6$ を、比較だけを使って昇順に並べかえる。$1$ 回の比較では、ある $2$ 個 $a_i,a_j$ について「$a_i<a_j$ か」を調べ、「はい」か「いいえ」の答えを得る。どのような比較ソートのアルゴリズムでも、最悪の場合の比較回数は決定木による下界 $\lceil {\log }_{2}6!\rceil$ 以上になる。この下界 $\lceil {\log }_{2}6!\rceil$ の値を求めよ。ただし、$\lceil x\rceil$ は $x$ 以上の最小の整数を表す。

$1,2,3,4,5,6$ を $1$ 列に並べる $6!$ 通りの並べ方から $1$ つを等確率で選び、それを配列 $A[1],A[2],\dots ,A[6]$ とする。$1\le i<j\le 6$ を満たす整数の組 $(i,j)$ で $A[i]>A[j]$ となるものを「転倒」とよぶ（転倒の個数は、挿入ソートで隣り合う要素を交換する回数に等しいことが知られている）。配列 $A$ に含まれる転倒の個数を $X$ とするとき、期待値 $E[X]$ を求めよ。

互いに異なる $6$ 個の実数を、$6!$ 通りの並べ方のどれもが等確率 $\frac{1}{720}$ で起こるように並べ、配列 $A[1],A[2],\dots ,A[6]$ を作る。$1\leqq i<j\leqq 6$ を満たす整数の組 $(i,j)$ のうち、$A[i]>A[j]$ となるものを転倒といい、転倒の個数を $X$ とする（$X$ は、この配列を挿入ソートで昇順に並べかえるときに行われる隣り合う要素の交換の回数に等しい）。$X$ の期待値 $E(X)$ を求めよ。

長さ $12$ のビット列 $b_1{b}_2\cdots b_{12}$ を、各ビット $b_j$ $(j=1,2,\dots ,12)$ が互いに独立に確率 $\frac{1}{2}$ ずつで $0$ または $1$ になるようにランダムに作る。このビット列の中でパターン $101$ が現れる回数 $X$ を
$$X=(b_i{b}_{i+1}{b}_{i+2}=101\text{ となる整数 }i(1\le i\le 10)\text{ の個数})$$
と定める（重なった出現も別々に数える。たとえば $10101$ の中には $101$ が $2$ 回現れる）。$X$ の期待値 $E(X)$ を求めよ。

ある天文台には天体望遠鏡が $1$ 台しかなく、$7$ 件の観測希望（番号 $1$〜$7$）が出ている。観測希望 $k$ は時刻 $s_k$ に始まり時刻 $f_k$ に終わり、半開区間 $[s_k,f_k)$（$s_k$ 以上 $f_k$ 未満）の間、望遠鏡を使う。時刻は整数で表し、ある観測の終了時刻と別の観測の開始時刻が等しい場合は、両方とも行うことができる。

次の貪欲法で、互いに時間が重ならない観測希望を選ぶ。

「観測希望を終了時刻 $f_k$ の早い順に並べ、先頭から順に見ていく。その観測希望の開始時刻が、すでに選んだ観測希望のうち最後に選んだものの終了時刻以上であれば（最初の $1$ 件は無条件に）選び、そうでなければ選ばない。」

この貪欲法によって選ばれる観測希望の番号の集合を求めよ。

ある科学フェスティバルで、$8$ つの体験教室 $1$〜$8$ が開かれる。体験教室 $k$ は時刻 $s_k$ に始まり時刻 $f_k$ に終わり、半開区間 $[s_k,f_k)$ の時間帯を使う（したがって、ある教室の終了時刻と別の教室の開始時刻が等しければ、両方に参加できる）。

ある参加者は、時間帯が重なる $2$ つの教室には同時に参加できない。この参加者が次の貪欲法で参加する教室を選ぶ。

「教室を終了時刻の早い順に並べ、先頭から順に見ていく。見ている教室の開始時刻が、直前に選んだ教室の終了時刻以上であれば（最初の教室は無条件に）その教室を選ぶ。そうでなければ選ばない。」

この貪欲法で選ばれる教室の番号の集合を求めよ。

ある人が、テレビ番組を $1$ 台のテレビで $1$ 本ずつ見ることにした。見たい番組が $8$ 本あり、番号 $1$〜$8$ が付いている。番組 $k$ の放送時間は、開始時刻 $s_k$ から終了時刻 $f_k$ の直前までの半開区間 $[s_k,f_k)$ である（時刻の単位は時間）。

番組は最初から最後まで見るものとし、放送時間が重なる $2$ 本を両方見ることはできない（一方の終了時刻ともう一方の開始時刻が等しい場合は、両方見られる）。

次の貪欲法で見る番組を選ぶ。

• 番組を終了時刻 $f_k$ の小さい順に並べる。
• その順に番組を調べ、その番組の開始時刻が、すでに選んだ番組の終了時刻の最大値以上であれば（まだ $1$ 本も選んでいなければ無条件に）その番組を選ぶ。そうでなければ選ばない。

この貪欲法で選ばれる番組の番号の集合を求めよ。

$1$ 円、$3$ 円、$4$ 円の硬貨がそれぞれ十分な枚数あるとする。$0$ 以上の整数 $n$ に対し、$n$ 円をちょうど支払うときに使う硬貨の枚数の最小値を $M(n)$ とする（$M(0)=0$ とする）。$M(n)$ は、$n\ge 1$ のとき漸化式
$$M(n)=\underset{c\in \{1,3,4\},c\le n}{\min }\{M(n-c)+1\}$$
を満たす。この漸化式を用いて $M(10)$ を求めよ。

$1$ 円、$4$ 円、$6$ 円の硬貨がそれぞれ十分な枚数あるとする。$0$ 以上の整数 $n$ に対し、$n$ 円をちょうど支払うときの硬貨の枚数の最小値を $M(n)$ とする（$M(0)=0$ とする）。$M(n)$ は、$n\ge 1$ のとき漸化式
$$M(n)=\underset{c\in \{1,4,6\},c\le n}{\min }\{M(n-c)+1\}$$
を満たす。この漸化式を用いて $M(0),M(1),\dots$ の表を順に埋め、$M(14)$ を求めよ。

$1$ 円、$4$ 円、$5$ 円の硬貨がそれぞれ十分な枚数あるとする。$0$ 以上の整数 $n$ に対し、$n$ 円をちょうど支払うときの硬貨の枚数の最小値を $f(n)$ とする（$f(0)=0$ とする）。$n\ge 1$ のとき、$f(n)$ は次の漸化式を満たす。
$$f(n)=\underset{c\in \{1,4,5\},c\le n}{\min }\{f(n-c)+1\}$$
この漸化式を用いて $f(0),f(1),\dots$ の表を順に埋め、$f(12)$ を求めよ。

$0$ 以上の整数 $k$ に対して $n=5^k$ とする。ある分割統治アルゴリズムの計算時間 $T(n)$ が、次の漸化式で与えられている。
$$T(1)=1,T(n)=25T\left(\frac{n}{5}\right)+n^2(n\geqq 5)$$
マスター定理を用いて $T(n)=\Theta (g(n))$ となる $g(n)$ を求めよ。ただし、答えは $\Theta$ の中身の式（例: $n\log n$）を、定数倍を除いた最も簡単な形で答えよ。対数は自然対数 $\log$ を用いて表すこと。

ある分割統治アルゴリズムは、大きさ $n$ の問題を大きさ $\frac{n}{9}$ の部分問題 $27$ 個に分け、分割と統合に $n\sqrt{n}$ の時間をかける。$0$ 以上の整数 $k$ を用いて $n=9^k$ と表される $n$ に対して、計算時間 $T(n)$ は次の漸化式で与えられる。$$T(1)=1,T(n)=27T\left(\frac{n}{9}\right)+n\sqrt{n}(n\geqq 9)$$$T(n)=\Theta (g(n))$ となる関数 $g(n)$ を求め、$\Theta$ の中身の式 $g(n)$ を $n$ の式で答えよ。ただし、$g(n)$ は係数を $1$ とした最も簡単な形で答え、対数が現れる場合は自然対数 $\log n$ を用いて書くこと。

ある分割統治アルゴリズムは、サイズ $n$ の問題をサイズ $\frac{n}{4}$ の部分問題 $8$ 個に分けて再帰的に解き、分割と結果の統合に $n^{3/2}$ の時間をかける。その計算時間 $T(n)$ は、$n=4^k$（$k$ は $0$ 以上の整数）のとき次の漸化式で与えられる。
$$T(1)=1,T(n)=8T\left(\frac{n}{4}\right)+n^{3/2}(n\geqq 4)$$
マスター定理を用いて $T(n)=\Theta (g(n))$ となる $g(n)$ を求めよ。ただし $g(n)$ は $\Theta$ の中身の式として、係数 $1$ の単項式（例: $n^3$, $n\log n$）で答えること。

互いに異なる $7$ 個の実数を並べた配列 $A[1],A[2],\dots ,A[7]$ を、次のバブルソートで昇順に並べかえる。

$k=1,2,\dots ,6$ の順に、$j=1,2,\dots ,7-k$ の順で $A[j]$ と $A[j+1]$ を比べ、$A[j]>A[j+1]$ ならば $A[j]$ と $A[j+1]$ を交換する。

最初の並びは、$7$ 個の数の $7!$ 通りの並べ方のどれもが同様に確からしいとする。このソートで行われる交換の回数の期待値を求めよ。

$1,2,\dots ,10$ を $1$ 列に並べた配列 $A[1],A[2],\dots ,A[10]$ がある。並び方は $10!$ 通りのどれも同様に確からしいとする。この配列を、次のバブルソートで昇順に並べかえる。

$i=1,2,\dots ,9$ の順に、各 $i$ について $j=1,2,\dots ,10-i$ の順に次の操作を行う：$A[j]>A[j+1]$ ならば $A[j]$ と $A[j+1]$ を入れかえ（交換し）、そうでなければ何もしない。

このバブルソートで行われる交換の回数の期待値を求めよ。

互いに異なる $10$ 個の実数を並べた配列 $A[1],A[2],\dots ,A[10]$ を、次のバブルソートで昇順に並べかえる。

$k=1,2,\dots ,9$ の順に、各 $k$ について $j=1,2,\dots ,10-k$ の順に次の操作を行う：$A[j]>A[j+1]$ ならば $A[j]$ と $A[j+1]$ を交換する。

入力の並びは $10!$ 通りの並べ方が同様に確からしいとする。このとき、ソートが終わるまでに行われる交換の回数の期待値を求めよ。

バケット数 $20$ のチェイン法ハッシュ表に、互いに異なる $6$ 個のキーを挿入する。各キーのハッシュ値は $20$ 個のバケットのどれかに等確率 $\frac{1}{20}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。$6$ 個のキーから選んだ $2$ 個のキーの組（順序は考えない）のうち、$2$ 個が同じバケットに入る組を「衝突する組」と呼ぶ。衝突する組の個数の期待値を求めよ。

バケット数 $3$ のチェイン法ハッシュ表が最初は空である。この表に、互いに異なる $4$ 個のキーを挿入する。各キーのハッシュ値は $3$ 個のバケットのどれかに等確率 $\frac{1}{3}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。$4$ 個のキーをすべて挿入し終えたとき、キーを $2$ 個以上含むバケットの個数の期待値を求めよ。

スロット番号が $0,1,\dots ,10$ の $11$ 個のスロットからなるハッシュ表を、オープンアドレス法（線形探査）で使う。はじめはすべてのスロットが空である。0 以上の整数のキー $k$ を挿入するときは、$i=0,1,2,\dots$ の順にスロット
$$h(k,i)=((k\mathrm{mod}11)+i)\mathrm{mod}11$$
を調べ、最初に見つかった空のスロットに $k$ を格納する。1 回の挿入で調べたスロットの個数（格納先の空のスロットも含める）を、その挿入の「探査回数」と呼ぶ。

キー
$$22,5,16,27,10,38,21,6$$
をこの順に挿入するとき、$8$ 回の挿入の探査回数の合計を求めよ。

互いに異なる $4$ 個の数が入った配列を、次の乱択クイックソートで小さい順に並べる。

• 並べる数が $0$ 個または $1$ 個のときは、何もせずに終わる（比較は行わない）。
• 並べる数が $m$ 個（$m\geqq 2$）のときは、その $m$ 個の中からピボットを $1$ 個、等確率 $\frac{1}{m}$ で選ぶ。ピボットを残りの $m-1$ 個の数とそれぞれ $1$ 回ずつ比較し、ピボットより小さい数の組と大きい数の組に分ける。そのあと、それぞれの組に同じ手順を行う。

ピボットの選択は毎回ほかの選択と独立に行うものとする。数どうしの比較は上の「ピボットと残りの数との比較」だけで行われるとき、$4$ 個の数を並べ終えるまでに行われる比較の回数の期待値を求めよ。

互いに異なる $4$ 個の数が入った配列を、次の乱択クイックソートで小さい順に並べる。

• 並べる対象の数が $0$ 個または $1$ 個のときは、何もせずに終わる（比較は行わない）。
• 対象の数が $m$ 個（$m\ge 2$）のときは、その $m$ 個の中からピボットを $1$ 個、等しい確率 $\frac{1}{m}$ で選ぶ。ピボットを残りの $m-1$ 個のそれぞれと $1$ 回ずつ比較し（比較は $m-1$ 回）、ピボットより小さい数の組と大きい数の組に分ける。それぞれの組に対して、同じ手順を繰り返す。

ピボットの選択はすべて互いに独立に行われるものとする。このとき、$4$ 個の数を並べ終えるまでに行われる比較の回数の期待値を求めよ。

互いに異なる $4$ 個の数が入った配列を、次の乱択クイックソートで小さい順に並べる。

• 並べる対象の個数が $1$ 個以下なら、何もしないで終わる。
• 対象が $m$ 個 $(m\ge 2)$ のときは、その $m$ 個の中からピボットを $1$ 個、等確率 $\frac{1}{m}$ で選ぶ。ピボットを残りの $m-1$ 個のそれぞれと $1$ 回ずつ比較して、ピボットより小さい数の集まりと大きい数の集まりに分ける（比較は $m-1$ 回）。そのあと、2 つの集まりのそれぞれに同じ手順を行う。
• ピボットの選び方は、毎回それまでの選び方と独立とする。比較回数として数えるのは、ピボットとほかの数との比較だけとする。

このアルゴリズムが終わるまでに行う比較回数の期待値を求めよ。

$1$ 円、$4$ 円、$6$ 円の硬貨がそれぞれ十分な枚数あるとする。正の整数 $n$ に対し、$n$ 円をちょうど支払う硬貨の組み合わせのうち、枚数が最小のものの枚数を $M(n)$ とする。

また、次の貪欲法で $n$ 円を支払ったときの硬貨の枚数を $G(n)$ とする。

（貪欲法）残りの金額が $0$ になるまで、残りの金額以下の硬貨のうち最も額面の大きいものを $1$ 枚使う、という操作をくり返す。

$1\le n\le 12$ を満たす整数 $n$ のうち、$G(n)>M(n)$ となる $n$ をすべて求めよ。

$1$ 円、$4$ 円、$5$ 円の硬貨がそれぞれ十分な枚数あるとする。正の整数 $n$ に対し、$n$ 円をちょうど支払う硬貨の組み合わせのうち、枚数が最小のものの枚数を $M(n)$ とする。また、「残りの金額を超えない硬貨のうち最も額の大きいものを $1$ 枚使う」ことを残りが $0$ 円になるまでくり返す貪欲法で $n$ 円を支払ったときの硬貨の枚数を $G(n)$ とする。$1\le n\le 12$ を満たす整数 $n$ のうち、$G(n)>M(n)$ となるものをすべて求めよ。

$1$ 円、$3$ 円、$4$ 円の硬貨がそれぞれ十分な枚数あるとする。正の整数 $n$ に対し、$n$ 円をちょうど支払う硬貨の組み合わせのうち、枚数が最小のものの枚数を $M(n)$ とする。また、「残りの金額を超えない硬貨のうち最も額の大きいものを $1$ 枚使う」ことを残りが $0$ 円になるまでくり返す貪欲法で $n$ 円を支払ったときの枚数を $G(n)$ とする。

$1\le n\le 12$ を満たす整数 $n$ のうち、$G(n)>M(n)$ となるものをすべて求めよ。

次の $4$ 個の品物から、重さの合計が $8$ 以下になるようにいくつか選ぶ。各品物は選ぶか選ばないかのどちらかで、同じ品物を $2$ 個以上選ぶことはできない。

品物を A, B, C, D の順に $1,2,3,4$ 番目とし、$i$ 番目の品物の重さを $w_i$、価値を $v_i$ とする。$V[i][w]$ を「$1$ 番目から $i$ 番目までの品物だけを使い、重さの合計が $w$ 以下になるように選んだときの価値の合計の最大値」とすると、$V[0][w]=0$ であり、$i\geqq 1$ のとき
$$V[i][w]=\{\begin{array}{ll}V[i-1][w]& (w<w_i)\\ \max \left(V[i-1][w],V[i-1][w-w_i]+v_i\right)& (w\geqq w_i)\end{array}$$
が成り立つ。この表を $w=0,1,\dots ,8$ について埋め、選んだ品物の価値の合計の最大値 $V[4][8]$ を求めよ。

次の $4$ 個の品物から、重さの合計が $8$ 以下になるようにいくつかを選びます。各品物は選ぶか選ばないかのどちらかで、同じ品物を $2$ 個以上選ぶことはできません。

品物を A, B, C, D の順に $1,2,3,4$ 番目とし、$i$ 番目の品物の重さを $w_i$、価値を $v_i$ とします。$V[i][w]$ を「$1$ 番目から $i$ 番目までの品物だけを使い、重さの合計が $w$ 以下になるように選んだときの価値の合計の最大値」と定めます（$V[0][w]=0$）。漸化式
$$V[i][w]=\max (V[i-1][w],V[i-1][w-w_i]+v_i)$$
（ただし $w<w_i$ のときは $V[i][w]=V[i-1][w]$）を用いて表を埋め、選んだ品物の価値の合計の最大値 $V[4][8]$ を求めてください。

次の $4$ 個の品物から、重さの合計が $8$ 以下になるようにいくつか選びます。各品物は選ぶか選ばないかのどちらかで、同じ品物を $2$ 個以上選ぶことはできません。

品物を A, B, C, D の順に品物 $1,2,3,4$ とし、品物 $i$ の重さを $w_i$、価値を $v_i$ とします。$V[i][w]$ を「品物 $1$ から $i$ までの中から、重さの合計が $w$ 以下になるように選んだときの価値の合計の最大値」と定めます（$V[0][w]=0$）。

$$V[i][w]=\{\begin{array}{ll}V[i-1][w]& (w<w_i)\\ \max \left(V[i-1][w],V[i-1][w-w_i]+v_i\right)& (w\ge w_i)\end{array}$$

を使って表を埋め、重さの合計が $8$ 以下のときの価値の合計の最大値 $V[4][8]$ を求めてください。

英大文字からなる文字列に対して、次の $3$ 種類の操作を考える。

• 挿入: 好きな位置に $1$ 文字を挿入する（コスト $1$）
• 削除: $1$ 文字を削除する（コスト $2$）
• 置換: $1$ 文字を別の $1$ 文字に置き換える（コスト $2$）

これらの操作をくり返して文字列 $X=\mathrm{TEA}$ を文字列 $Y=\mathrm{EAST}$ に変換するとき、かかるコストの合計の最小値（重み付き編集距離）を求めよ。

文字 $\mathrm{A},\mathrm{C},\mathrm{G},\mathrm{T}$ からなる文字列に対して、次の $3$ 種類の操作を考える。

• 挿入: 好きな位置に $1$ 文字を挿入する（コスト $1$）
• 削除: $1$ 文字を削除する（コスト $2$）
• 置換: $1$ 文字を別の $1$ 文字に置き換える（コスト $3$）

これらの操作をくり返して、文字列 $X=\mathrm{ACG}$ を文字列 $Y=\mathrm{CAG}$ に変換する。かかるコストの合計の最小値（重み付き編集距離）を求めよ。

文字 $\mathrm{A},\mathrm{C},\mathrm{G},\mathrm{T}$ からなる文字列（DNA 配列）に対して、次の $3$ 種類の操作を考える。

• 削除: $1$ 文字を削除する（コスト $1$）
• 挿入: 好きな位置に $1$ 文字を挿入する（コスト $2$）
• 置換: $1$ 文字を別の $1$ 文字に置き換える（コスト $1$）

操作をくり返して文字列 $X$ を文字列 $Y$ に変換するとき、使った操作のコストの合計の最小値を、$X$ から $Y$ への重み付き編集距離という。

$X=\mathrm{ACGA}$、$Y=\mathrm{CAG}$ のとき、$X$ から $Y$ への重み付き編集距離を求めよ。

文字列 $Z$ から $0$ 個以上の文字を取り除き、残った文字を元の順に並べて得られる文字列を $Z$ の部分列という（取り除く文字は連続していなくてよい）。$2$ つの文字列の両方の部分列である文字列を共通部分列といい、共通部分列のうち長さが最大のものを最長共通部分列という。

$2$ つの DNA の塩基配列を表す文字列
$$X=\mathrm{AGCAT},Y=\mathrm{GACTA}$$
を比べる。$X$ の先頭から $i$ 文字目を $x_i$、$Y$ の先頭から $j$ 文字目を $y_j$ とし、$X$ の最初の $i$ 文字と $Y$ の最初の $j$ 文字の最長共通部分列の長さを $L[i][j]$ とする（$0\le i\le 5,0\le j\le 5$）。$L[i][j]$ は $L[0][j]=L[i][0]=0$ と、$i,j\ge 1$ に対する漸化式
$$L[i][j]=\{\begin{array}{ll}L[i-1][j-1]+1& (x_i=y_j)\\ \max (L[i-1][j],L[i][j-1])& (x_i\ne y_j)\end{array}$$
で求められる。この表を埋めて、$X$ と $Y$ の最長共通部分列の長さ $L[5][5]$ を求めよ。

文字列 $Z$ から $0$ 個以上の文字を取り除き、残った文字を元の順に並べて得られる文字列を $Z$ の部分列という（取り除く文字は連続していなくてよい）。$2$ つの文字列の両方の部分列であるものを共通部分列といい、共通部分列のうち長さが最大のものを最長共通部分列という。

$2$ つの DNA 塩基配列を表す文字列
$$X=\mathrm{GATCA},Y=\mathrm{TACGA}$$
の最長共通部分列の長さを求めよ。

文字列 $Z$ から $0$ 個以上の文字を取り除き、残った文字を元の順序のまま並べた文字列を、$Z$ の部分列という。$2$ つの文字列の両方の部分列になっている文字列を共通部分列という。

DNA の塩基配列を表す $2$ つの文字列
$$X=\mathrm{ACGTA},Y=\mathrm{CATGA}$$
について、$X$ の先頭 $i$ 文字と $Y$ の先頭 $j$ 文字の最長共通部分列の長さを $L[i][j]$ とする（$0\le i\le 5,0\le j\le 5$。$L[0][j]=L[i][0]=0$）。$X$ の $i$ 文字目を $x_i$、$Y$ の $j$ 文字目を $y_j$ とすると、$i,j\ge 1$ のとき
$$L[i][j]=\{\begin{array}{ll}L[i-1][j-1]+1& (x_i=y_j)\\ \max (L[i-1][j],L[i][j-1])& (x_i\ne y_j)\end{array}$$
が成り立つ。この漸化式で表を埋めて、$X$ と $Y$ の最長共通部分列の長さ $L[5][5]$ を求めよ。

$n$ を $3$ 以上の整数とし、$n$ の関数として次の $4$ つの計算時間を考える（$\log$ は自然対数）。
$$f_1(n)=n^{100},f_2(n)=2^{\sqrt{n}},f_3(n)=n^{\log n},f_4(n)=(\log n{)}^5$$
これらは、ある並べ方 $f_a,f_b,f_c,f_d$ について
$$f_a=o(f_b),f_b=o(f_c),f_c=o(f_d)(n\to \infty )$$
を満たす。添字の組 $(a,b,c,d)$ を求めよ。ここで $f=o(g)$ は $\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=0$ を表す。

ある分割統治アルゴリズムは、大きさ $n$ の入力を大きさ $n/2$ の 3 つの部分問題に分けて再帰的に解き、分割と統合に $n$ の手間をかける。その計算時間 $T(n)$ は、0 以上の整数 $k$ に対して $n=2^k$ のとき
$$T(1)=1,T(n)=3T\left(\frac{n}{2}\right)+n(n\ge 2)$$
を満たすとする。0 以上の整数 $k$ に対して、$T(2^k)$ を $k$ の式で表せ。

$1$ つの会議室を使いたい $9$ 件の予約に番号 $1$〜$9$ が付いており、それぞれの利用時間は次の半開区間 $[s,f)$（開始時刻 $s$ から終了時刻 $f$ の直前まで）である。

利用時間が重ならない予約をできるだけ多く選ぶために、次の貪欲法を使う（ある予約の終了時刻と別の予約の開始時刻が等しい場合は重ならないとみなす）。

1. 予約を終了時刻 $f$ の小さい順に並べる。
2. 直前に選んだ予約の終了時刻を $t$ とする（最初は $t=-\infty$）。並べた順に予約を 1 つずつ見て、開始時刻 $s$ が $s\ge t$ を満たせばその予約を選び、$t$ をその予約の終了時刻に更新する。満たさなければ選ばない。

この貪欲法によって選ばれる予約の番号の集合を求めよ。

英大文字からなる文字列に対して、次の $3$ 種類の操作を考える。

• 挿入: 好きな位置に $1$ 文字を挿入する
• 削除: $1$ 文字を削除する
• 置換: $1$ 文字を別の $1$ 文字に置き換える

どの操作も $1$ 回につきコスト $1$ とする。文字列 $s$ を文字列 $t$ に変えるのに必要な操作の回数の最小値を、$s$ と $t$ の編集距離という。

文字列 $s=\text{PARADE}$ と $t=\text{DRAPED}$ の編集距離を求めよ。

$1$ つの会議室を使いたい $10$ 個の予約 A〜J がある。予約 X の開始時刻を $s_X$、終了時刻を $f_X$ とし、予約 X は時間帯 $[s_X,f_X)$（$s_X$ 以上 $f_X$ 未満）に会議室を使う。

$2$ つの予約 X, Y は、$f_X\le s_Y$ または $f_Y\le s_X$ のとき、同時に採用できるものとする。次の貪欲法で予約を採用する。

1. 予約を終了時刻 $f_X$ の小さい順に並べる。
2. その順に予約を $1$ つずつ調べ、すでに採用した予約のどれとも同時に採用できるならば採用し、そうでなければ採用しない。

この貪欲法で採用される予約をすべて選び、その記号をアルファベット順に「,」で区切って答えよ（解答例：A, D, G）。

ある分割統治アルゴリズムは、大きさ $n$ の入力を大きさ $n/2$ の $4$ つの部分問題に分けて再帰的に解き、分割と統合に $n^2$ の手間をかける。その計算時間 $T(n)$ は、$0$ 以上の整数 $k$ に対して $n=2^k$ のとき
$$T(1)=2,T(n)=4T\left(\frac{n}{2}\right)+n^2(n\ge 2)$$
を満たす。$n=2^k$（$k$ は $0$ 以上の整数）のときの $T(n)$ を、$n$ の式で表せ。対数を使う場合は ${\log }_{2}n$ を用いてよい。

$6$ 種類の文字 $\mathrm{A},\mathrm{B},\mathrm{C},\mathrm{D},\mathrm{E},\mathrm{F}$ からなる長さ $45$ の文字列があり、各文字の出現回数は次のとおりである。

この文字列を、次の貪欲法（ハフマン符号の構成法）で作った $2$ 進符号で符号化する。

• 各文字を、出現回数を重みとする $1$ 頂点だけの木とする。
• 木が $2$ 本以上ある間、重みが最も小さい木と $2$ 番目に小さい木を取り出し、それらを左右の子とする新しい根を作って $1$ 本の木にまとめる。新しい木の重みは $2$ つの木の重みの和とする（重みが等しい木が複数あるときは、どれを選んでもよい）。
• 最後に残った木で、根から各文字の葉までの道の各辺に、左の子へ進む辺は $0$、右の子へ進む辺は $1$ を割り当て、その道に沿って並べた $0,1$ の列をその文字の符号語とする。

文字列の各文字をその符号語に置き換えて並べたとき、得られる $0,1$ の列の長さ（ビット数）を求めよ。

昇順に並んだ互いに異なる $10$ 個の数の配列 $A[1]<A[2]<\cdots <A[10]$ から、値 $x$ を次の二分探索で探す。ただし、$x$ は $A[1],A[2],\dots ,A[10]$ のどれかと必ず等しいとする。

• はじめに $\mathrm{lo}=1$, $\mathrm{hi}=10$ とする。
• $m=\lfloor \frac{\mathrm{lo}+\mathrm{hi}}{2}\rfloor$ とし、$x$ と $A[m]$ を比較する。この比較は $1$ 回で「$x=A[m]$」「$x<A[m]$」「$x>A[m]$」のどれであるかがわかるものとし、比較 $1$ 回と数える。
• $x=A[m]$ ならば探索を終える。$x<A[m]$ ならば $\mathrm{hi}=m-1$ とし、$x>A[m]$ ならば $\mathrm{lo}=m+1$ として、前の手順に戻る。

$x$ が $A[1],A[2],\dots ,A[10]$ のそれぞれと等しい確率がどれも $\frac{1}{10}$ であるとき、探索を終えるまでの比較回数の期待値を求めよ。

ある会議室を使いたい $9$ 件の予約希望があり、予約 $k$（$k=1,2,\dots ,9$）は時刻 $s_k$ に始まり時刻 $f_k$ に終わる（区間 $[s_k,f_k)$ を使う）。

$2$ つの予約 $i,j$ は、$f_i\leqq s_j$ または $f_j\leqq s_i$ のとき両立する（同時に採用できる）とする。次の貪欲法で、互いに両立する予約を選ぶ。

• 予約を終了時刻 $f_k$ の小さい順に並べる。
• その順に予約を $1$ つずつ調べ、それまでに選んだどの予約とも両立するならば選び、そうでなければ選ばない。

この貪欲法で選ばれる予約の番号 $k$ の集合を求めよ。

$n\times n$ 行列どうしの積を計算するある分割統治アルゴリズムは、$n$ が $2$ 以上の $2$ のべきのとき、各行列を $\frac{n}{2}\times \frac{n}{2}$ の $4$ つのブロックに分け、$\frac{n}{2}\times \frac{n}{2}$ 行列どうしの積を $7$ 回だけ再帰的に計算し、そのほかにブロックどうしの和と差の計算に $\frac{9}{2}{n}^2$ の手間をかける。このアルゴリズムの計算時間 $T(n)$ は、$0$ 以上の整数 $k$ に対して $n=2^k$ のとき
$$T(1)=1,T(n)=7T\left(\frac{n}{2}\right)+\frac{9}{2}{n}^2(n\geqq 2)$$
を満たす。

$T(n)=\Theta (g(n))$ となる関数 $g(n)$ を、係数を含まない $n$ のべきの形で求めよ（答えは $\Theta$ の中身の式 $g(n)$ で答えること）。

相異なる $9$ 個の実数を格納した配列 $A[1],A[2],\dots ,A[9]$ がある。$A$ の要素のうち、小さい方から数えた順位が $3$ 以上 $7$ 以下であるものを「良い要素」とよぶ。良い要素を $1$ つ見つけるために、次の乱択アルゴリズムを使う。

• $1$ 以上 $9$ 以下の整数 $i$ を等確率 $\frac{1}{9}$ で選ぶ。
• $A[i]$ を、それ以外の $8$ 個の要素 $A[j](j\ne i)$ のそれぞれと $1$ 回ずつ比較して、$A[i]$ より小さい要素の個数を数え、$A[i]$ の順位を求める。
• $A[i]$ が良い要素であればアルゴリズムを終了し、そうでなければ最初に戻って $i$ を選び直し、同じことをくり返す。

ここで、各回の $i$ の選び方は互いに独立であり、以前に選んだ位置が再び選ばれることもある。また、各回の比較はその回ごとに改めて $8$ 回行う（以前の比較結果は使わない）。アルゴリズムが終了するまでに行う要素どうしの比較の回数の期待値を求めよ。

正の整数 $n$ に対して
$$S(n)=\sum _{k=1}^{n}k\log k$$
とおく（$\log$ は自然対数）。ここで、正の整数上で定義された非負の値をとる関数 $f,g$ について $f(n)=\Theta (g(n))$ とは、正の定数 $c_1,c_2$ と正の整数 $n_0$ が存在して、$n\ge n_0$ を満たすすべての整数 $n$ に対して $c_{1}g(n)\le f(n)\le c_{2}g(n)$ が成り立つことと定める。

このとき、$S(n)=\Theta (n^2\log n)$ であることを証明せよ。

$1$ 台の機械で $6$ 個の仕事 $\mathrm{A},\mathrm{B},\mathrm{C},\mathrm{D},\mathrm{E},\mathrm{F}$ をすべて処理する。仕事 $X$ には処理時間 $p_X$ と重み $w_X$ が次のように定まっている。

機械は時刻 $0$ から使うことができ、どの仕事も時刻 $0$ の時点ですでにそろっていて、いつでも処理を始められる（仕事ごとの到着時刻や締め切りの制約はない）。機械は同時に $1$ つの仕事しか処理できない。また、仕事を途中で中断することはできない（仕事 $X$ を始めたら、$p_X$ だけ時間がたって終わるまで処理を続ける）。仕事 $X$ の処理が終わる時刻を $C_X$ とする。

仕事を処理する順序（および開始時刻）をうまく選んで
$$S=\sum _X{w}_X{C}_X=w_{\mathrm{A}}{C}_{\mathrm{A}}+w_{\mathrm{B}}{C}_{\mathrm{B}}+\cdots +w_{\mathrm{F}}{C}_{\mathrm{F}}$$
をできるだけ小さくしたい。$S$ の最小値を求めよ。

英大文字からなる文字列に対して、次の $3$ 種類の操作を考える。

• 挿入: 好きな位置に $1$ 文字を挿入する（コスト $2$）
• 削除: $1$ 文字を削除する（コスト $2$）
• 置換: $1$ 文字を別の $1$ 文字に置き換える（コスト $3$）

操作を何回か行って文字列 $X$ を文字列 $Y$ に変えるとき、使った操作のコストの合計の最小値を $d(X,Y)$ と書く。

$$X=\mathrm{BRIDGE},Y=\mathrm{BADGER}$$

のとき、$d(X,Y)$ を求めよ。

ある分割統治アルゴリズムは、大きさ $n$ の入力を大きさ $n/4$ の $2$ つの部分問題に分けて再帰的に解く。分割と統合には $\sqrt{n}$ の手間をかける。入力の大きさは $4$ のべき $n=4^k$（$k$ は $0$ 以上の整数）に限るものとし、計算時間 $T(n)$ は次の漸化式で定まるとする。
$$T(1)=1,T(n)=2T\left(\frac{n}{4}\right)+\sqrt{n}(n=4^k,k\ge 1)$$
$n=4^k$ のときの $T(n)$ を $n$ の式で表せ。対数を使う場合は、底を明示するか自然対数 $\log$ を用いて表すこと。

互いに異なる $6$ 個の数を並べた配列 $A[1],A[2],\dots ,A[6]$ を、次の挿入ソートで昇順に並べかえる。

$i=2,3,\dots ,6$ の順に、次の操作を行う。$x=A[i]$ とし、$j=i-1$ から始めて、$j\geqq 1$ である間「$A[j]$ と $x$ を比較し、$A[j]>x$ ならば $A[j]$ を $A[j+1]$ に移して $j$ を $1$ 減らす。$A[j]<x$ ならばそこで止める」をくり返す。止まったとき（または $j=0$ になったとき）、$A[j+1]=x$ とする。

ここで、数どうしの比較（$A[j]$ と $x$ の比較）だけを数え、$j\geqq 1$ かどうかの判定は数えない。最初の配列が $6$ 個の数の $6!$ 通りの並べ方のどれであるかが同様に確からしいとき、比較回数の期待値を求めよ。

バケット数 $4$ のチェイン法ハッシュ表に、互いに異なる $5$ 個のキーを挿入する。各キーのハッシュ値は $4$ 個のバケットのどれかに等確率 $\frac{1}{4}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。$5$ 個すべてを挿入し終えたとき、キーを $2$ 個以上含むバケットの個数の期待値を求めよ。

次の $6$ 個の品物から、重さの合計が $12$ 以下になるようにいくつか選ぶ（各品物は選ぶか選ばないかのどちらかで、同じ品物を $2$ 個以上選ぶことはできない）。

選んだ品物の価値の合計の最大値を求めよ。

互いに異なる $5$ 個の数が入った配列から、小さい方から $3$ 番目の数（中央値）を、次の乱択選択アルゴリズム（乱択クイックセレクト）で求める。

• 現在の候補の集合を $X$ とし、最初は $X$ を $5$ 個の数全体とする。また、求めたい順位を $k=3$ とする。
• $X$ の要素が $1$ 個だけなら、それを答えとして終了する（比較は行わない）。
• そうでなければ、$X$ の要素から $1$ つを等確率で選んでピボット $p$ とし、$p$ を $X$ のほかのすべての要素と $1$ 回ずつ比較して、$p$ より小さい要素の集合 $L$ と大きい要素の集合 $R$ に分ける（このとき比較は $|X|-1$ 回行われる）。
• $|L|=k-1$ なら $p$ を答えとして終了する。
• $|L|\ge k$ なら、$X$ を $L$ に置き換えて（$k$ はそのまま）最初の手順に戻る。
• $|L|\le k-2$ なら、$X$ を $R$ に、$k$ を $k-|L|-1$ に置き換えて最初の手順に戻る。

ピボットの選択は毎回独立に行われるものとする。このアルゴリズムが終了するまでに行う比較の回数の期待値を求めよ。

互いに異なる $7$ 個の実数からなる集合を、次の乱択クイックソートで昇順に並べかえる。

• 大きさ $2$ 以上の集合 $S$ を処理するときは、$S$ の要素から $1$ 個をピボット $p$ として等確率で選ぶ。$p$ を $S$ のほかのすべての要素とそれぞれちょうど $1$ 回ずつ比較し、$S$ を $p$ より小さい要素の集合 $S_{-}$ と $p$ より大きい要素の集合 $S_{+}$ に分ける。そのあと、$S_{-}$ と $S_{+}$ をそれぞれ同じ方法で処理する。
• 大きさ $0$ または $1$ の集合を処理するときは、何もしない（比較を行わない）。

ピボットの選択はそれぞれ独立に行うものとする。最初の集合 $7$ 個全体を処理し始めてから終わるまでに行われる比較のうち、小さい方から $3$ 番目の要素がかかわる比較の回数の期待値を求めよ。

番号 $0,1,2,3,4$ の $5$ 個のスロットからなるハッシュ表が最初は空である。この表に、互いに異なる $3$ 個のキーを $1$ 個ずつ順に、次の線形探査法（オープンアドレス法）で挿入する。

• キーのハッシュ値を $h$ とし、スロット $h,h+1,h+2,\dots$ の順に（番号は $5$ を法として考え、スロット $4$ の次はスロット $0$ とする）調べ、最初に見つかった空のスロットにそのキーを入れる。
• $1$ 個のスロットを調べることを探査 $1$ 回と数える。キーを入れた空のスロットを調べることも $1$ 回に数える（たとえば、スロット $h$ が空ならば探査は $1$ 回）。

各キーのハッシュ値は $0,1,2,3,4$ のどれかに等確率 $\frac{1}{5}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。$3$ 個のキーを挿入し終えるまでの探査回数の合計の期待値を求めよ。

ある分割統治アルゴリズムは、大きさ $n$ の入力を大きさ $n/2$ の $4$ つの部分問題に分けて再帰的に解き、分割と統合に $n^2+n$ の手間をかける。入力の大きさは $2$ のべき $n=2^k$（$k$ は $0$ 以上の整数）に限って考え、その計算時間 $T(n)$ は
$$T(1)=1,T(n)=4T\left(\frac{n}{2}\right)+n^2+n(n=2^k,k\text{ は正の整数})$$
をみたすとする。$0$ 以上の整数 $k$ に対して、$T(2^k)$ を $k$ の式で表せ。

文字列 $Z$ から $0$ 個以上の文字を取り除き、残った文字を元の順に並べて得られる文字列を、$Z$ の部分列という（取り除く文字は連続していなくてよい）。

$2$ つの文字列
$$X=\mathrm{DBACBAD},Y=\mathrm{ABDCADB}$$
を考える。$X$ と $Y$ がどちらも $Z$ の部分列となるような文字列 $Z$（$X$ と $Y$ の共通超列）のうち、長さが最小のものの長さを求めよ。

$n$ を $3$ 以上の整数とする。相異なる $n$ 個の実数からなる列 $X=(x_1,x_2,\dots ,x_n)$ が与えられたとき、$X$ が単調であるかどうか、すなわち「$x_1<x_2<\cdots <x_n$ または $x_1>x_2>\cdots >x_n$」が成り立つかどうかを判定し、「はい」または「いいえ」を出力する問題を考える。

判定を行うアルゴリズムは決定的であり、入力の値には「2 つの添字 $i,j$ $(i\ne j)$ を指定して $x_i<x_j$ かどうかを調べる」比較によってのみアクセスできるものとする。どの比較を次に行うか、いつ停止して何を出力するかは、それまでの比較の結果だけから決まる。

この判定を常に正しく行う任意のアルゴリズムに対し、比較を少なくとも $n-1$ 回行う入力が存在すること、すなわち最悪の場合の比較回数が $n-1$ 以上であることを証明せよ。

$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}$ が成り立つことを証明せよ。

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

• 最初に $M\leftarrow A[1]$, $m\leftarrow A[1]$ とする。
• $i=2,3,\dots ,8$ の順に、次の操作を行う。
• まず $A[i]$ と $M$ を比較する。$A[i]>M$ ならば $M\leftarrow A[i]$ とし、この $i$ についての操作を終える（$m$ とは比較しない）。
• $A[i]<M$ ならば、続けて $A[i]$ と $m$ を比較する。$A[i]<m$ ならば $m\leftarrow A[i]$ とする。

配列の並び方は $8!$ 通りのどれも同様に確からしいとする。このアルゴリズムで行われる要素どうしの比較（$A[i]$ と $M$ の比較、$A[i]$ と $m$ の比較）の回数の期待値を求めよ。

ある分割統治アルゴリズムの計算時間 $T(n)$ は、$0$ 以上の整数 $k$ に対して $n=2^k$ のとき、次の漸化式で与えられる。
$$T(1)=1,T(n)=4T\left(\frac{n}{2}\right)+\frac{n^2}{{\log }_{2}n}(n\ge 2)$$
$n=2^k$ の形の $n$ に限って $n\to \infty$ を考えるとき、$T(n)=\Theta (g(n))$ となる関数 $g(n)$ を求めよ。答えは $\Theta$ の中身の式（定数倍を除いた最も簡単な形。例：$n\log n$）で答えよ。

番号 $0,1,2,3,4,5$ の $6$ 個のセルからなる、線形探査法（オープンアドレス法）のハッシュ表がある。最初はすべてのセルが空である。この表に、互いに異なる $4$ 個のキーを $1$ 個ずつ順に挿入する（削除は行わない）。

キー $x$ を挿入するときは、ハッシュ値 $h(x)\in \{0,1,\dots ,5\}$ から始めて、セル $h(x),h(x)+1,h(x)+2,\dots$（番号は $6$ を法として考え、セル $5$ の次はセル $0$ とする）の順に調べ、最初に見つかった空のセルにキーを格納する。調べたセルの個数（キーを格納した空のセルも $1$ 個と数える）を、その挿入の探査回数とよぶ。

各キーのハッシュ値は $0,1,\dots ,5$ のどれかに等確率 $\frac{1}{6}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。$4$ 個のキーの挿入における探査回数の合計の期待値を求めよ。

$n$ を $2$ 以上の整数とし、$n$ の関数として次の $8$ 個の計算時間を考える（$\log$ は自然対数、${\log }_2$ は底 $2$ の対数）。
$$f_1(n)=({\log }_{2}n{)}^{{\log }_{2}n},f_2(n)=n^3,f_3(n)=2^{\sqrt{2{\log }_{2}n}},f_4(n)=({\log }_{2}n{)}^5,$$
$$f_5(n)=\left(\genfrac{}{}{0ex}{}{2n}{n}\right),f_6(n)=\sum _{k=1}^n{k}^2\log k,f_7(n)=3^n,f_8(n)={\log }_2(n!)$$
正の値をとる関数 $f,g$ について、$\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=0$ が成り立つことを $f=o(g)$ と書く。
$1$ から $8$ までの番号を並べかえた組 $(i_1,i_2,\dots ,i_8)$ で
$$f_{i_1}=o(f_{i_2}),f_{i_2}=o(f_{i_3}),\dots ,f_{i_7}=o(f_{i_8})$$
がすべて成り立つものがただ $1$ つ存在する。この組 $(i_1,i_2,\dots ,i_8)$ を求めよ。

$8$ 種類の文字 $\mathrm{A},\mathrm{B},\mathrm{C},\mathrm{D},\mathrm{E},\mathrm{F},\mathrm{G},\mathrm{H}$ からなる長さ $100$ の文字列があり、各文字の出現回数は次の表のとおりである。

各文字に、$3$ 種類の記号 $0,1,2$ からなる長さ $1$ 以上の符号語を $1$ つずつ割り当てる。ただし、異なる文字の符号語は異なり、どの符号語も他の符号語の先頭部分（接頭語）になっていない（語頭符号である）ものとする。文字列の各文字をその符号語に置きかえてつなげたとき、得られる記号列の長さ（記号の個数）の最小値を求めよ。

文字列 $X$ から $0$ 個以上の文字を取り除き、残った文字を順序を変えずに並べた文字列を $X$ の部分列という。$2$ つの文字列 $X,Y$ の両方の部分列である文字列を共通部分列といい、共通部分列のうち長さが最大のものを最長共通部分列という。

$$X=\mathrm{CABDAB},Y=\mathrm{ABCADB}$$

とする。$X$ と $Y$ の最長共通部分列は、文字列として何通りあるか求めよ。ただし、取り出す文字の位置が異なっても、文字列として同じものは $1$ 通りと数える。

互いに異なる $6$ 個の実数を並べた配列を、次のマージソートで昇順に並べかえる。

• 長さ $1$ の列はそのまま返す。
• 長さ $k\ge 2$ の列は、前半の $\lceil k/2\rceil$ 個と後半の残り $\lfloor k/2\rfloor$ 個に分け、それぞれを再帰的に昇順に並べかえてから、次の手続きで併合する。
• 併合の手続き: 昇順に並んだ $2$ つの列 $P,Q$ が与えられたとき、どちらも空でない間は、$P$ の先頭と $Q$ の先頭を $1$ 回比較し、小さい方を取り出して出力の末尾に加える。一方の列が空になったら、もう一方の列に残っている要素を、比較を行わずにそのまま順に出力の末尾に加える。

入力の $6$ 個の数の並び方は $6!$ 通りすべてが等確率で現れるとする。このマージソート全体で行われる要素どうしの比較回数の期待値を求めよ。

バケット数 $5$ のチェイン法ハッシュ表が最初は空である。互いに異なるキーを $1$ 個ずつ順に挿入していき、すでに $1$ 個以上のキーが入っているバケットにキーが挿入された時点（最初の衝突が起きた時点）で挿入をやめる。各キーのハッシュ値は $5$ 個のバケットのそれぞれに確率 $\frac{1}{5}$ で、ほかのキーとは独立に定まるものとする。挿入をやめるまでに挿入したキーの個数を $T$ とする（衝突を起こしたキーも数える）。$T$ の期待値 $E[T]$ を求めよ。

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

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

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

$1$ 円、$7$ 円、$10$ 円の硬貨がそれぞれ十分な枚数あるとする。正の整数 $n$ に対し、$n$ 円をちょうど支払う硬貨の組み合わせのうち枚数が最小のものの枚数を $O(n)$ とする。また、次の貪欲法で $n$ 円を支払ったときの枚数を $G(n)$ とする。

貪欲法：残りの金額が $0$ になるまで、残りの金額以下で額面が最大の硬貨を $1$ 枚使う。

$1\leqq n\leqq 100$ を満たす整数 $n$ のうち、$G(n)>O(n)$ となるものの個数を求めよ。

$n>1$ の実数 $n$ の関数として、次の $5$ つを考える（$\log$ は自然対数）。
$$f_1(n)=2^{\sqrt{n}},f_2(n)=(\log n{)}^{\log n},f_3(n)=n^3,f_4(n)=n^{(\log n)/2},f_5(n)=n^{\sqrt{\log n}}$$
関数 $f,g$ について、$\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=0$ のとき $f=o(g)$ と書く。添字 $1,2,3,4,5$ を並べかえた $(i_1,i_2,i_3,i_4,i_5)$ で
$$f_{i_1}=o(f_{i_2}),f_{i_2}=o(f_{i_3}),f_{i_3}=o(f_{i_4}),f_{i_4}=o(f_{i_5})$$
をすべて満たすものはただ $1$ つある。組 $(i_1,i_2,i_3,i_4,i_5)$ を求めよ。

ある再帰アルゴリズムは、大きさ $n$ の入力を大きさ $\sqrt{n}$ の $2$ つの部分問題に分けて再帰的に解き、分割と統合に ${\log }_{2}n$ の手間をかける。その計算時間 $T(n)$ は、$0$ 以上の整数 $m$ に対して $n=2^{2^m}$ の形の $n$ について
$$T(2)=1,T(n)=2T\left(\sqrt{n}\right)+{\log }_{2}n(n\ge 4)$$
で定められている。

$0$ 以上の整数 $m$ に対し、$T\left(2^{2^m}\right)$ を $m$ の式で表せ。

互いに異なる $8$ 個の数を並べた配列を、次のマージソートで昇順に並べかえる。

• 長さ $1$ の配列はそのまま返す。
• 長さ $2k$（$k$ は正の整数）の配列は、前半 $k$ 個と後半 $k$ 個に分け、それぞれを再帰的にこのマージソートで並べかえたあと、次の「マージ」で $1$ つの昇順の列にまとめる。
• マージ: 昇順に並んだ 2 つの列の先頭どうしを $1$ 回比較し、小さい方を取り出して出力の末尾に加える。これを一方の列が空になるまで繰り返し、空になったら、もう一方の列に残っている数を比較せずにそのまま出力の末尾に加える。

入力の $8$ 個の数の並び方は $8!$ 通りすべてが等確率で現れるものとする。このとき、ソート全体で行われる数どうしの比較回数の期待値を求めよ。

$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$ 通りと数える）。

番号 $0,1,2,3,4$ の $5$ 個のビットからなるブルームフィルタを考える。最初はすべてのビットが $0$ である。このフィルタは $2$ 個のハッシュ関数 $h_1,h_2$ を使い、次のように動作する。

• 要素 $x$ を挿入するときは、ビット $h_1(x)$ とビット $h_2(x)$ を $1$ にする（$h_1(x)=h_2(x)$ のときは、そのビット $1$ 個だけが $1$ になる）。
• 要素 $y$ を問い合わせるときは、ビット $h_1(y)$ とビット $h_2(y)$ がともに $1$ であれば「含まれる」と答え、そうでなければ「含まれない」と答える。

互いに異なる $2$ 個の要素 $a,b$ をこの順に挿入したあと、$a,b$ のどちらとも異なる要素 $c$ を問い合わせる。ここで、$6$ 個の値 $h_1(a),h_2(a),h_1(b),h_2(b),h_1(c),h_2(c)$ は互いに独立で、それぞれ $0,1,2,3,4$ のどれかに等確率 $\frac{1}{5}$ で定まるとする。