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.

第12回 全解の構造と選択

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

← 备考目录

試験時間(目安)満点問題数
200分100点全3問
問題分野テーマ配点
問題1グラフ理論すべての経路が通る辺35点
問題2動的計画法個数を指定した重み付き区間選択35点
問題3整列アルゴリズム必要な先頭だけを整列する30点

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

すべての経路が通る辺

有向非巡回グラフ G=(V,E)G=(V,E) と、相異なる頂点 s,ts,t が与えられ、ss から tt への有向道が少なくとも一つ存在する。辺の重複はない。すべての s−ts-t 道が通る頂点を必経頂点、すべての s−ts-t 道が使う辺を必経辺という。道の本数を数える際には、整数を厳密に保持するものとし、当初は任意精度整数の加算・乗算を1操作と数える。最後の小問ではビット計算量を別に評価する。

(1) 道数の漸化式(5点)

ss から vv までの道の本数を A(v)A(v)、vv から tt までの道の本数を B(v)B(v) とする。トポロジカル順序を用いる二つの漸化式と初期値を示し、到達不能な頂点の扱いを説明せよ。

(2) 辺の通過道数(5点)

辺 e=(u,v)e=(u,v) を使う s−ts-t 道の本数が A(u)B(v)A(u)B(v) となることを証明せよ。DAG であることが、前半と後半の道を連結する際にどこで必要になるかも述べよ。

(3) 必経辺と必経頂点(7点)

必経辺と必経頂点を道の本数の式で判定する方法を示せ。M=A(t)M=A(t) とし、M>0M>0 の仮定を使って必要十分性を証明せよ。s,ts,t を必経頂点に含めるかも明記せよ。

(4) 道数の具体例(6点)

頂点は {s,a,b,c,d,z,t}\{s,a,b,c,d,z,t\}、辺は s→a,s→b,a→c,b→c,a→d,b→d,c→z,d→z,z→ts\to a,s\to b,a\to c,b\to c,a\to d,b\to d,c\to z,d\to z,z\to t とする。全頂点の A,BA,B を表にし、必経頂点・必経辺をすべて求めよ。

(5) 最短道への限定(7点)

各辺に非負の長さが与えられた場合、すべての最短 s−ts-t 道が通る辺を求めたい。ss からの距離と tt までの距離を使って対象辺だけを残す方法を示し、その部分グラフで本問の計数法を適用できることを証明せよ。

(6) ビット計算量と辺削除法(5点)

道数のビット長の最大を LL とする。加算 O(L)O(L)、通常の整数乗算 O(L2)O(L^{2}) としたビット計算量を示せ。さらに大整数を使わず、辺を1本ずつ削除して必経性を判定する方法と比較せよ。

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

個数を指定した重み付き区間選択

nn 個の半開区間 Ij=[sj,fjI_{j}=[s_{j},f_{j}) に重み wjw_{j} が付いている。sj<fjs_{j}<f_{j} であり、重みは負でもよい。互いに重ならない区間をちょうど qq 個選び、重みの和を最大化したい。0≤q≤n0\le q\le n とする。区間は終了時刻の非減少順に並べ、同じ終了時刻では入力番号順とする。p(j)p(j) は、jj より前の区間のうち fi≤sjf_{i}\le s_{j} を満たす最大の番号であり、そのような区間がなければ0とする。実現不能な状態の値は −∞-\infty とする。

(1) 適合する接頭辞の探索(5点)

p(j)p(j) を各区間について求める方法を書け。終了時刻の整列と二分探索を含めた計算量を示せ。半開区間であることが適合条件の等号にどう関係するかも説明せよ。

(2) 状態と漸化式(6点)

D(j,r)D(j,r) を先頭 jj 区間からちょうど rr 個選ぶ最適値とする。境界と漸化式を定め、最後の区間 jj を選ぶ場合・選ばない場合に分けて正しさを証明せよ。

(3) 具体例と最適集合(7点)

区間と重みを順に (0,3,5),(1,4,6),(3,5,4),(4,7,7),(5,8,8)(0,3,5),(1,4,6),(3,5,4),(4,7,7),(5,8,8) とする。pp の列、および j=0,…,5j=0,\ldots ,5、r=0,…,3r=0,\ldots ,3 の DD 表を作れ。ちょうど2個・ちょうど3個の最適な集合をそれぞれ求めよ。

(4) 復元と個数制約(6点)

最適集合を復元する手順と必要な情報を示せ。また「高々 qq 個」の問題に変更したときの答えを DD で表せ。負の重みがあるため、ちょうど qq と高々 qq が異なる例も作れ。

(5) 個数順の計算と空間削減(6点)

時間 O(nq)O(nq) の計算を擬似コードで示せ。最適値だけなら rr を外側のループにすることで O(n)O(n) 空間に削減できることを説明し、jj を外側として単純に2行だけ保持する方法が不適切な理由も述べよ。

(6) 密なDAGとの比較(5点)

各区間を頂点とし、適合する i,ji,j に辺 i→ji\to j を置くDAGによっても問題を表せる。個数を状態に加えた最長道の計算を説明し、全辺を明示すると遅くなり得る理由と p(j)p(j) による改善の意味を述べよ。

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

必要な先頭だけを整列する

NN 個のレコードから、キーが小さい順の先頭 kk 個だけを昇順に出力したい。1≤k≤N1\le k\le N とする。同じキーでは入力順を保つため、各レコードに元の位置 ii を付け、組 (キー,ii) を辞書式に比較する。これにより比較対象は全順序で相異なる。比較・移動は定数時間とする。全 NN 個を整列する方法より、kk が小さいときに有利な最悪計算量保証を目指す。

(1) 線形時間の選択法(6点)

5個ずつの群の中央値から再帰的に中央値を選ぶ選択法を記述せよ。選んだピボットで分割した際、少なくとも 3N/10−63N/10-6 個を片側から除外できる理由と、線形時間となる漸化式を示せ。

(2) 中央値と分割の具体例(5点)

キーの列を5個ずつ 19,4,12,8,25/7,21,3,16,10/11,2,24,6,1719,4,12,8,25 / 7,21,3,16,10 / 11,2,24,6,17 に分ける。各群の中央値、中央値の中央値、最初の分割結果を求めよ。第6小要素を求める際に次に探索する群も示せ。

(3) 選択後の部分整列(7点)

線形時間選択を利用し、先頭 kk 個だけを安定に整列するアルゴリズムを書け。選択、抽出、残った要素の整列を区別し、最悪時間 O(N+klog⁡(k+1))O(N+k \log(k+1)) と補助空間の上界を示せ。

(4) 比較回数の下界(6点)

キーがすべて異なる入力に制限しても、問題に必要な最悪比較回数が Ω(N+klog⁡(k+1))\Omega (N+k \log(k+1)) となることを証明せよ。最小値を必ず出力することと、kk個の未知の順序を区別することをそれぞれ使え。

(5) 最大ヒープとの比較(6点)

大きさ kk の最大ヒープを用いて先頭候補を保持する方法を示し、全整列・(3)の方法と比較せよ。k=1k=1、kkが小さい定数、k=Nk=N の各場合の時間の違いも説明せよ。