estie Advent Calendar 2019 15日目の記事になります。
初めに
estie.incでエンジニアやってます、YuanzhongLiともうします。
現在は東大工学部の4年生です。
Advent Calendarを書く際にいいのが思い浮かばず、最近解いてる東大情報理工創造情報院試の過去問で勉強になったなぁ、面白かったなぁと思ったものを解説しながら3年分くらい共有できたらいいなぁ〜という感じでこの記事を書いているので大目に見ていただけるとありがたいです😅
問題出典: 東京大学情報理工学系研究科創造情報学専攻入試案内
では早速いってみましょう~
2013年度夏
僕個人の感想ですが、今のところ試験としてのできが最高だと思っている年です。
様々な専攻向けのプログラミングの試験なのでアセンブリを書かせるのはさすがに難易度が高い、だけど実際に書いたプログラムがどう動いているかは知ってる？というのをしっかり確認させてきます。また決してアセンブリを書いたことがないと詰むという訳ではなく誘導もきれいです。（もちろんある程度の知識も必要です）
出題テーマ
- アセンブリ, 命令セット
問題文
※ 東大の公式アーカイブにはすでにのっていなく、ここでは他のアーカイブサービスから取得したものを公開しますが、東京大学側から指摘があった場合は問題文を削除いたします。
解答
import sys
sys.path.append('..')
import IsStrNumber as isn # stringかintかをcheckし、さらにはstr to int(int to str)の機能をもつモジュール
file_path = 'prog.txt'
def solve(file_path):
max_order = 100
orders = []
with open(file_path, encoding='ascii') as f:
for i in range(0, max_order):
line = f.readline()
if (line != ''):
line = line.rstrip('\n')
code_array = line.split(' ')
orders.append(code_array)
# python のglobal変数が使い辛すぎるのでこうした
next_order = { 'num': 0 }
sub_order_stack = []
# register_stack[0]をglobal register(実際のレジスタ)とする
register_stack = [{}]
# register_stackの最後尾のregisterオブジェクトを使用することによって局所レジスタ群を実現
def compileOrder(order, op1, op2):
if (order == 'ADD'):
next_order['num'] += 1
if (isn.isNumber(op1)):
register_stack[len(register_stack)-1][op2] += isn.STRtoNumber(op1)
else:
register_stack[len(register_stack)-1][op2] += register_stack[len(register_stack)-1][op1]
elif (order == 'PRN'):
next_order['num'] += 1
if (isn.isNumber(op1)):
if (isn.isNumber(op2)):
print(isn.STRtoNumber(op1), isn.STRtoNumber(op2))
else:
print(isn.STRtoNumber(op1), register_stack[len(register_stack)-1][op2])
else:
print(register_stack[len(register_stack)-1][op1], register_stack[len(register_stack)-1][op2])
elif (order == 'SET'):
next_order['num'] += 1
if (isn.isNumber(op2)):
register_stack[len(register_stack)-1][op1] = isn.STRtoNumber(op2)
else:
register_stack[len(register_stack)-1][op1] = register_stack[len(register_stack)-1][op2]
elif (order == 'CMP'):
next_order['num'] += 1
if (isn.isNumber(op1)):
if (isn.isNumber(op2)):
if (isn.STRtoNumber(op1) == isn.STRtoNumber(op2)):
next_order['num'] += 1
else:
if (isn.STRtoNumber(op1) == register_stack[len(register_stack)-1][op2]):
next_order['num'] += 1
else:
if (isn.isNumber(op2)):
if (register_stack[len(register_stack)-1][op1] == isn.STRtoNumber(op2)):
next_order['num'] += 1
else:
if (register_stack[len(register_stack)-1][op1] == register_stack[len(register_stack)-1][op2]):
next_order['num'] += 1
elif (order == 'JMP'):
if (isn.isNumber(op1)):
next_order['num'] += isn.STRtoNumber(op1)
else:
next_order['num'] += register_stack[len(register_stack)-1][op1]
elif (order == 'SUB'):
# 次のorderをstackに保存
sub_order_stack.append(next_order['num']+1)
compileOrder('JMP', op1, op2)
elif (order == 'BAK'):
next_order['num'] = sub_order_stack.pop()
elif (order == 'CAL'):
sub_order_stack.append(next_order['num']+1)
new_register = { 'in': 0 }
if (isn.isNumber(op2)):
new_register['in'] = isn.STRtoNumber(op2)
else:
new_register['in'] = register_stack[len(register_stack)-1][op2]
compileOrder('JMP', op1, op2)
# JMPしてから局所レジスタ群をスタックに追加
register_stack.append(new_register)
elif (order == 'RET'):
next_order['num'] = sub_order_stack.pop()
# 局所レジスタ群を消去
old_register = register_stack.pop()
# 局所を抜けた後にoutを使用できるように、抜けた直後の局所register群にoutを追加
if (isn.isNumber(op1)):
register_stack[len(register_stack)-1]['out'] = isn.STRtoNumber(op1)
else:
register_stack[len(register_stack)-1]['out'] = old_register[op1]
while (next_order['num'] < len(orders)):
order = orders[next_order['num']][0]
op1 = orders[next_order['num']][1]
op2 = orders[next_order['num']][2]
compileOrder(order, op1, op2)
解説
1. レジスタ
値（変数など）を保持するもので, 本来はこれにメモリ上の値などを格納し、cpu上で高速に使用して計算している。
今回でいうとα、βの値や、そのほか定義された変数を保持している。一般的には32個と有限であるが今回はそれを無限として考えていいので従来のメモリがそのままレジスタとなっているイメージ。
そしてレジスタ群というのは要は変数群のことになります。
なぜこういう解説を入れたかというと、本来のアセンブリコードではADD reg1 reg2のようにレジスタ指定して動くからである。逆にこの説明で混乱してしまうのならただの変数と思ってもこの問題では差し支えない。
2. PC（プログラムカウンタ）
簡単にいうとこれは次の命令が何であるかを保持している。今回の問題では行毎に命令が書かれているので、次の命令が何行目かを示している。本来は次の命令のアドレスを示している。
つまりJMPはPC（コード上ではnext_order）にJMP先が何行目かを渡せば実現できる。
1, 2がわかっていると(4)までは実装ができ、for loopなどができるようになる
3. CAL, RET
ここから基礎知識がないと急に難しくなると思う。CALは関数を呼び、RETはその関数での返り値というイメージである。
しかし、ここで問題になるのが関数内で関数を読んだんり、再帰関数のように何度も自身を読んだりするものである。このとき局所変数の管理の仕方が大変難しくなってくる。じゃあこれをどう実現するかというと、スタックを使います。このスタックを使うというのが今回のみそです。
今回の問題ではglobal変数がなく、必ずCALの引数で渡しています。なので、まずレジスタ群のスタックを作っちゃいましょう。さらに、PCもスタックで管理したいのでPC用のスタックも作りましょう。そしてCAL命令が実行されたら、まずPCをPCのスタック（コード上ではsub_order_stack）に入れ、次に新しいレジスタ群をレジスタ群のスタックに入れます。そしてRETのとき、つまり関数呼び出しが終わり元のコードの位置に戻るときに、PCのスタックをpopすると、関数に入る前（CALを実行する前）のPCがtopにあり、取得されるのでこれをそのままnext_order（次に実行する命令、要はPC）にしちゃいましょう。局所レジスタ群は返り値だけ渡してあげて、あとはいらないのでpopしてポイ捨てしちゃいます。こうすると関数は関数内で完結させることができます。
実際のアセンブリではSP（スタックポインタ）というアドレスを格納するスタックを使って実現しています。つまり、この問題はSPという知識がないと詰む可能性が高いと言えますが、必ずしもはっきりと理解している必要もなくアセンブリではCAL、RETをスタック使ってやっているよねーくらいの知識で十分なので、なんとも絶妙に作られた問題ですね（べた褒め）。
2012年度夏
先ほどの問題がもっとも勉強になる問題だとしたら、この問題がもっとも解いていて楽しい問題だと思います。
この問題ではすごくシンプルなシューティングゲームを作らせます。
オブジェクト指向のパワーを遺憾無く発揮しましょう笑
出題テーマ
- フレーム
問題文
※ 東京大学側から指摘があった場合は問題文を削除いたします。
解答
import copy as cp
import time
import fcntl
import termios
import sys
import os
def getkey():
fno = sys.stdin.fileno()
#stdinの端末属性を取得
attr_old = termios.tcgetattr(fno)
# stdinのエコー無効、カノニカルモード無効
attr = termios.tcgetattr(fno)
attr[3] = attr[3] & ~termios.ECHO & ~termios.ICANON # & ~termios.ISIG
termios.tcsetattr(fno, termios.TCSADRAIN, attr)
# stdinをNONBLOCKに設定
fcntl_old = fcntl.fcntl(fno, fcntl.F_GETFL)
fcntl.fcntl(fno, fcntl.F_SETFL, fcntl_old | os.O_NONBLOCK)
chr = 0
try:
# キーを取得
c = sys.stdin.read(1)
if len(c):
while len(c):
chr = (chr << 8) + ord(c)
c = sys.stdin.read(1)
finally:
# stdinを元に戻す
fcntl.fcntl(fno, fcntl.F_SETFL, fcntl_old)
termios.tcsetattr(fno, termios.TCSANOW, attr_old)
return chr
class Enemy(object):
def __init__(self):
self.x = int(4)
self.y = int(0)
self.mark = 'O'
self.vector = [1, 1]
def __repr__(self):
return 'x: {0}, y: {1}, vec: {2}'.format(self.x, self.y, self.vector)
def move(self):
self.x += self.vector[0]
self.y += self.vector[1]
if (self.y > 14):
self.x = int(4)
self.y = int(0)
self.vector = [1, 1]
elif (self.x == 0):
self.vector[0] = 1
elif (self.x == 8):
self.vector[0] = -1
class Bullet(object):
def __init__(self, x:int):
self.x = int(x)
self.y = int(14)
self.mark = 'e'
def __repr__(self):
return 'x: {0}, y: {1}'.format(self.x, self.y)
def move(self):
self.y -= 1
class Gun(object):
def __init__(self):
self.x = int(4)
self.mark = 'X'
# 残弾数
self.remain_bullet = 2
def __repr__(self):
return 'x: {0}, 残弾数: {1}'.format(self.x, self.remain_bullet)
class Game(object):
def __init__(self):
self.board = [
['|', '-', '-', '-', 'V', '-', '-', '-', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', '-', '-', '-', 'X', '-', '-', '-', '|'],
]
self.default_board = [
['|', '-', '-', '-', 'V', '-', '-', '-', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'],
['|', '-', '-', '-', '-', '-', '-', '-', '|'],
]
self.enemy = Enemy()
self.bullets = []
self.gun = Gun()
self.point = 0
self.fail = 0
# 初期段階
self.phase = 0
def print_board(self):
row = len(self.board)
print()
col = len(self.board[0])
for i in range(0, row):
row_str = ''
for j in range(0, col):
row_str += self.board[i][j]
print(row_str)
def fire_gun(self, key):
if (self.gun.remain_bullet > 0 and key == 'i'):
self.bullets.append(Bullet(self.gun.x))
self.gun.remain_bullet -= 1
def move_enemy(self):
# 移動
self.enemy.move()
if (self.enemy.y == 14):
self.fail += 1
# 初期位置にreset
elif (self.enemy.y == 0):
self.gun.remain_bullet = 2
def move_bullets(self):
for index, bullet in enumerate(self.bullets):
if (bullet.y >= 0):
bullet.move()
def get_default_board_cell(self, x, y):
if (x == 4 and y == 0):
return 'V'
elif (x == 0 or x == 8):
return '|'
elif (y == 0 or y == 14):
return '-'
else:
return ' '
def move_gun(self, key):
if (key == 'j'):
self.gun.x -= 1
if (self.gun.x < 0):
self.gun.x = 0
if (key == 'l'):
self.gun.x += 1
if (self.gun.x > 8):
self.gun.x = 8
def update_board(self):
tmp_board = cp.deepcopy(self.default_board)
# enemyの移動後を更新
tmp_board[self.enemy.y][self.enemy.x] = 'O'
# enemyがresetした時にVに戻す
tmp_board[0][4] = 'V'
# gunの移動を更新
tmp_board[14][self.gun.x] = 'X'
# bulletの移動を更新
for index, bullet in enumerate(self.bullets):
if (bullet.y > 0 and bullet.y < 14):
# enemyに当たった
if (tmp_board[bullet.y][bullet.x] == 'O'):
tmp_board[bullet.y][bullet.x] = self.get_default_board_cell(bullet.x, bullet.y)
self.point += 1
self.gun.remain_bullet = 2
# reset enemy
self.enemy = Enemy()
# disable bullet
bullet.y = -1
else:
tmp_board[bullet.y][bullet.x] = 'e'
self.board = tmp_board
def update_phase(self, key):
if (key == 'i' or key == 'j' or key == 'k' or key == 'l'):
self.phase += 1
self.move_gun(key)
self.fire_gun(key)
self.move_enemy()
self.move_bullets()
self.update_board()
def play_game_debug(self):
print('phase: {0}, point: {1}, fail: {2}, 残弾数: {3}'.format(game.phase, game.point, game.fail, game.gun.remain_bullet))
game.print_board()
print('=' * 20)
while (game.fail < 5 and game.phase < 40):
start = time.time()
key = 'k'
randn = random.randrange(9)
if (randn == 0):
key = 'i'
if (randn == 1):
key ='j'
if (randn == 2):
key = 'k'
if (randn == 3):
key = 'l'
# 0.5 秒いない
while (time.time() - start < 0.5):
key = key
self.update_phase(key)
print('phase: {0}, point: {1}, fail: {2}, 残弾数: {3}'.format(game.phase, game.point, game.fail, game.gun.remain_bullet))
game.print_board()
print('=' * 20)
def play_game(self):
print('phase: {0}, point: {1}, fail: {2}, 残弾数: {3}'.format(game.phase, game.point, game.fail, game.gun.remain_bullet))
game.print_board()
print('=' * 20)
while (game.fail < 5):
start = time.time()
key = 'k'
while (time.time() - start < 0.5):
input_key = chr(getkey())
if (input_key == 'i' or input_key == 'j' or input_key == 'l'):
key = input_key
self.update_phase(key)
print('phase: {0}, point: {1}, fail: {2}, 残弾数: {3}'.format(game.phase, game.point, game.fail, game.gun.remain_bullet))
game.print_board()
print('=' * 20)
game = Game()
game.play_game()
解説
1. オブジェクト指向
要は物体毎に考えようってだけです。
この問題だと、敵、銃、弾といかにも物体（オブジェクト）であろうもののclassを作ると、プログラミングがだいぶ楽になります。
2. 画面描画
実はこの問題の裏テーマ（ともなり得た）。問題文で指定されている解き方2でやるとこの問題にぶち当たるでしょう。
僕は一応2でもできますが、チキって1でやりました笑。2でやる場合は描画の局所の追跡ができるようにする必要があり、これはそれぞれのオブジェクトの移動の前後を保持することで可能です。
1の方法ではオブジェクトに自身の位置を保持させ、毎回ゲームのフィールドを描画してその上にオブジェクトをその位置を元に描画するイメージです。
実はこれだけで(5)までは解けてしまいます。
3. フレーム
(7)を実現するため、ここからは実際のゲームのようにフレーム単位で考えましょう。
格闘ゲームに詳しいとわかりますが、ゲームはフレーム毎になっています。（なので格闘ゲームでは必ず技の順序が決まっています。）つまりこのゲームでもフレーム(問題で約0.5秒と指定)毎に考えることで実現して行こうと思います。
まずはフレーム単位でkeyの入力をbusy waitで受け取ります。
busy wait とはwhile(true)のように1実行(多分マイクロ秒のオーダーで非常に小さく、速い)毎に入力を受け取ります。そして受け取った入力をフレームの終了と同時に反映させ、その後次のフレームを開始します。人間にとってはフレーム毎でも十分滑らかなに見えるのでこれで十分です。
ちなみにterminalで上記のコードを保存したファイルを実行すると遊べます笑。
2014年度冬
この問題を選んだのは直近で解いたからという理由だけです笑。
出題テーマ
- 数値計算
問題文
※ 東京大学側から指摘があった場合は問題文を削除いたします。
解答
# (1)
def solve1(x):
if (x <= 2):
return 1
else:
return solve1(x - 1) + solve1(x - 2)
# (2)
memo = [0] * 100
memo[0], memo[1] = 0, 1
def init():
for i in range(2, 99):
memo[i] = memo[i - 1] + memo[i - 2]
def solve2(x):
init()
return memo[x]
# (3)
def solve3(s1, s2):
carry = 0
ret = ''
for i in range(32):
ch1 = s1[31 - i]
ch2 = s2[31 - i]
n1 = int(ch1)
n2 = int(ch2)
a = n1 + n2 + carry
if (a >= 10):
carry = 1
else:
carry = 0
b = a % 10
ret += str(b)
return ret[::-1]
# (4)
memo = [0] * 141
memo[0], memo[1] = 0, 1
def init():
for i in range(2, len(memo)):
memo[i] = memo[i - 1] + memo[i - 2]
def solve4(x):
init()
return memo[x]
# (5)
def solve5(s1, s2):
n1 = int(s1)
n2 = int(s2)
return n1 / (10**(31 - n2))
# (6)
def root(x):
x = float(x)
right = x
left = 0.0
esp = 1e-7
while (abs(right - left) > esp):
mid = (right + left) / 2
if (mid * mid > x):
right = mid
else:
left = mid
return right
def solve6():
return (1 + root(5)) / 2
# (7)
# (a + b * root(5) / 2)** 2のa, b
def func1(a, b):
new_a = int((a ** 2 + (b**2)*5) / 2)
new_b = int(a * b)
return new_a, new_b
# (a + b * root(5) / 2) * (c + d * root(5) / 2)
def func2(a, b, c, d):
new_a = int((a * c + b * d * 5) / 2)
new_b = int((a * d + b * c) / 2)
return new_a, new_b
root5 = root(5)
class obj:
def __init__(self, a, b):
self.a = a
self.b = b
def __repr__(self):
return '({0} + {1} * root5) / 2'.format(self.a, self.b)
def cal(self):
return (self.a + self.b * root5) / 2
def f1(self):
new_a, new_b = func1(self.a, self.b)
return obj(new_a, new_b)
# (1+roo5/2)の2のindex-1乗のobjを格納
memo1 = [obj(0, 0)] * 9
memo1[1] = obj(1, 1)
def init_memo1():
# 128 (2^7)まで計算
for i in range(2, len(memo1)):
memo1[i] = memo1[i - 1].f1()
init_memo1()
# ex) 139 = 128(2^7) + 8(2^3) + 2(2^1) + 1(2^0) = [1, 1, 0, 1, 0, 0, 0, 1]
def func3(x):
ret = [0] * 8
if (x >= 128):
ret[7] = 1
x -= 128
if (x >= 64):
ret[6] = 1
x -= 64
if (x >= 32):
ret[5] = 1
x -= 32
if (x >= 16):
ret[4] = 1
x -= 16
if (x >= 8):
ret[3] = 1
x -= 8
if (x >= 4):
ret[2] = 1
x -= 4
if (x >= 2):
ret[1] = 1
x -= 2
if (x >= 1):
ret[0] = 1
x -= 1
return ret
def obj_mul(obj1, obj2):
a = obj1.a
b = obj1.b
c = obj2.a
d = obj2.b
new_a, new_b = func2(a, b, c, d)
return obj(new_a, new_b)
# (1+roo5/2)index乗のobjを格納
memo2 = [obj(0, 0)] * 141
memo2[1] = obj(1, 1)
for i in range(2, len(memo2)):
digit2 = func3(i)
obj_array = []
for (index, j) in enumerate(digit2):
if (j == 1):
obj_array.append(memo1[index+1])
tmp = obj_array[0]
for k in range(1, len(obj_array)):
tmp = obj_mul(tmp, obj_array[k])
memo2[i] = tmp
def g(x):
return memo2[x].cal() / root5
# (8)
def f(x):
return solve4(x)
def solve8():
Max = 0.0
for i in range(1, 141):
Max = max(abs(f(i) - g(i)), Max)
return Max
解説
1. 再帰関数(1), (2)
(2)でなぜ計算時間をきにしてきたのかというと,
例えば、
f(32) = f(31) + f(30)
f(31) = f(30) + f(29), f(30) = f(29) + f(28)
f(30) = f(29) + f(28), f(29) = f(28) + f(27), f(29) = f(28) + f(27), f(28) = f(27) + f(26)
...
を見るとわかるが2の乗数分計算している。これではf(50)は約2^50のオーダーとなるがこれはとてもではないが間に合わない。
なのでsolve2を見るとわかるがメモ化再帰という手法をとると簡単にかける。要は逐一計算した値をメモのように残して、その値を使って計算する方法である。
2. キャリー (3), (4), (5)
要は繰り上げを考慮すると10^32（約2^106）という膨大な数も簡単に計算できる。（一般的に整数は最大でも64bitでの表現が限界でこれは2^64までしか表せない）
実はpythonだとデフォルトでそのように計算できるので、(4), (5)は(3)を利用しなくても解けてしまう。
こういうのはやはりpythonのいいところ。
3. newton法 (6)
ちょっと変わっているのは微分で傾きではなく二分探索のように解いた。要は抑えたい誤差以下になるまで反復計算させれば良い。
4. 整数管理 (7), (8)
ここでやったことはまず整数は整数、ルートはルートで管理するように、objという数のclassを作成した。あとはobj classのコードを見ていただいた方がわかりやすいが、aとbから簡単に計算できるようになっている。
また140は2進数で8桁で表せるので、初めに1, 2, 4, 8, 16, 32, 64, 128乗を計算しといて、あとはその組み合わせを計算（高々8回）することで求めらるようにした。もしこれを乗数分計算することになると、例えばn乗はn回計算する必要があり、1から140までだと1, 2, 3 ... 140の合計、つまり140^2のオーダーになるが、上述の計算方法だと140*log(140)のオーダーになる。
(8)はxが整数前提で解いたが、区間の場合どちらも指数的に単調増加するから多分x=140のとき差が最大になると予想はできる。
区間の場合はそれこそf(x)とg(x)を求め、f(x) - g(x)を微分してnewton法でやるしかないだろう。