東京大学大学院情報理工学系研究科 創造情報学専攻 2015年度冬 プログラミング試験

2015年度冬の院試の解答例です
※記載の内容は筆者が個人的に解いたものであり、正答を保証するものではなく、また東京大学及び本試験内容の提供に関わる組織とは無関係です。

### 出題テーマ
- メモ化再帰


### 問題文
※ 東京大学側から指摘があった場合は問題文を削除いたします。
<img width="612" alt="Screen Shot 2020-01-26 at 11.56.17.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/226167/07b7cbe8-5763-78b0-b918-776999bed736.png">

### 関数, クラス
```python
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)
```python
def solve1():
    n = 100
    print(func1(n))
```

### (2)
```python
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)
```python
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)
```python
def solve4():
    n = 1000000
    print(func1_v2(n))
```

### (5)
```python
def solve5():
    memo = make_func2_memo()
    print('g(2): ', memo[2])
    print('g(3): ', memo[3]) 
```
### (6)
```python
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)となる。
     
```python
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となるまで探索は必要です。）