2015年度冬の院試の解答例です
※記載の内容は筆者が個人的に解いたものであり、正答を保証するものではなく、また東京大学及び本試験内容の提供に関わる組織とは無関係です。
出題テーマ
- メモ化再帰
問題文
※ 東京大学側から指摘があった場合は問題文を削除いたします。
関数, クラス
def func1(n):
Max = 10000
memo = [0 for _ in range(Max)]
memo[0] = 1
mod = 1<<24
for i in range(1, Max):
memo[i] = (161 * memo[i-1]+2457) % mod
return memo[n]
def func1_v2(n):
Max = 1000000+7
memo = [0 for _ in range(Max)]
memo[0] = 1
mod = 1<<24
for i in range(1, Max):
memo[i] = (161 * memo[i-1]+2457) % mod
return memo[n]
def make_func2_memo(memo_size=10000):
memo = [0 for _ in range(memo_size)]
memo[0] = 1
mod = 1<<26
for i in range(1, len(memo)):
memo[i] = (1103515245 * memo[i-1]+12345) % mod
return memo
def get_min_k(memo_size=1000007):
memo = make_func2_memo(memo_size)
for k in range(1, memo_size):
if memo[0] == memo[k]:
return k
return -1
(1)
def solve1():
n = 100
print(func1(n))
(2)
def solve2():
Max = 100
memo = [0 for _ in range(Max)]
memo[0] = 1
mod = 1<<24
# f(0) = 1でodd
cnt = 0
for i in range(1, Max):
memo[i] = (161 * memo[i-1]+2457) % mod
if memo[i] % 2 == 0:
cnt += 1
print(cnt)
(3)
def solve3():
Max = 100
memo = [0 for _ in range(Max)]
memo[0] = 1
mod = 1<<24
# f(0) = 1, i: even
cnt = 0
for i in range(1, Max):
memo[i] = (161 * memo[i-1]+2457) % mod
if i % 2 == 1 and memo[i] % 2 == 0:
cnt += 1
print(cnt)
(4)
def solve4():
n = 1000000
print(func1_v2(n))
(5)
def solve5():
memo = make_func2_memo()
print('g(2): ', memo[2])
print('g(3): ', memo[3])
(6)
def solve6():
n = 1
mod = 1<<26
cur = 1
k = 1
while True:
cur = (1103515245 * cur+12345) % mod
if cur == 1:
break
k += 1
if k > 100000000:
k = -1
break
return k
(7)
g(n) = g(n+k)と任意のnで成立するとき
h(n) = g(n) mod 2^10
h(n+k) = g(n+k) mod 2^10
よりh(n) = h(n+k)が任意のnについて成立する。
よってkの探索範囲は(6)で求めたk、これをg_kとすると、k <= g_kの範囲に絞られる。
またあるm（非負整数）に関してh(m) = h(m+k)が成立するとき、h(m) = aとするとh(m+1) = (1103515245*a+12345) mod 2^26 mod 2^10となり、h(m+k) = aなのでh(m+k+1) = h(m+1)となる。つまり、ある非負整数mに対してh(m) = h(m+k)が成立するとき、任意の非負整数M >= mに関してh(M) = h(M+k)が成立する。つまり題意を満たすにはh(0) = h(k)となるkを探索すればよく、これは任意の非負整数nに関してh(n) = h(n+k)となる。
def solve7():
max_k = 67108864
g_mod = 1<<26
h_mod = 1<<10
g_cur = 1
h_cur = 1
for k in range(1, max_k+1):
g_cur = (1103515245 * g_cur+12345) % g_mod
h_cur = g_cur % h_mod
# print(g_cur, h_cur)
if h_cur == 1:
return k
return -1
感想
- うーん、僕が問題勘違いしていたらあれですけど、この年は簡単過ぎる気がします...
- (6)で線形探索で間に合わないとまずいかなと思いましたが、10^8以下でちゃんと探索が終わったので特に工夫する部分もなく、45分程度で全問解き終わりました。
- ミスしやすい部分としては鳩ノ巣論法だ！と思って(6)の探索をk <=2^26で抑えられると勘違いすることですかね...（任意の非負整数なのでg(k) = 1となるまで探索は必要です。）