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

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

この分野が出題される大学・研究科

アルゴリズムを主要試験科目に据えているのは、情報系の主要研究科のほぼ全てです。東京大学 情報理工学系研究科 電子情報学、九州大学 システム情報科学府 情報科学（数学系）、東京科学大学 工学院 情報通信系、電気通信大学 情報理工学研究科 機械知能システム、東北大学 工学研究科 電気・情報工学 基礎・専門。注意したいのは、出題形式が研究科ごとにかなり違うことです。東大は擬似コードと計算量の論証を一体で書かせる形式、九大は具体的なグラフ問題の手順を逐次記述させる形式、東京科学大は離散数学と組み合わせた論証問題が中心、電通大と東北大は計算機関連科目の一部としてやや基礎寄りに出題される、という傾向があります。たとえば「擬似コードを書く練習だけしておけば足りる」という戦略は東京科学大では成立しにくく、逆に「離散数学の証明問題を中心に詰める」という戦略は九大では空振りしやすい。志望研究科の出題範囲と形式は、想像ではなく必ず最新の募集要項と公開過去問で直接確認してください。

学部段階で固めておくべき基礎

アルゴリズムの演習に入る前に、最低限ここまでは詰めておく必要があります。逆に言えば、ここが曖昧なまま過去問演習に入ると、解説を読んでも「なぜその計算量になるのか」が腹落ちせず、2周目以降の効率が大きく落ちます。

• 離散数学：集合・写像、関係（同値関係・順序関係）、命題論理、述語論理、数学的帰納法。グラフ理論の語彙（次数・連結・木）も含む
• 計算量のオーダー記法：O・Ω・Θ の定義と差、最悪・平均・償却計算量の使い分け。マスター定理の適用条件まで含めて言える状態
• 再帰と帰納法：再帰関数の正当性を帰納法で示せる、再帰関係を漸化式に翻訳できる
• データ構造の基本：配列・連結リスト・スタック・キュー・木・グラフの内部表現と各操作の計算量
• 確率と組み合わせ：期待値の線型性、二項係数、ハッシュ法の衝突確率や乱択アルゴリズムで使う
• 形式言語の基礎：正規表現とオートマトンの対応、文脈自由文法の概念。情報系上位校で必須

ここが怪しい場合は、アルゴリズムの演習に入る前に1〜2週間を集中的に確保し、学部1〜2年次の離散数学・論理学の章末問題を埋めてから戻ってきた方が、結果的に近道になります。特に「再帰関係の漸化式 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 について矛盾を導く」という流れになります。ここで「自分が分解を選ぶ」と勘違いした瞬間に証明が崩壊します。文脈自由文法の問題では、与えられた文法から導出される言語の特定や、曖昧性の判定（複数の最左導出が存在することを示す）が頻出です。チューリング機械では停止問題の決定不能性の証明（対角線論法）が出題されることがあり、自己参照の構造を答案で正確に追えるかが分かれ目になります。

出題大学ごとの色の違い

同じアルゴリズム科目でも、研究科が違えば「採点者が見ているもの」が違います。志望先によって演習の比重の置き方が変わります。

• 東大 情報理工 電子情報学：擬似コードと計算量論証を一体で書かせる形式が中心。計算量はマスター定理での導出を要求してくる。乱択アルゴリズムや近似アルゴリズム（頂点被覆の2近似など）の出題も増えており、確率論的解析の答案作法に慣れておく必要がある。
• 京大 情報学（情報学研究科）：論理過程を最後まで書かせる文化が強く、途中式や定義の明示を省略すると配点を取り切れない。動的計画法の漸化式の正当性証明（帰納法による）まで踏み込んで問われることがある。
• 九大 システム情報科学府 情報科学（数学系）：具体的なグラフを与えて手順を逐次記述させる形式が多く、定型アルゴリズムの実行トレース能力が問われる。ダイクストラ法・最小全域木の手順を表で示せるかが分かれ目。
• 東京科学大 工学院 情報通信系：離散数学と組み合わせた論証問題が中心で、計算量理論や NP 完全性の帰着構成が頻出。問題集ベースの定型対策に頼ると本番でズレが出る研究科の代表格。
• 東北大 工学研究科 電気・情報工学 基礎・専門：計算機関連科目の一部としてやや基礎寄りに出題され、ソート・探索・基本データ構造の理解を満遍なく問う傾向。極端な難問は少ないが、形式不備の減点は厳しめ。
• 電通大 情報理工 機械知能システム：機械系と情報系の境界にある研究科で、アルゴリズムは基礎的なソート・探索・グラフが中心。専門深度よりも幅広く正答することが効く。
• 奈良先端大 情報科学：選択問題の中にアルゴリズム・離散数学のセットが組まれることがあり、形式言語・オートマトンと組み合わせた出題が見られる。

