Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

第17回 削除の影響・禁止パターン・入力構造への適応

グラフ理論・動的計画法・整列アルゴリズム

← 备考目录

試験時間(目安)満点問題数
210分100点全3問
問題分野テーマ配点
問題1グラフ理論頂点需要を用いた分離被害と感度35点
問題2動的計画法禁止パターンを含まない共通部分列35点
問題3整列アルゴリズム区間の長さに適応する安定整列30点

問題1 · グラフ理論(35点)

頂点需要を用いた分離被害と感度

頂点数 n≥2n\ge 2 の連結単純無向グラフ G=(V,E)G=(V,E) に正の整数の頂点需要 μ(v)\mu (v) が付く。総需要を M=∑μ(v)M=\sum \mu (v) とする。頂点 vv の削除後の各連結成分の需要和を a1,…,aka_{1},\ldots ,a_{k} とし、I(v)=∑i<jaiajI(v)=\sum _{i<j}a_{i}a_{j} と定める。これは分断される頂点対 {x,y}\{x,y\} の需要積 μ(x)μ(y)\mu (x)\mu (y) の総和であり、頂点数だけでは被害を測れない。DFS の発見番号 dd、親の木辺を除く後退辺から計算する low、部分木需要 t(v)=∑x∈subtree⁡(v)μ(x)t(v)=\sum _{x\in \operatorname{subtree}(v)}\mu (x) を用いる。全頂点の被害を一括計算し、需要の変化に対する感度も調べよ。

(1) 分離条件の証明(5点)

根でない頂点 vv の子 cc について、low⁡(c)≥d(v)\operatorname{low}(c)\ge d(v) なら cc の部分木が G−vG-v の一つの成分になることを証明せよ。low⁡(c)<d(v)\operatorname{low}(c)<d(v) の子の部分木が、vv の親を含む側と連結していることも証明せよ。

(2) 成分需要と根の扱い(6点)

根でない vv を削除したときの成分需要を t(c),M,μ(v)t(c),M,\mu (v) を用いて表せ。「残りの成分」の需要が正である理由を述べよ。DFS 根の場合の式を別に示し、同じ成分サイズでも需要によって被害が違う例を与えよ。

(3) 全頂点の被害計算(6点)

I(v)=((M−μ(v))2−∑ai2)/2I(v)=((M-\mu (v))^{2}-\sum a_i^{2})/2 を導け。全頂点について I(v)I(v) と成分需要一覧を O(n+m)O(n+m) 時間で計算する擬似コードを書け。一覧の総出力長と、必要な整数の桁数にも触れよ。

(4) 関節点と橋の不等号(6点)

low⁡(c)≥d(v)\operatorname{low}(c)\ge d(v) を low⁡(c)>d(v)\operatorname{low}(c)>d(v) に置き換える誤った方法が見落とす関節点を、5頂点以上の具体的なグラフで示せ。同時に、橋の判定に厳密な不等号が必要である理由を説明せよ。

(5) 需要付きグラフの具体例(7点)

根1、番号順の DFS とし、辺は {12,23,31,34,45,56,64,47,78}\{12,23,31,34,45,56,64,47,78\}、頂点需要は順に (1,2,1,3,1,2,1,2)(1,2,1,3,1,2,1,2) である。各 d,low⁡,td,\operatorname{low},t と、関節点の削除後の成分需要・I(v)I(v) を求め、被害最大の頂点を答えよ。

(6) 連結問い合わせと感度(5点)

v,x,yv,x,y は相異なる頂点とする。多数の (v,x,y)(v,x,y) の連結判定を O(log⁡n)O(\log n) で答える前処理を設計せよ。μ(z)+Δ>0\mu (z)+\Delta >0 を保つ単一変更の I(v)I(v) の感度も求め、v=zv=z と v≠zv\ne z を区別せよ。変更自体は実行しない。

問題2 · 動的計画法(35点)

禁止パターンを含まない共通部分列

二つの文字列 X=X1…XmX=X_{1}\ldots X_{m}、Y=Y1…YnY=Y_{1}\ldots Y_{n} は文字 A,BA,B からなる。両方の共通部分列であり、その結果の文字列の連続部分文字列として ABA を含まないもののうち、最長のものを求める。入力に ABA が含まれるかどうかではなく、選んだ文字を連結した結果に対する制約である。結果の接尾辞が ABA の真の接頭辞のどれと一致するかを状態にし、q=0,1,2q=0,1,2 をそれぞれ空、AA、AB に対応させる。ABA が完成すると禁止状態へ入る。空部分列は許され、実現不能状態は −∞-\infty とする。

(1) 禁止パターンの遷移表(5点)

