院試アルゴリズムの対策正当性と計算量の書き方

演習で確かめるのは、擬似コードが正しい結果を返すことと、実行時間や使用メモリを説明できることの二つです。答案には配列の境界と停止条件、計算量で数えた操作を残してください。

試験科目や配点、出題範囲は研究科ごとに違います。最新の募集要項と公式過去問で確認してください。このページは公開過去問の分類と定番の解き方をもとに、計算量、データ構造、グラフ、動的計画法を順に扱います。

教科書で補うならアルゴリズムの参考書と使う章へ。操作を追う段階で止まる人と、正当性や計算量の説明で止まる人とで、読む章を分けてあります。演習の解答をどこまで照合できるかも載せました。

二分探索の答案を正当性まで閉じる

昇順配列 a = [2, 5, 5, 9, 14, 20] から、x = 5 以上になる最初の位置を探します。擬似コードが動いても、それだけでは正当性の根拠になりません。事前条件、不変条件、停止性、計算量の4項目を分けて書きます。

lo = -1
hi = n
while hi - lo > 1:
    mid = floor((lo + hi) / 2)
    if a[mid] >= x:
        hi = mid
    else:
        lo = mid
return hi

証明の中でだけ a[-1] = -∞、a[n] = +∞ とみなし、ループ不変条件を a[lo] < x ≤ a[hi] と置きます。実装が番兵の位置を読むことはありません。a[mid] ≥ x なら hi = mid、そうでなければ lo = mid と更新するので、不変条件は崩れません。

反復ごとに区間長 hi − lo はほぼ半分になり、正の整数のまま減っていきます。だから必ず hi − lo = 1 で止まります。この実装の比較回数は高々 ceil(log₂(n + 1))、計算量は O(log n) です。返り値が n なら、条件を満たす要素はありません。

設問そのものは大学の一次資料で見てください。東京大学情報理工学系研究科は入試問題アーカイブ、東京科学大学は大学院入試の過去問題を案内しています。ほかの大学は公式過去問リンク集から辿れます。

この節と過去問の解答・解説は院試hubが作ったもので、大学の公式解答ではありません。誤りに気づいたら制作方針と訂正窓口から知らせてください。

学部で身につけておく基礎

• 離散数学：集合と写像、同値関係と順序関係、命題論理と述語論理、数学的帰納法。次数や連結、木といったグラフ理論の用語も出てきます
• オーダー記法：O、Ω、Θ の定義の違い。最悪計算量と平均計算量、償却計算量をどう使い分けるか。マスター定理は適用条件まで言えるようにします
• 再帰と帰納法：正当性を帰納法で示し、再帰関係を漸化式に直す
• データ構造：配列、連結リスト、スタック、キュー、木、グラフ。それぞれの内部表現と、各操作にかかる計算量を言えるようにします
• 確率と組み合わせ：期待値の線型性と二項係数。ハッシュ法の衝突確率や乱択アルゴリズムで使います
• 形式言語：出題範囲にあるなら、正規表現とオートマトンの対応と、文脈自由文法の定義と導出まで

分割統治の計算量は、部分問題の数と入力サイズ、再帰以外にかかる費用から漸化式を立てて求めます。 T(n) = aT(n/b) + f(n) の形になったら、マスター定理の条件に入るかを確かめます。

論点別の条件と確認方法

このあとはソート、グラフ、動的計画法、計算量クラス、文字列、形式言語の順です。各節に、解法を使える条件と答案で確かめることを書きました。

ソートと探索の計算量解析

クイックソートやマージソート、ヒープソート、基数ソート、二分探索、ハッシュ法を比べるときは、入力と数える操作をそろえます。「O(n log n)です」で終わらせず、どの操作を何回数えたかまで書いてください。

クイックソートの平均計算量なら、ピボット選択の確率分布を仮定して再帰関係 T(n) = T(k) + T(n-k-1) + O(n) を立てます。期待値の線型性を通って O(n log n) に至る流れを答案に残します。

マージソートは T(n) = 2T(n/2) + Θ(n) から、マスター定理のケース2で Θ(n log n)。f(n) と n^(log_b a) の比を確かめておくと、どの場合分けを使ったかの根拠になります。

安定性を問われたら、指定された実装で同じキーの要素の順序が保たれるかを追います。不安定だと言うなら、順序が逆転する入力と、そのときの交換操作を示してください。

基数ソートやバケットソートは線形時間を狙うソートです。整数で値域が O(n) といった入力の仮定を、答案の頭に書きます。書かずにおくと「O(n) ソートがあるのだから比較ソートの下界 Ω(n log n) と矛盾する」という誤解を招きます。キー比較以外に使える操作と、値域や分布の仮定は別のものです。

