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

ある会議室を使いたい $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$ の集合を求めよ。

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

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

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

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

$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）。

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

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

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

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

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

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