豊橋技科大 工学研究科 情報・知能工学専攻基礎科目 第1次募集 院試 解答例・解説

方針

この問題は、同じ対角化を三つの場面で使い回す構成である。固有値と固有ベクトルを求めたら、微分方程式では指数関数、漸化式では固有値のべき乗に置き換わる。

初期値の扱い

微分方程式では $P^{-1}x(0)$ を必ず計算する。ここが $(1,1)^{\mathsf T}$ になるため、両方の固有成分が残る。一方、数列の初期値 $(1,2)^{\mathsf T}$ は固有ベクトル $e_1$ と一致するので、$\lambda_1=3$ の成分だけが残る。

検算

$A(1,2)^{\mathsf T}=(3,6)^{\mathsf T}=3(1,2)^{\mathsf T}$ なので、数列の答え $(a_n,b_n)=(3^{n-1},2\cdot 3^{n-1})$ は漸化式にそのまま代入して確認できる。

場合分けの軸

袋の問題では、最初に袋Aから何色が出たかでBから引く個数が変わる。ここを先に分ければ、あとは超幾何分布または単純な条件付き確率になる。Bから2個引く場合は順序を考えず、$\binom72$ を分母に置くと計算が安定する。

条件付き確率の注意

「Bから取り出された玉がすべて青」という条件は、Aから赤だった場合と白だった場合で意味が違う。赤ならBから2個、白ならBから1個なので、同じ「すべて青」でも確率は $\binom52/\binom72$ と $5/7$ に分かれる。

連続分布の検算

密度関数は左右対称な二次式 $6x(1-x)$ で、区間 $[2/5,3/5]$ は中心 $1/2$ のまわりに対称である。答えが $37/125\approx0.296$ となり、区間幅 $0.2$ に対して密度の中心値 $1.5$ を掛けた概算 $0.3$ に近いので、桁の検算として自然である。

C言語の型

`malloc` が返すのは汎用ポインタであり、ここでは `struct Node*` として受ける。確保するサイズはポインタのサイズではなく構造体本体のサイズなので、`sizeof(struct Node)` と考える。`sizeof(struct Node*)` にすると、ノード全体を置く領域として不足する。

再帰呼び出しの数え方

挿入関数は、目的位置に到達した後、最後に `root` が空である呼び出しでもう一度実行される。このため、深さ $d_i$ の位置に入るノードの呼び出し回数は $d_i$ ではなく $d_i+1$ である。

計算量

二分探索木は、形が平衡に近ければ高さが $\log N$ 程度で済む。しかし、入力順が悪いと高さが $N$ 程度になり、探索も挿入も線形探索と同程度まで悪化する。この問題では、図を選ぶだけでなく、木の形が計算量を決めることまで押さえるのが採点上重要である。