令和 4 年度
千葉大学先進科学プログラム入学者選考課題
課題論述
解答例

情報

1
□
（出題意図）ゲーム木探索のミニマックス法を題材として、アルゴリズムを考え、再帰的なプログラムで実現する能力を問う。
問１
コンピュータ 1 回目
1

2

人間 1 回目

コンピュータ 2 回目

コンピュータの勝敗

1

3勝ち

22勝ち

31勝ち

12勝ち

2

1勝ち

3負け

1
3

1勝ち

2負け

問2
kc(k)の戻り値

kh(k)の戻り値

N-1

-1

N-1

1

N-2

1

N-2

-1

N-3

1

N-3

-1

N-4

1

N-4

-1

問3
int c(int k){
int i;
if ((k >= N) || (k < 0)) {return 0;}
if (k >= N-4) {if (k == N-1) {return -1;} else {return 1;}}for (i = 1; i <= 3; i++) {if (h(k+i) == 1) {return 1;}}
return -1;}

int h(int k){
int i;
if ((k >= N) || (k < 0)) {return 0;}
if (k >= N-4) {if (k == N-1) {return 1;} else {return -1;}}
for (i = 1; i <= 3; i++) {if (h(k+i) == 1) {return -1;}}
return 1;}

2□
問 1 再帰関数呼び出しと漸化式の関係を問う課題である．位置(i,j)のマス目までの経路数をroute[i][j]とする。まず S である位置(0,0)までの経路は 1 つしかない。すなわち，route[0][0]=1である。次に，最上行の位置(0,j),j=1,2,…,W-1 については，左隣(0,j-1)からの経路しかないため，経路数は route[0][j]= route[0][j-1]と再帰的に与えられる。最左列の位置(i,0),i=1,2,…,H-1も同様に，経路数は route[i][0]=route[i-1][0]と与えられる。上記以外の経路数は，route[i][j]= route [i][j-1]+ route[i-1][j]と再帰的に与えられる。なぜならば，位置(i,j)のマス目に到達するには，左隣(i,j-1)あるいは上隣(i-1,j)のマス目からの経路しかなく，位置(i,j)までの経路の総数は，それらの和になるからである。
問 2 繰り返し文を用いて，経路数 route[i][j]を，(i,j)=(0,0),(0,1),…,(1,0),(1,1),…,(H-1,W1)の順に計算していく。効率的な計算のための代表的なアルゴリズムの一つである，動的計画法の例になっている。
#include <stdio.h>#define H 4#define W 7
int main(void) {int route[H][W]={0};int i, j;route[0][0] = 1;
for(i=1; i<H; i++)route[i][0] = route[i-1][0];for(j=1; j<W; j++)route[0][j] = route[0][j-1];
for(i=1; i<H; i++)for(j=1; j<W; j++)route[i][j] = route[i][j-1] + route[i-1][j];printf("経路の数:%d¥n", route[H-1][W-1]);
return 0;}

問３ 問 1 の再帰関数呼び出しを用いたプログラムでは，同じ引数に対する関数計算を何度も重複して実行しているため遅い。一方，動的計画法を用いたプログラムでは，経路数 route[i][j]を順に一度だけ計算するだけであるから，重複がなく，高速になる。

問 4 あるマス目の通行止めが左隣にあるとき，そのマス目に到達するまでの経路数は，上隣のマス目までの経路数と同じである。なぜならば，左隣が通行止めであるから，上隣から来るしかないからである。すなわち，位置(i,j)のマス目までの経路の数 route[i][j]は，route[i][j]=route[i-1][j]と再帰的に求めることができる。同様に，上隣が通行止めであれば，route[i][j]=route[i][j-1]と求めることができる。左隣や上隣に通行止めがなければ，問 1 や問 2 で考えたように，経路の数は，route[i][j]=route[i-1][j]+route[i][j-1]と求めることができる。通行止めのマス目のroute[i][j]の値を-1 とすると，上の 3 つの再帰式はまとめて次のように書くことができる。ただし，max(x, y)は引数x, yのうち，大きい方を返す関数とする。
route[i][j]=max(route[i-1][j],0)+max(route[i][j-1],0)#include <stdio.h>#define H 4#define W 7
int max(int x, int y){if(x>y)return x;
else
return y;}
int main(void) {int route[H][W]={0};int i, j;route[1][2] = -1; /* 通行止めを-1 で表現 */route[2][4] = -1;
route[0][0] = 1;
for(i=1; i<H; i++)route[i][0] = route[i-1][0];for(j=1; j<W; j++)route[0][j] = route[0][j-1];
for(i=1; i<H; i++)for(j=1; j<W; j++)if(route[i][j]!=-1)
route[i][j] = max(route[i][j-1],0) + max(route[i-1][j],0);
printf("経路の数:%d¥n", route[H-1][W-1]);
return 0;}

