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

$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$ の列の長さ（ビット数）を求めよ。

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

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

文字列 $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!$ 通りすべてが等確率で現れるとする。このマージソート全体で行われる要素どうしの比較回数の期待値を求めよ。

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

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