院試 アルゴリズムの出題傾向と対策

アルゴリズムは情報系の院試で必出の科目であり、配点の比重も大きい。学部のアルゴリズムとデータ構造の標準範囲から外れる出題はほとんどないにもかかわらず、合格者と不合格者の差は明確に出ます。理由は単純で、この科目は「計算量解析」と「実装（擬似コード）」という二つの異なるスキルを同じ答案の中で要求するからです。実装を書ける受験生は計算量の論証で詰まり、計算量を式で論ずる受験生は擬似コードのインデックス境界でバグを残す。どちらか片方だけでは合格答案にならない構造になっていて、これが外部生にとっての最大のハードルです。本記事は、アルゴリズムを主要試験科目とする情報系研究科の出題傾向と頻出パターン、答案で失点しやすい論点を整理した実務マップです。

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

昇順配列 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) を見てマスター定理の3ケースのどれに該当するかを判断する」ことは、ソートと分割統治の問題で毎回出てくるので、ここでつまずくと演習量が一気に増えます。

論点別に見る出題と失点

アルゴリズム試験の頻出論点はおおむね6つに整理できます。それぞれに固有の答案作法と典型失点があるので、1論点ずつ独立に押さえた方が頭に残ります。

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

頻出は、クイックソート、マージソート、ヒープソート、基数ソート、二分探索、ハッシュ法。出題の中心は「アルゴリズムが書けるか」ではなく「計算量を論証として書けるか」です。最大の失点源は、計算量だけを「O(n log n) です」と書いて論証を省略してしまうこと。これでは部分点を取り切れません。クイックソートの平均計算量を問われたら、ピボット選択の確率分布を仮定したうえで再帰関係 T(n) = T(k) + T(n-k-1) + O(n) を立て、期待値の線型性を経由して O(n log n) を導く流れを答案に残す必要があります。マージソートなら T(n) = 2T(n/2) + O(n) からマスター定理のケース2で Θ(n log n) を出す。ここで「マスター定理の適用条件（f(n) と n^(log_b a) の比）を確認する」一行を省くと、減点対象です。

安定性を問われたときに「クイックソートは安定でない」と一行書くだけで終わらせず、なぜ安定でないかの反例（同じキーを持つ要素のペアで順序が逆転する具体例）を一つ示せると確実です。基数ソートやバケットソートのような線形時間ソートでは、入力に対する仮定（整数で値域が O(n) など）を答案の頭に明示しないと、「O(n) ソートが存在するから比較ソートの下界 Ω(n log n) と矛盾する」という誤った印象を採点者に与えかねません。ハッシュ法では、チェイン法とオープンアドレス法の計算量を負荷率 α の関数で書き分け、「α が定数なら期待 O(1)」と書くときに前提（一様ハッシュ仮定）を必ず明示してください。二分探索木では、平衡性が保証されないと最悪 O(n) に劣化することを答案に残し、AVL 木・赤黒木・B 木のいずれかで O(log n) を保証する流れを書きます。

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

頻出は、DFS と BFS、ダイクストラ法、ベルマン・フォード法、ワーシャル・フロイド法、最小全域木（クラスカル法・プリム法）、最大流（フォード・ファルカーソン法）。失点の最大の発生源は、グラフの表現方法（隣接リストか隣接行列か）を明示しないまま計算量を書いてしまうことです。ダイクストラ法の計算量は、配列で実装すれば O(V²)、二分ヒープなら O((V+E) log V)、フィボナッチヒープなら O(E + V log V) と、データ構造の選択で変わります。これを答案に書かないと、採点者はどの計算量を期待されているのか判別できません。

ベルマン・フォードを使う場面（負辺がある）とダイクストラを使う場面（非負辺）の区別、ワーシャル・フロイドの三重ループの中で k を最外周に置く理由（部分問題の単調性）、これらも頻出の論証ポイントです。「k を内側に置いたら答えが合わない」のは単なる実装ミスではなく、動的計画法の部分問題の依存関係の問題なので、答案では「dp[k][i][j] が dp[k-1][·][·] にのみ依存する」ことを一言示すと完璧です。最小全域木でクラスカルを選んだ場合は Union-Find の必要性とその経路圧縮・ランク合併によるほぼ O(α(V)) の計算量、プリムを選んだ場合は優先度付きキューの操作回数、を答案で書き分けてください。最大流の問題では、フォード・ファルカーソンが擬似多項式時間であること、エドモンズ・カープが O(VE²) で多項式時間になる理由（BFS による最短増加路選択）、を区別できるかが上位校では問われます。最大流・最小カット定理を使った双対性の論証も、東大・東京科学大の過去問では定期的に登場します。

動的計画法と分割統治

頻出は、ナップサック問題、最長共通部分列、編集距離、行列連鎖積、ビタビアルゴリズム、区間スケジューリング。動的計画法で最も多い失点は、部分問題の定義が曖昧なまま漸化式を立てて、答案が後半で破綻することです。「dp[i][j] = ナップサックの容量 j まで使って最初の i 個から得られる最大価値」のように、配列の意味を1行の自然言語で書き添える。これは採点者のためというより、自分が答案の後半で混乱しないための保険でもあります。