ハッシュ法では、チェイン法とオープンアドレス法の計算量を負荷率 α の関数で書き分けます。一様ハッシュ等の仮定の下で、チェイン法はαが定数以下なら期待 O(1)。オープンアドレス法は、αを1より小さい定数以下に抑える条件も要ります。

二分探索木は、平衡性の保証がなければ最悪 O(n) です。答案にはそれを書いたうえで、AVL 木や赤黒木、B 木のどれかで O(log n) を保証する流れにつなげます。

グラフアルゴリズム（DFS/BFS、最短経路、最小全域木）

DFS と BFS、最短経路、最小全域木、最大流では、何を求めるかと辺の条件を分けて考えます。計算量を比べる前に、グラフを隣接リストで持つか隣接行列で持つかをそろえてください。

ダイクストラ法の計算量はデータ構造で変わります。配列なら O(V²)、二分ヒープなら O((V+E) log V)、フィボナッチヒープなら O(E + V log V)。 各頂点と各辺を何回処理し、キュー操作にいくらかかるかを対応させます。

ダイクストラ法を使う前に、辺の重みが非負かを見ます。 ベルマン・フォード法なら負の辺も扱えます。ただし、始点から到達できる負閉路を通って届く頂点には、有限の最短距離がありません。 距離の計算と負閉路の検出は分けて書き、どの頂点が影響を受けるかを確かめます。

MITのベルマン・フォード法の講義資料は、到達できない頂点と有限距離を持つ頂点、負閉路の影響を受ける頂点を分けて扱っています。

ワーシャル・フロイド法では、dp[k][i][j]を「中間頂点に1からkまでを使えるときの、iからjへの最短距離」と定義します。 有限の最短距離を求めるなら、負閉路がないことが前提です。dp[k-1]からdp[k]を作る依存関係と、kを最外周のループに置く実装を対応させてください。

最小全域木をクラスカル法で解くなら、連結成分をどう管理するかを書きます。 経路圧縮とランク併合を使うUnion-Findでは、1操作あたりの償却計算量と操作回数を分けて数えます。 プリム法で数えるのは優先度付きキューの操作回数です。

最大流には区別すべき点が二つあります。整数容量・初期流0のフォード・ファルカーソンは、計算量が容量の数値にも依存する擬似多項式時間です。エドモンズ・カープは BFS で最短の増加路を選ぶので、O(VE²) の多項式時間になります。最大流・最小カット定理を使うなら、流量とカット容量を同じ定義で計算し、最適値が一致するのを確かめてください。

動的計画法と分割統治

ナップサック問題、最長共通部分列、編集距離、行列連鎖積。どれも漸化式より先に部分問題を定義します。たとえば「dp[i][j] = ナップサックの容量 j まで使って最初の i 個から得られる最大価値」と配列の意味を書き、遷移と初期条件、計算順序がその定義に合うかを見ます。

遷移式 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w_i] + v_i) を書いたら、境界条件も添えてください。dp[0][j] = 0 とし、j < 0 のときの扱いを決め、i を外側、j を内側にして埋めます。

最長共通部分列は遷移が3通りです。一致する場合、i 側を進める場合、j 側を進める場合を分けて書けば、条件と境界を検算できます。編集距離は挿入と削除、置換に対応する遷移を1本ずつ書き、最後に min を取れば完成です。

区間を重ならないように選んで個数を最大にする問題なら、貪欲法が使えます。終了時刻の早い順に見て、選んだ区間と重ならないものを採ります。 重みの合計を最大にする問題では、この選び方で合計が最大になるとは限りません。

交換論法では、最適解の最初の区間を貪欲法で選んだ区間に置き換えても、実行可能性と個数が保たれることを示し、残りの区間に同じ議論を繰り返します。 目的と証明の対応はJeff Ericksonの教科書4.2節を参照してください。

分割統治で再帰関係を立てたら、マスター定理の条件を確認します。T(n) = aT(n/b) + f(n) では a ≥ 1、b > 1 とし、f(n) を n^(log_b a) と比べます。

f(n) = Θ(n^(log_b a)) は定理が使える場合です。「多項式的な差がないから使えない」と判断してはいけません。f(n) が多項式的に大きいときは正則条件も要ります。十分大きいnで af(n/b) ≤ c f(n) となる定数 c < 1 があるかどうかです。

どの条件にも入らなければ、再帰木の展開や置換法に切り替えます。条件の一覧はニューヨーク大学のマスター定理の講義ノートでも確認できます。