外部生がつまずく構造的な理由

アルゴリズムで外部生が苦戦するのは、能力差ではなく構造的な要因が大きいです。情報系学部で系統的にアルゴリズムとデータ構造の演習を積んできた内部生に対して、他分野出身の外部生は「擬似コードの書き方の流儀」自体が違うところからスタートします。配列のインデックスを 0 始まりにするか 1 始まりにするか、ループの終了条件をどう書くか、再帰の停止条件をどこに置くかといった所作は、講義と演習で繰り返し添削されて初めて身につくもので、独学で本だけ読んでも体に入らない。結果として、本番の答案で擬似コードのインデックス境界がずれて配列外参照を起こす、あるいはループ不変条件を書き忘れて正当性証明が成立しない、といった失点が積み重なります。

二つ目は、計算量の論証で「どこまで書けば十分か」の感覚が掴めないこと。内部生は学部の演習レポートで「O(n log n) です」だけでは丸がつかない経験を何度もしているので、論証の粒度を肌で知っています。外部生は教科書の例題を読んでも、教科書では結論だけが書かれている箇所が多いため、答案で再現すべき論証の量を見誤ります。実際の合格答案は教科書よりも一段詳しく、漸化式・マスター定理の適用・境界条件の確認、までを明示的に書く必要があります。これは情報差の問題なので、過去問の解答パックで「合格答案の粒度」を一度キャリブレーションするのが最短です。

三つ目は、NP 完全性と計算量理論の答案作法。これらは学部の標準カリキュラムでも扱いが薄く、内部生でも演習量に差が出る領域です。多項式時間帰着の方向、帰着の正当性証明の構造、ポンピング補題の論理構造、こうした抽象的な論証は、独学では「読めるけど書けない」状態で止まりがちです。答案として再現するには、過去問で出題された帰着構成を3〜5問、自分の手で書き写してから類題を解く、という地道な訓練が必要になります。

残り月数別の演習ロードマップ

アルゴリズム対策に使える月数別に、現実的に効くやり方を整理します。すべての月数で共通するのは「過去問1年分を最初に時間を計って解き、現状を可視化する」ことです。これを飛ばすと、自信のある論点に時間を使いすぎ、NP 完全性やオートマトンといった不慣れな論点を後回しにする悪い循環に入ります。

残り6か月の場合

最初の2か月は学部教科書（CLRS または藤原本）の章末問題で、ソート・探索・基本データ構造・グラフアルゴリズムの計算量解析を一通り埋めます。難しい論文や応用書を新たに買うより、標準教科書を1冊通読する方が結果として速い。次の2か月で公開過去問を年度ごとに解き、論点別の弱点と配点比重を可視化します。動的計画法と NP 完全性は短期間で身につきにくいので、この段階で5〜10問の典型例を手で解いて頭に入れておく。最後の2か月は弱点論点の章末問題と過去問演習を交互に回し、答案を時間制限付きで書く訓練に切り替えます。オートマトン・形式言語が範囲に含まれる研究科の場合、この最後の2か月の前半でホップクロフトの教科書から正規言語と文脈自由言語の章を集中して仕上げると得点源になります。

残り3か月の場合

過去問1年分を時間を計って解き、論点別の得点率を可視化します。最初の1か月は弱点論点の教科書復習に充て、特に動的計画法と NP 完全性のどちらかが弱い場合はそこに時間を集中します。次の1か月で過去問を直近5年分2周し、擬似コードと計算量論証を答案として書く訓練を反復。最後の1か月は答案の作法（部分問題の定義、漸化式の境界条件、データ構造の選択明示、計算量の論証粒度）と時間配分の調整に充てます。離散数学の基礎（集合・写像・命題論理・帰納法）は毎日30分程度の固定枠を確保し、論証の体力を切らさないことが重要です。