各状態 qq と新しい文字 A,BA,B に対する遷移表を作れ。たとえば q=1q=1 で AA を読むとき、状態を0に戻すのが誤りである理由を説明せよ。

(2) 後処理が最適でない反例(5点)

通常の最長共通部分列を一つ求め、その中の最も左の ABA の中央の BB を消す操作を繰り返す方法は最適とは限らない。X=Y=ABABAX=Y=ABABA でこの方法と最適解を比較し、制約を後処理にできない理由を述べよ。

(3) 状態を追加したLCS(8点)

F(i,j,q)F(i,j,q) を XX の長さ ii の接頭辞と YY の長さ jj の接頭辞から得られ、状態 qq で終わる合法な共通部分列の最大長と定義する。境界値と全遷移を示し、状態 qq が最適部分構造を回復させることを証明せよ。

(4) 最適部分列の具体例(5点)

X=AABABAX=AABABA、Y=ABAABAY=ABAABA について最適長と最適部分列を一つ求め、双方で選ぶ位置を示せ。最適長を証明するため、最後のセルの3状態の値、または同等の上界を示せ。

(5) 一般の禁止語への拡張(7点)

禁止語を任意の長さ h≥1h\ge 1 の1語 PP に置き換える。状態を「結果の接尾辞と一致する PP の最長の真の接頭辞の長さ」とするオートマトンを定義し、遷移の構築方法と DP の時間・空間を評価せよ。PP の完成を避ける遷移のみを採用すること。

(6) 復元と相異なる部分列の個数(5点)

最適部分列を一つ復元するための情報を説明せよ。DP の経路数を数えることが、相異なる最適部分列の個数を数えることと一致しない具体例を与え、この二つを区別せよ。

問題3 · 整列アルゴリズム(30点)

区間の長さに適応する安定整列

元の配列中の kk 本の連続区間は、それぞれ整列済みで長さ r1,…,rkr_{1},\ldots ,r_{k} が知られている。N=∑ri≥2N=\sum r_{i}\ge 2、pi=ri/Np_{i}=r_{i}/N、H=∑pilog2(1/pi)H=\sum p_ilog_{2}(1/p_{i}) とする。隣接区間の安定併合の費用は要素数の和である。O(Nlog⁡k)O(N \log k) の一律の評価から進み、長さが偏っている場合にも有利な O(N(1+H))O(N(1+H)) の手順を設計したい。二進語 b1…bdb_{1}\ldots b_d を、[0,10,1) の長さ 2−d2^{-d} の二進区間に対応させる。互いに交わらない二進区間に対応する語は、相互に接頭語にならないという性質を利用してよい。

(1) 下降区間と安定性(4点)

任意の配列から非減少区間と厳密な減少区間を取り出し、減少区間を反転して整列済み区間にする方法を説明せよ。減少区間に等号を認めて反転すると安定性が失われる具体例を示せ。

(2) 均等葉数の併合木(4点)

葉数を均等に二分する併合木の費用が O(Nlog⁡k)O(N \log k) となる理由を述べよ。長さ (N−k+1,1,…,1)(N-k+1,1,\ldots ,1) について、その上界が HH を用いた評価より粗くなり得ることを示せ。

(3) 中点を使う接頭語符号(7点)

si=∑j<ipjs_{i}=\sum _{j<i}p_{j} とし、区間 [si,si+pis_{i},s_{i}+p_{i}) の中点を含む長さ 2−ℓi2^{-\ell _{i}} の二進区間を選ぶ。ただし ℓi=⌈log⁡2(1/pi)⌉+1\ell _{i}=\lceil \log_{2}(1/p_{i})\rceil +1 とする。この二進区間が元の区間内に収まることと、得られる語が葉順を保つ接頭語符号となることを証明せよ。

(4) 葉順を保つ木の構築(7点)

(3)の語から二分木を作り、子が1個だけの頂点を縮約して合法な隣接併合木を得よ。総費用が N(H+2)N(H+2) 未満となることを示せ。木の構築も含めて O(N(1+H))O(N(1+H)) 時間に収まる理由を説明せよ。

(5) 情報量の下界(4点)

キーがすべて異なり、各区間内の順序だけが既知である比較モデルを考える。可能な全併合順序の数を求め、比較回数の下界を示せ。N!≥(N/e)NN!\ge (N/e)^N と r!≤rrr!\le r^r を使い、下界と NH の関係を評価せよ。

(6) 長さに適応する具体例(4点)

すべての要素を書き出す時間も費用に含める。(5)の下界から最悪時間 Ω(N(1+H))\Omega (N(1+H)) を導き、(4)までのアルゴリズムがこの入力の約束に対してオーダー最適であることを説明せよ。