Standard 演習 解答
G. グラフと木（第6章）
G1
各辺は両端の頂点の次数を1ずつ増やすため、
deg(a)=2, deg(b)=2, deg(c)=3, deg(d)=1
となる。
G2
パスは、連続する2頂点の間に辺があるように並べた頂点列である。閉路はパスのうち、始点と終点が同じものである。
G3
木の辺数は頂点数より1少ないため6本。木では任意の2頂点間の単純道が一意なので、既存の2頂点を結ぶ辺を1本追加すると、その辺と既存の一意な道が閉路を作る。
G4
各辺 {u,v} は、uの次数とvの次数をそれぞれ1増やす。全頂点の次数を合計すると各辺をちょうど2回数えるため、次数の和は 2|E| になる。
G5
訪問順は、隣接頂点を記載順にQueueへ入れると次のとおり。
a, b, c, d, e
最短距離は次のとおり。
dist(a)=0, dist(b)=1, dist(c)=1, dist(d)=2, dist(e)=2
dはa-b-dまたはa-c-d、eはa-c-eで距離2になる。
G6
再帰DFSは a から b、b から d、d から c、c から e へ進む。訪問済み頂点は飛ばすため、訪問順は次のとおり。
a, b, d, c, e
G7
BFSは始点を距離0の層としてQueueへ入れ、取り出した頂点の未訪問隣接頂点を次の距離の層として末尾へ追加する。Queueは先に発見した浅い層を先に処理するため、頂点を最初に発見した時点の距離が最短距離になる。
G8
uからvへの有向パスを P1、vからwへの有向パスを P2 とする。P1の末尾とP2の先頭はいずれもvなので、vを重ねずに両方の頂点列を連結すれば、各辺の向きに従うuからwへのパスが得られる。したがってuからwへ到達できる。
G9
たとえば次の順序が条件を満たす。
a, b, c, d, e
aとb、cとdは、それぞれ必要な先行関係を保つ範囲で入れ替えられるため、解は一意とは限らない。
G10
入次数0の頂点が存在しないと仮定する。任意の頂点 v0 には流入辺があるため、その始点を v1 とする。同様に v1 へ入る頂点 v2 を選び、この操作を続ける。グラフは有限なので、得られる頂点列では同じ頂点が必ず再登場する。その間の辺をたどると有向閉路が得られ、DAGであることに矛盾する。したがって入次数0の頂点が少なくとも1つ存在する。
G11
n=1では辺数は0で、n-1に等しい。n=kの木がk-1本の辺を持つと仮定する。頂点数2以上の有限木で最長の単純パスを取ると、その端点は次数1でなければパスを延長できるため、葉が存在する。k+1頂点の木から葉とその接続辺1本を除いても連結性と非巡回性は保たれるので、残るグラフはk頂点の木である。帰納法の仮定から残りの辺数はk-1本であり、除いた1本を戻すとk=(k+1)-1本になる。
G12
擬似コードの一例は次のとおり。
BFS_DISTANCE(G, s):
for v in V:
dist[v] = ∞
dist[s] = 0
Q = empty queue
ENQUEUE(Q, s)
while Q is not empty:
u = DEQUEUE(Q)
for v in Adj[u]:
if dist[v] == ∞:
dist[v] = dist[u] + 1
ENQUEUE(Q, v)
return dist
各頂点は高々1回Queueへ入り、各頂点の隣接リストも1回だけ走査する。したがって頂点処理に O(|V|)、辺の走査に O(|E|) を使い、合計は O(|V|+|E|) である。
A. 組合せと数え上げ
S1
各位置に 0 または 1 の2通りがあるので、積の法則により 2^n 個。
S2
n 個の位置から、1 を置く k 個の位置を選べばよい。したがって C(n,k) 個。
S3
各要素について、部分集合に入れるか入れないかの2択がある。したがって 2^n 個。
S4
最初に n 通り、次に n-1 通り、以後同様なので n! 通り。
S5
n(n-1)...(n-k+1) = n!/(n-k)! 通り。
S6
順序を無視するので、順序付きの選び方 n!/(n-k)! を k! で割る。したがって C(n,k) = n!/(k!(n-k)!)。
S7
k 個を選ぶことは、選ばない n-k 個を決めることと一対一に対応する。よって C(n,k) = C(n,n-k)。
S8
特定の要素 x に注目する。x を選ばない場合は C(n-1,k) 通り。x を選ぶ場合は、残りから k-1 個選ぶので C(n-1,k-1) 通り。この2場合は重ならず、すべてを尽くすため、和を取る。
S9
左辺は、サイズ k の部分集合をすべての k について数え上げたもの。右辺は、各要素について「入れる」「入れない」を選んだもの。どちらも n 要素集合のすべての部分集合を数えている。
S10
2で割り切れるものは50個。5で割り切れるものは20個。両方で割り切れるもの、つまり10で割り切れるものは10個。
50 + 20 - 10 = 60
答えは60個。
S11
2で割り切れるものは50個、3で割り切れるものは33個、5で割り切れるものは20個。
2かつ3は6の倍数で16個。2かつ5は10の倍数で10個。3かつ5は15の倍数で6個。2かつ3かつ5は30の倍数で3個。
50 + 33 + 20 - 16 - 10 - 6 + 3 = 74
答えは74個。
S12
誕生月は12種類の箱、13人は13個の物に対応する。鳩ノ巣原理により、少なくとも1つの月に2人以上が入る。
S13
各桁に10通りあるので 10^n 個。
S14
重複なしで長さ n の列を作るため、
10·9·8·...·(10-n+1) = 10!/(10-n)!
個。n=0 の場合は空列1個。
S15
各変数に真または偽の2通りがあるので 2^n 個。
S16
Q×Σ の要素数は m a。遷移関数表には各組に対する遷移先が必要なので、エントリ数は ma。
S17
先頭は 1 に固定。残り n-1 位置は自由に選べるので 2^{n-1} 個。
S18
末尾で場合分けする。末尾が 1 なら、その前は長さ n-1 の有効列。末尾が 0 なら、直前は 0 ではいけないので、末尾は 10 で、その前は長さ n-2 の有効列。よって
a_n = a_{n-1} + a_{n-2}
初期値は a_0=1, a_1=2。
S19
非負整数解
x_a + x_b + x_c = k
の個数。仕切りと玉により C(k+2,2) 個。
S20
比較ソートは、入力がどの順列であるかを比較結果から区別して、正しい順序を出力する必要がある。相異なる n 要素には n! 通りの順列があり、比較に基づく決定木はこれらを別々の葉に割り当てなければならない。このため、比較ソートの下界は log_2(n!) と関係し、これは Ω(n log n) になる。
B. データ構造と基本アルゴリズム
S21
抽象データ型は、提供する操作と意味を定めるもの。Stack なら push, pop, top などを持ち、LIFO で動作する。実装は、それを配列で実現するか、連結リストで実現するかという具体的方法である。
S22
配列では、先頭アドレス、要素サイズ、インデックスから対象要素の位置を直接計算できる。要素を順に辿らないため O(1) とみなされる。
S23
先頭に要素を挿入すると、既存の n 個の要素を後ろにずらす必要があるため、移動回数が n に比例する。したがって O(n)。
S24
連結リストでは、i 番目のノードのアドレスを直接計算できない。先頭から次ポインタを辿る必要があるため、最悪で i 個、つまり O(n)。
S25
Stack は LIFO。最後に入れた要素を最初に取り出す。用途例は DFS や関数呼び出し管理。Queue は FIFO。最初に入れた要素を最初に取り出す。用途例は BFS やタスクキュー。
S26
ハッシュ値がよく分散していれば、各バケットの要素数は小さく、平均 O(1) で検索できる。しかし、多数のキーが同じバケットに衝突すると、そのバケット内を線形に調べる必要があり、最悪 O(n) になる。
S27
最小値を見るだけなら根を見るので O(1)。最小値を削除する場合は、根を取り除いた後にヒープ条件を回復するため、木の高さに比例して O(log n)。
S28
二分探索木が一直線に偏ると、構造は連結リストと同じになる。検索では根から順に子を辿るため、最悪で全ノードを見ることになり O(n)。
S29
make_set(x), find(x), union(x,y)。
S30
隣接行列はメモリ O(|V|^2) を使い、辺の存在確認は O(1)。隣接リストはメモリ O(|V|+|E|) で済むが、辺の存在確認は通常、隣接リスト内の探索が必要で O(deg(v)) などになる。
S31
無向辺 {u,v} は、u の隣接リストに v を入れ、v の隣接リストに u を入れる。
S32
BFS は始点から距離0、距離1、距離2の順に探索する。先に発見した頂点を先に処理する必要があるため FIFO の Queue が適している。
S33
DFS は、現在の頂点から未訪問の隣接頂点へ深く進み、行き止まりで戻る探索である。最後に発見した未処理箇所から再開するため Stack が適している。再帰呼び出しも実質的に呼び出しスタックを使う。
S34
各頂点は高々一度訪問されるため O(|V|)。各辺は隣接リストを走査する過程で定数回だけ調べられるため O(|E|)。合計で O(|V|+|E|)。
S35
[left,right) では空区間が left == right で表せる。また、中央より左側と右側を分けるときに right = mid や left = mid+1 と書きやすく、境界条件を統一しやすい。
S36
7 以上となる最初の位置は、値 7 が最初に現れるインデックス4。
S37
挿入ソート O(n^2)、マージソート O(n log n)、クイックソート O(n^2)、ヒープソート O(n log n)。
S38
未確定頂点の中から、現在の暫定距離が最小の頂点を効率よく取り出すため。単純に全頂点を走査すると高くつくが、優先度付きキューを使うと取り出しや更新を対数時間程度で扱える。
S39
状態は、部分問題を識別するための変数や添字である。遷移は、小さい状態の答えから大きい状態の答えを計算する規則である。
S40
たとえば dp0[i] を長さ i の有効列で末尾が 0 の個数、dp1[i] を末尾が 1 の個数とする。
dp0[i] = dp1[i-1]
dp1[i] = dp0[i-1] + dp1[i-1]
初期値は dp0[1]=1, dp1[1]=1。合計は dp0[n]+dp1[n]。別解として a_n = a_{n-1}+a_{n-2} でもよい。
C. 形式言語の入口
S41
Σ は記号の集合。Σ* は Σ の記号から作られるすべての有限文字列の集合。
S42
ε は長さ0の文字列。∅ は要素を1つも持たない集合。ε は文字列であり、∅ は集合である。
S43
ε, 0, 1, 00, 01, 10, 11
S44
|ε| = 0
|0| = 1
|10101| = 5
S45
uv = 01100
vu = 10001
S46
n=0,1,2,3 に対応して、
ε, 01, 0011, 000111
S47
L1L2 = {0a, 0b, 1a, 1b}
S48
ε, 0, 00, 000, 0000
S49
任意長のビット列のうち、末尾が 1 のものを表す。長さ1以上で、最後の記号が 1。
S50
0が0個以上続き、その後に1が0個以上続く文字列の集合。例: ε, 0, 1, 00, 01, 11, 00111。ただし 10 や 101 は含まれない。
S51
生成される文字列は、0個以上の a の後に b が1つあるもの。短いものから、
b, ab, aab, aaab, aaaab
S52
0 と 1 が同数で、すべての 0 がすべての 1 より前にある文字列。つまり
{ 0^n1^n | n >= 0 }
S53
M = (Q, Σ, δ, q0, F)
Q は状態集合、Σ は入力アルファベット、δ は遷移関数、q0 は初期状態、F は受理状態集合。
S54
これまで読んだ 0 の個数が偶数か奇数かだけを覚えればよい。したがって、偶数状態と奇数状態の2状態を用意し、0 を読むたびに状態を反転し、1 を読んでも状態を変えない。初期状態かつ受理状態は偶数状態。
S55
現在状態 q∈Q と入力記号 a∈Σ の組に対して、次状態 δ(q,a)∈Q を返す関数である。
S56
NFA は確率で遷移を選ぶモデルではない。入力を受理するとは、可能な遷移経路の中に受理状態へ到達するものが少なくとも1つ存在する、という意味である。
S57
判定問題を、入力文字列の集合への所属判定として表すこと。素数判定なら、整数 n を符号化した文字列 enc(n) のうち、n が素数であるもの全体を
PRIME = { enc(n) | n は素数 }
と定義し、入力が PRIME に属するかを判定する。
S58
{ε} は空文字列を1つだけ含む集合。∅ は何も含まない集合。{∅} は空集合を1つの要素として含む集合。したがって3つはすべて異なる。
S59
無限言語。たとえば ε, 11, 1111, 111111, … のように、1 を偶数個含む文字列は無限に存在する。
S60
文字列は、空文字列から始めて記号を1つずつ連結する形で再帰的に定義できる。そのため、空文字列の場合を示し、任意の文字列で成り立つと仮定して1文字追加した場合を示す、という構造帰納法が使える。