残り1か月の場合

この段階では新規論点に手を広げるより、既に解いた過去問の答案を「採点者が読める形」に書き直す方が得点を伸ばします。各設問について、データ構造の選択明示・漸化式の境界条件・計算量の論証・擬似コードのループ不変条件、の4点を必ず答案に残す訓練を反復します。時間が足りない論点は、配点の取りやすい設問（基本ソートの計算量・グラフの DFS/BFS のトレース・正規表現と NFA の変換）を確実に取りにいく戦略に切り替え、最大流や接尾辞配列のような難問の完答は捨てる判断も必要です。NP 完全性は出題されたら帰着の方向だけは絶対に間違えない、という最低ラインを死守してください。

推奨教科書・参考書

アルゴリズムの教科書選びは、新しい本を増やすより1冊を完走することの方が大事です。以下は「これだけ揃えれば十分」という基準で、各書の使いどころも併記します。

• 標準：Cormen-Leiserson-Rivest-Stein『Introduction to Algorithms（アルゴリズムイントロダクション）』（近代科学社） — 事実上の標準教科書。網羅性と論証の厳密さで他書を圧倒する。章末問題の質が高く、東大・東京科学大志望者は最低でも主要章を完走しておく。
• 日本語入門：藤原暁宏『アルゴリズムとデータ構造』（森北出版） — CLRS の前段として最適。擬似コードと計算量の論証が日本語でコンパクトにまとまっていて、外部生の最初の1冊に向く。
• 古典：石畑清『アルゴリズムとデータ構造』（岩波講座 ソフトウェア科学） — 日本の情報系の標準書の一つ。記述が簡潔で、辞書的に参照する用途で手元に置く。
• 実装重視：Sedgewick『Algorithms』 — 実装に踏み込んだ説明が手厚く、擬似コードと実コードの橋渡しに向く。九大のような手順記述型の研究科で実行トレースの感覚を磨くのに使える。
• 計算量理論：Garey-Johnson『Computers and Intractability』 — NP 完全性と帰着の標準。代表的 NP 完全問題のリストと帰着のテクニックを参照用に持っておくと答案の幅が広がる。
• オートマトン：Hopcroft-Motwani-Ullman『Introduction to Automata Theory, Languages, and Computation』 — 正規言語・文脈自由言語・チューリング機械の標準教科書。東京科学大・東大の論証系問題に必須。
• 演習補強：『プログラミングコンテストチャレンジブック（蟻本）』 — 動的計画法とグラフアルゴリズムの典型問題が大量に載っていて、演習量の底上げに使える。試験対策の主軸には置かないが、副教材として有効。

院試hub の解答パックでカバーされる範囲

院試hub ではアルゴリズムを主要試験科目とする情報系研究科について、年度別の解答パックを整備しています。東大 情報理工 電子情報学、九大 システム情報科学府 情報科学（数学系）、東京科学大 工学院 情報通信系、東北大 工学研究科 電気・情報工学 など、複数研究科を比較しながら擬似コード型・論証型・手順記述型の答案作法の違いを学べる構成です。

各解答PDFは年度別に整理されていて、各設問に方針・典型失点・部分点の置き所を併記しています。使い方の推奨は次の順序です。まず公式PDFの問題を自力で時間を計って解く。次に解答パックの「方針」だけ先に読み、自分が立てた漸化式や帰着の方向が一致しているかを確認する。最後に答案全体を突き合わせ、計算量の論証粒度・部分問題の定義・データ構造の選択明示など、答案作法の不備を直していく。3周目以降は時間配分の最適化と、難問の捨て判断の訓練に使えます。1年分を解くごとに、自分の弱点が「論点理解」「答案作法」「時間配分」のどれに分類されるかを記録しておくと、残り月数別ロードマップの調整に役立ちます。

公開前に必ず最新の公式募集要項・公式過去問ページで試験科目・出題範囲を確認してください。