3
□
出題の意図
本問は，比較的単純な統計的手法を理解できる数理的読解力，およびそれを実装し計算コストを見積もる実装力を問う問題である。大学で理系分野を学ぶために数理的読解力は言うまでもなく重要な能力であり，それを試すにあたり昨今の情報科学で進展めざましい機械学習に関連するトピックを採用した。また数理的な理解を実際にプログラムとして実現する力（実装力）も重要である。今回は筆記での試験であるので複雑な実装は求めなかった。説明された手法が正確に読解できていれば即座に実装できると思われる。問 3，問 4 は計算問題である。問 3 は考えている確率変数が 1 または-1 しか取らないので，素直に全通り考えることができる。期待値の定義がわかっていれば解ける問題である。問 4 は多少の計算が必要になる。問 3 の結果がうまく活用できるかが鍵となる。
問1
def sim(a, b):s = 0n = len(a)for i in range(n):s += a[i]*b[i]return s
def nearest_neighbor_id(y, X):k, s, m = -1, -1, len(X)for i in range(m):s_ = sim(y, X[i])if i==0 or s_ > s:s = s_k = ireturn k

問2
計算コストは，2𝑚𝑛。二つのベクトルの内積を計算するのがコスト𝑛（要素同士の積が 1，𝑠への加算で 1，それを𝑛回繰り返し2𝑛）。最近傍データを見つけるために，この内積計算を𝑚回繰り返すので，結局2𝑚𝑛。
問32
𝔼[𝑤𝑖,𝑗 ] = 0, 𝔼[𝑤𝑖,𝑗] = 1, 𝔼[𝑤𝑖,𝑗 𝑤𝑖,𝑘 ] = 0

問4𝑑𝑑𝑛𝑛

𝑗=1

𝑗=1 𝑘=1 𝑙=1

1
1𝔼[𝑧⃗1 ∙ 𝑧⃗2 ] = ∑ 𝔼[(𝑢⃗⃗1 ∙ 𝑤⃗⃗⃗𝑗 )(𝑢⃗⃗2 ∙ 𝑤⃗⃗⃗𝑗 )] = ∑ ∑ ∑ 𝔼[𝑢1,𝑘 𝑤𝑗,𝑘 𝑢2,𝑙 𝑤𝑗,𝑙 ]𝑑𝑑𝑑𝑛𝑑𝑛112= ∑ ∑ 𝔼[𝑢1,𝑘 𝑢2,𝑘 𝑤𝑗,𝑘] = ∑ ∑ 𝑢1,𝑘 𝑢2,𝑘 = 𝑢⃗⃗1 ∙ 𝑢⃗⃗2𝑑𝑑
𝑗=1 𝑘=1

𝑗=1 𝑘=1問5
def reduction(y, W):v = []
d = len(W)for i in range(d):s = sim(y, W[i])s /= d**0.5
v.append(s)return v# これはなくても良い

def approximate_nearest_neighbor_id(y, X, Z, W):v = reduction(y, W)
k = nearest_neighbor_id(v, Z)
return k

問6
計算コストは，2𝑑(𝑚 + 𝑛 + 1)。reduction()では𝑛次元ベクトルに対し sim()を𝑑回繰り返すので，(2𝑛 + 2)𝑑（平方根・除算の計算で+2 される）。問 2 の結果から最近傍探索で，2𝑚𝑑。合計して整理す
ると，2𝑑(𝑚 + 𝑛 + 1)。ただし問 5 で，s /= d**0.5 を書かなかった場合は，計算コストは2𝑑(𝑚 + 𝑛)となる。4□
本問の目的は論理演算への理解の確認である。
問 1 関数 d は引数を 2 進数で表したときの各桁の値を下位桁から順に要素として持つリストを返す。関数 e では引数と戻り値を逆にし、リストから数値を返すようにすればいい。

def e(b):x=0while b:x = (x << 1) | b.pop()
return x
別解：python 本来の 2 進数を扱う機能を使ってもよい。
def e(b):return int(''.join((str(_) for _ in reversed(b))), 2)

問 2 関数 t は第 1 引数をしきい値とし、第 2 引数に与えられるリストの内、1 である要素の数を数えるしきい値関数である。ここで、第 2 引数のリストに含まれる要素は 0 と 1 に限る。2 入力論理積はしきい値 2 のしきい値関数である。
def c(x,y):
return t(2,[x,y])

問 3 半加算器を作ればいい。関数 c は論理積であり、関数 v は否定であることから、これらを組み合わせれば半加算器を作ることができる。論理和 t(1,[x,y])も使える。別解は多い。
def a(x,y):
return e([c(t(1,[x,y]), v(c(x,y))), c(x,y)])

問 4 乗算のアルゴリズムを理解していることと、非常に制限された記述法の中でリストの例外対策が行えるか、が問われる。後者は重視しない。別解は多い。本問が解ければ優秀である。
2 進数 2 ビット値 (x1x0), (y1y0) の積は次式の通り:(2x1+x0)(2y1+y0)=4x1y1+2(x1y0+y1x0)+y0x0

よって、各桁の値は次式で得られる。4 の位、2 の位では桁上がりが発生することに注意。
1 の位: y0x0
2 の位: (x1y0 xor y1x0); 4 の位への桁上がり c は (x1y0 and y1x0)

4 の位: (x1y1 xor c) ; 8 の位への桁上がりは (x1y1 and c)
8 の位: (x1y1 and c)def m(x,y):lx=d(x)lx.extend([0,0])x0=lx.pop(0)x1=lx.pop(0)ly=d(y)y0=ly.pop(0) if ly else 0y1=ly.pop(0) if ly else 0
r = [c(x0,y0)]lz = d(a(c(x1,y0), c(x0,y1)))lz.extend([0,0])r.append(lz.pop(0))
r.extend(d(a(c(x1,y1), lz.pop(0))))
return e(r)