メモ化再帰とボトムアップDPを比べるなら、同じ状態と遷移を扱っているか、計算順序が依存関係を満たしているかを見てください。どちらも、部分問題の定義と依存関係が決まらないうちは書けません。

計算量クラスと NP 完全性

P、NP、NP困難、NP完全の定義と関係、SAT のクック・レビン定理、3-SAT や頂点被覆、ハミルトン閉路、部分和といった代表的な NP 完全問題、多項式時間帰着。これらを学ぶときは帰着の向きに注意します。

A が NP 困難だと示すには、既知の NP 困難問題 B から A への多項式時間帰着（B ≤_p A）を作ります。逆向きに A から B への帰着を作っても、A の困難性は出ません。証明の冒頭に、どの問題からどの問題へ帰着するかを書いてください。

帰着で示すことは二つです。一つは、変換結果のサイズが元の入力サイズの多項式で抑えられ、変換自体も多項式時間で計算できること。もう一つは、B の YES インスタンスと A の YES インスタンスが対応する同値性です。

前者だけ書いて同値性を省いた答案や、変換の手順を示さず「明らかに多項式時間」と書いた答案では、帰着の条件を確かめられません。同値性は「B が YES ならば A が YES」と「A が YES ならば B が YES」を別々に示します。

クック・レビン定理などを前提に具体的な帰着を練習するときも、「3-SAT から頂点被覆への帰着」「3-SAT から独立集合への帰着」のように、変換と同値性を一つずつ書きます。近似アルゴリズムが出たら、対象問題の条件と近似比の定義を確認しましょう。

文字列アルゴリズム

KMP 法、ボイヤー・ムーア法、ラビン・カープ法（ローリングハッシュ）、接尾辞配列、接尾辞木、最長共通部分列、編集距離（DP と重なります）。どれも、入力する文字列それぞれの長さを区別して操作を数えます。

KMP の失敗関数（border function）が記録するのは、パターンの各位置までで、真の接頭辞かつ真の接尾辞であるものの最長の長さです。 パターン長をmとすると、構築の二重ループが実際には償却 O(m) で済むことを、償却解析で示します。

ラビン・カープ法では、何をランダムに選ぶのか、ハッシュが一致したあと文字列を照合するのかを区別します。法pを素数にしただけでは、衝突確率は1/pになりません。

例を一つ挙げます。異なる文字を0以上p未満の異なる整数に符号化し、長さmが同じで内容の異なる2つの文字列を固定して、多項式として評価する方式です。基数を有限体F_pから一様に選べば、衝突確率は高々 (m−1)/p。差の多項式は零でなく次数が高々m−1なので、根も高々m−1個しかありません。

一致した候補を1文字ずつ照合すれば誤一致は除けますが、その照合時間も計算量に含めます。仮定と証明はMartin Marešのハッシュ関数の講義ノートにあります。

接尾辞配列の計算量は構築法で変わります。比較のたびに接尾辞を先頭から照合する素朴なソートなら最悪 O(n² log n)。SA-ISなら、文字の整数表現と値域などの条件の下で O(n) です。どの構築法が要り、入力に何を仮定するかは、志望研究科の問題で確かめてください。

オートマトンと正規言語

決定性有限オートマトン（DFA）、非決定性有限オートマトン（NFA）、正規表現、文脈自由文法、プッシュダウンオートマトン、チューリング機械は、表せる言語と計算の仕組みがそれぞれ違います。

NFA から DFA への部分集合構成法（subset construction）や、正規表現と NFA の等価性（トンプソンの構成法）を説明するときは、変換の前後で同じ語を受理することを確かめます。

正規言語のポンピング補題はこう述べます。ある整数p ≥ 1が存在し、その正規言語に属する長さp以上の任意の語wに対して、|xy| ≤ p、|y| ≥ 1 を満たす分解w = xyzが存在し、すべての整数i ≥ 0でxyⁱzが言語に属する。量化の順は ∃p ∀w ∃(x,y,z) ∀i です。

言語が正規でないと示す証明は、「ある言語 L が正規だと仮定し、ポンピング長 p の存在を仮定し、L の中から長さ p 以上の文字列 w を一つ選び、上の長さ条件を満たすすべての分解 w = xyz に対し、xyⁱzが言語に属さなくなるiを示す」という流れです。都合のよい分解を一つ選んだだけでは、すべての分解についての主張になりません。

文脈自由文法では、生成される言語を調べます。曖昧性を示すなら、同じ語に異なる最左導出があることを確かめます。停止問題の決定不能性を対角線論法で示す場合は、仮定した判定器の入出力と、そこから組み立てる機械の動作を混ぜないでください。