東京科学大 情報理工学院 情報工学系 専門科目（情報工学） 2025年度 院試 解答例・解説

微分の確認

$(\alpha+\sqrt{x})^2$ は展開してから微分すると符号ミスが減る。 偏導関数では $x$ と $y$ のどちらを固定しているかを明確にし，混合偏導関数が一致することも確認できる。

媒介変数表示の面積

曲線と $x$ 軸で囲まれる面積は $\int y\,dx$ で求める。 ここでは $y(t)=2\sin t$ と簡単になり，さらに $x'(t)=4\sin^2t$ なので， 標準積分 $\int_0^\pi\sin^3t\,dt=4/3$ に帰着する。

係数ベクトルで判定する

$v_1,v_2,v_3$ が一次独立であるため，それらを基底のように扱って係数だけを見ればよい。 3 次元に 4 本ある時点で従属と分かる b) を，行列式計算で無理に処理しないのが効率的である。

二変量正規分布

正規分布では，線形結合の平均・分散は共分散行列から直接読める。 条件付き分布の平均は $\operatorname{Cov}(X_1,X_2)/\operatorname{Var}(X_2)\cdot x_2$， 分散は $\operatorname{Var}(X_1)-\operatorname{Cov}(X_1,X_2)^2/\operatorname{Var}(X_2)$ である。

採点の置き所

微分では途中の一次偏導関数を書き，二次偏導の符号を確認する。 面積問題では，媒介変数表示のまま $\int y(t)x'(t)\,dt$ に移す理由を書く。 線形独立性は，元のベクトルではなく係数ベクトルへ移せることを明記すると短く正確に処理できる。

検算

面積 $32/3$ は正であり，$y(t)=2\sin t$ が $0<t<\pi$ で正であることと整合する。 条件付き分散 $1$ は元の $\operatorname{Var}(X_1)=2$ より小さく，共分散による情報を反映している。

正規文法の読み替え

右線形文法は有限オートマトンと同じ情報を持つ。終端だけで終わる規則は受理状態へ入る遷移， 終端と非終端が続く規則は次状態への遷移と考えると，反復や連結の文法を作りやすい。

スターと連結

$L^\ast$ では空語を必ず含める必要がある。さらに 1 語を作り終えた後に開始記号へ戻す規則を入れる。 一方，$L_1L_1$ では 1 個目と 2 個目の生成過程を混ぜないよう，非終端記号をコピーして接続するのが安全である。

言語族の判定

正規性を否定するときはポンピング補題や単項言語の性質を使う。 文脈自由性を否定するときは，三つのブロック長を同時に一致させる形へ準同型や逆準同型で落とすのが定石である。

採点の置き所

文法構成問題では，開始記号，受理に対応する終端規則，反復に戻る規則をはっきり分ける。 DFA の補集合は，遷移を全定義にしてから受理状態を反転する必要がある。 言語族分類は記号だけでなく，正規，文脈自由，非文脈自由の根拠を一文ずつ添えると安定する。

典型ミス

$L^\ast$ が空語を含むことを忘れると，スターに関する空欄と包含判定を同時に落とす。 補集合 DFA で沈み状態を入れないまま受理状態だけを反転すると，未定義遷移の語を正しく扱えない。

最短経路は二項係数

最短経路では，横方向の移動回数と縦方向の移動回数が固定される。 したがって「何番目に横へ動くか」を選べばよく，$\binom{W+H}{W}$ に帰着する。 通行止めを含む問題では，全体から「その点を通る経路」を引くのが最も確実である。

DP 配列の添字

配列が $a[i][j]$ の順で書かれているため，第一添字が縦方向，第二添字が横方向である。 $a[i][j]=a[i][j-1]+a[i-1][j]$ と書けるかが要点で，ここを逆にすると返す位置 $a[h][w]$ まで連鎖的に誤る。

再帰で全経路を数えるときの訪問済み判定

非最短経路を含めると，単純な二項係数では数えられない。 各再帰呼び出しが現在位置と過去位置へのポインタを持つことで，探索木の各枝ごとに異なる訪問履歴を表せる。 ただし，現在のノード自身と比較すると必ず一致してしまうので，親ノードから順に調べる点が重要である。

printf の位置による違い

32 行目直後では，再帰に入る前の候補座標が印字対象になる。 34 行目直後では，再帰呼び出しが終わった後に印字されるため，深さ優先探索で最初に戻ってきた枝の座標が出る。 どちらも条件は $t<5$ なので，印字されるのは最初の 4 回だけである。

採点の置き所

格子経路では，最短経路，通行止め付き最短経路，自己交差を避ける一般経路を区別して解く。 DP の空欄は配列の意味を先に決め，境界条件，内部遷移，戻り値の順に埋める。 再帰プログラムの空欄は，座標，親ノードポインタ，訪問済み判定，範囲外判定を分けて読むと一貫する。

検算

通行止めなしの経路数から，通行止めを通る経路数を引いた値が正で全体数より小さいことを確認する。 $N=3$ の全経路数 $184$ は，最短経路数より大きくなるはずなので，最短経路の二項係数だけで答えていないかを確認できる。 印字位置の問題は，深さ優先探索の最初の数手だけを手で追うと出力順を検算しやすい。