遷移式 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 側を進める）を答案に分けて書くと採点者の心象が良くなります。編集距離では3つの操作（挿入・削除・置換）に対応する遷移をそれぞれ書き、最後に min を取る形を残します。区間スケジューリングのような貪欲法が成立する問題でも、なぜ貪欲が最適性を持つかの交換論法（exchange argument）を一行入れると論証として閉じます。

分割統治では、再帰関係を立てた後にマスター定理を適用する流れが定型で、ここで「マスター定理の3ケースのうちどれに該当するか」の判定理由（漸近的比較）を一行入れないと、最終結果が同じでも論証として不完全と見なされます。マスター定理が適用できないケース（f(n) が n^(log_b a) と多項式的に異ならない場合など）では、再帰木を直接展開する手法に切り替える判断も必要です。動的計画法と分割統治を「再帰的部分問題の解き方」として共通の枠で捉えると、遷移の正当性証明がしやすくなります。メモ化再帰とボトムアップDPの等価性も、上位校では概念を問う出題の対象になります。

計算量クラスと NP 完全性

頻出は、P、NP、NP困難、NP完全の定義と相互関係、SAT のクック・レビン定理、3-SAT・頂点被覆・ハミルトン閉路・部分和などの代表的 NP 完全問題、多項式時間帰着。最大の失点は、帰着の方向を取り違えることです。「ある問題 A が NP 困難であることを示すには、既知の NP 困難問題 B から A への多項式時間帰着（B ≤_p A）を構成する」が原則であって、逆向き（A から B への帰着）を作っても A の困難性は出ません。この方向は試験会場の緊張下で取り違える典型ポイントなので、答案の最初に「ここでは B から A への帰着を構成する」と一文書く癖をつけてください。

帰着の構成では「入力サイズが多項式オーダーであること」と「B の YES インスタンスと A の YES インスタンスが対応すること（同値性）」の両方を示す必要があります。前者だけ示して後者を省略する答案、あるいは前者を「明らかに多項式時間」と一言で済ませて減点される答案、はどちらも頻発します。同値性の証明は「B が YES ならば A が YES」「A が YES ならば B が YES」の双方向を分けて書くのが安全で、片方向だけだと採点者は構成の正当性を確認できません。クック・レビン定理の証明そのものを書かせる出題は少なく、定理を所与として「3-SAT から頂点被覆への帰着」「3-SAT から独立集合への帰着」のような具体例を構成させる形式が多いです。近似アルゴリズムの近似比（頂点被覆の2近似、TSP のクリストフィデス法など）も、NP 完全性と組み合わせて出題されることがあります。

文字列アルゴリズム

頻出は、KMP 法、ボイヤー・ムーア法、ラビン・カープ法（ローリングハッシュ）、接尾辞配列、接尾辞木、最長共通部分列、編集距離（DP との重複）。文字列アルゴリズムは情報系上位校でやや専門寄りに出ることが多く、KMP の失敗関数（border function）の構築が O(m) で済む理由を答案で説明できるかが分かれ目になります。失敗関数の定義（パターンの各位置までの最長の真の接頭辞かつ真の接尾辞の長さ）を一行書き、構築の二重ループが実際には償却 O(m) で済むことを摂動論的に示せれば十分です。

ラビン・カープでは、ハッシュの衝突確率の見積もりが論点になることが多く、「期待計算量」と「最悪計算量」を区別して書く必要があります。法 p を素数に取った場合の衝突確率 1/p を経由して期待値を出す流れは、確率論的解析の典型例として答案に書ける状態にしておきます。接尾辞配列は構築の計算量（素朴 O(n² log n)、SA-IS で O(n)）の差を問われることがあり、どこまでの知識を答案に書くかは志望研究科の過去問で確認してください。

オートマトンと正規言語

頻出は、決定性有限オートマトン（DFA）、非決定性有限オートマトン（NFA）、正規表現、ポンピング補題、文脈自由文法、プッシュダウンオートマトン、チューリング機械。NFA から DFA への部分集合構成法（subset construction）の手続き、正規表現と NFA の等価性（トンプソンの構成法）、ポンピング補題による「ある言語が正規でないことの証明」、これらは情報系の試験で繰り返し出ます。

ポンピング補題の使い方で最も多い失点は、補題の論理構造（∀ ∃ ∀ ∃）を取り違えて、誤った「分解」を選んでしまうことです。証明は「ある言語 L が正規だと仮定し、ポンピング長 p の存在を仮定し、L の中から長さ p 以上の文字列 w を一つ選び、補題が保証する任意の分解 w = xyz について矛盾を導く」という流れになります。ここで「自分が分解を選ぶ」と勘違いした瞬間に証明が崩壊します。文脈自由文法の問題では、与えられた文法から導出される言語の特定や、曖昧性の判定（複数の最左導出が存在することを示す）が頻出です。チューリング機械では停止問題の決定不能性の証明（対角線論法）が出題されることがあり、自己参照の構造を答案で正確に追えるかが分かれ目になります。