Help us understand the problem. What is going on with this article?

東京大学大学院情報理工学系研究科 創造情報学専攻 2018年度 実技試験

More than 1 year has passed since last update.

東京大学大学院情報理工学系研究科 創造情報学専攻の2018年度 実技試験(プログラミング)の解答例(Python3)です。
https://www.i.u-tokyo.ac.jp/common/file/edu/course/ci/2017-8-program.pdf

※公開元ページはこちら
※記載の内容は筆者が個人的に解いたものであり、正答を保証するものではなく、また東京大学及び本試験内容の提供に関わる組織とは無関係です。

(1)

問題文に記載のプログラムから、一番内側のループ1回の実行でa及びbから要素を読むため、2回あり、外側のループから、
2*{(n*m)m} = 2n*m^2

(2)

本当の試験ではUSBメモリを渡されて、その中にmat1.txtがあるわけですが(おそらく非常に大きなファイル)、今回は以下のファイルをサンプルとして想定します。

  • mat1.txt
0 1 2 3,4 5 6 7,8 9 10 11.xxx
  • 2.py
import numpy as np
import re
def setArray(fn):
   mat = open(fn,'r')
   rn = 0 
   cn = 0 
   for row in mat:
       regex = re.compile('([0-9 \.]+)(\.|,)')
       ret = regex.findall(row.strip())
       rn = len(ret)
       n = 0 
       for i in ret:
           tmp = i[0].strip().split(' ')
           if cn == 0:
               cn = len(tmp)
               A = np.zeros((rn,cn)).astype(int)
           A[n] = tmp 
           n = n + 1 
       print("rn,cn:"+str(A.shape))
   return A
A = setArray("./mat1.txt")
rn,cn:(3, 4)

rnが行の数、cnが列の数になります。

(3)

想定するmat2.txtとプログラム、実行結果は以下になります。

  • mat2.txt
12 13 14,15 16 17,18 19 20,21 22 23.
  • 3.py
import numpy as np
import re
def setArray(fn):
   mat = open(fn,'r')
   rn = 0 
   cn = 0 
   for row in mat:
       regex = re.compile('([0-9 \.]+)(\.|,)')
       ret = regex.findall(row.strip())
       rn = len(ret)
       n = 0 
       for i in ret:
           tmp = i[0].strip().split(' ')
           if cn == 0:
               cn = len(tmp)
               A = np.zeros((rn,cn)).astype(int)
           A[n] = tmp 
           n = n + 1 
       print("rn,cn:"+str(A.shape))
   return A
A = setArray("./mat1.txt")
B = setArray("./mat2.txt")
C = np.dot(A,B)
print(C)
print(sum(np.diag(C)))
rn,cn:(3, 4)
rn,cn:(4, 3)
[[114 120 126]
[378 400 422]
[642 680 718]]
1232

(4)

(4)からは、メモリ、キャッシュメモリを使った読み込みに関する問題が続きます。
m,n,s(キャッシュ)からメモリから読む回数を数えるプログラムは以下になります。

def readCount(m,n,s):
    i = 0 
    ret = 0 
    c = {}
    for i in range(m):
        j = 0 
        for j in range(m):
            d = 0 
            k = 0 
            for k in range(n):
                index = "a:"+str(i)+":"+str(k)
                try:
                    c[index]
                except KeyError:
                    ret = ret + 1 
                    if len(c) >= s and len(c) > 0:
                        delKey = min(c, key=c.get)
                        del c[delKey]
                c[index] = k + j*n + i*m*n
                index = "b:"+str(k)+":"+str(j)
                try:
                    c[index]
                except KeyError:
                    ret = ret + 1 
                    if len(c) >= s and len(c) > 0:
                        delKey = min(c, key=c.get)
                        del c[delKey]
                c[index] = k + j*n + i*m*n
                k = k + 1 
            j = j + 1 
        i = i + 1 
    return str(ret)

(5)

効率化のためにm,nの公約数pを使ったプログラムに変わります。
空欄はこのようになると思われます。
i < u + p
j < v + p
k < w + p

(6)

(5)の実装をすればよいので以下のようになります。

def readCount(m,n,p,s):
    i = 0
    ret = 0
    c = {}
    u = 0

    indexValue = 0;
    while u < m:
        v = 0
        while v < m:
            w = 0
            while w < n:
                i = u
                while i < u + p:
                    j = v
                    while j < v + p:
                        k = w
                        while k < w + p:
                            indexValue = indexValue + 1
                            index = "a:"+str(i)+":"+str(k)
                            try:
                                c[index]
                            except KeyError:
                                ret = ret + 1
                                if len(c) >= s and len(c) > 0:
                                    delKey = min(c, key=c.get)
                                    del c[delKey]
                            c[index] = indexValue
                            index = "b:"+str(k)+":"+str(j)
                            try:
                                c[index]
                            except KeyError:
                                ret = ret + 1
                                if len(c) >= s and len(c) > 0:
                                    delKey = min(c, key=c.get)
                                    del c[delKey]
                            c[index] = indexValue
                            k = k + 1
                        j = j + 1
                    i = i + 1
                w = w + p
            v = v + p
        u = u + p
    return str(ret)

問題は(7)までですが、筆者は解くのが難しかったのでできれば後日まとめられればと思っています(詳しい方いたらぜひ教えてください!)。

unpg
都内でITエンジニアを営んでおります。プログラミング試験関連の情報を発信していきます!
https://twitter.com/unpgnow
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした