LoginSignup
5
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@YuanzhongLi(yuanzhong li)

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

Last updated at Posted at 2019-11-12

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

出題テーマ

  • 画像圧縮
  • byteへ変換そしてbinary書き出し

問題文

※ 東京大学側から指摘があった場合は問題文を削除いたします。Screen Shot 2019-11-12 at 16.05.41.png
Screen Shot 2019-11-12 at 16.06.00.png

配布ファイル

※ 公開されていないので以下は筆者が適当に作ったものです

image1.txt

19 7 0 17 13 1 29 3 27 5 11 23 0 0 0 255 255 255
19 7 0 255 255 255 29 3 27 5 11 23 0 0 0 255 255 255
19 7 0 17 13 1 255 255 255 5 11 23 0 0 0 255 255 255
19 7 0 17 13 1 29 3 27 255 255 255 0 0 0 255 255 255
19 7 0 17 13 1 29 3 27 255 255 255 0 0 0 255 255 255
1 1 1 10 10 10 100 100 100 50 80 46 96 71 1 255 255 255

(1)

# (1)
file_path = 'image1.txt'
def solve(file_path):
    with open(file_path, mode='r') as f:
        ret = []
        lines = f.readlines()
        for line in lines:
            ret.extend(line.rstrip('\n').split(' '))  
        print(int(len(ret) / 3))

(2)

import sys
sys.path.append('..')

import IsStrNumber as isn
from Divisors import divisors

file_path = 'image1.txt'

def is_white(cell):
    total = 0
    for c in cell:
        total += c
    return total == (255 * 3)

def solve(file_path):
    array = []
    cells = []
    with open(file_path, mode='r') as f:        
        lines = f.readlines()
        for line in lines:
            array.extend(line.rstrip('\n').split(' '))               
        for i in range(0, int(len(array) / 3)):
            idx = i * 3
            cell = [isn.STRtoNumber(array[idx]), isn.STRtoNumber(array[idx+1]), isn.STRtoNumber(array[idx+2])]
            cells.append(cell)
        cell_num = len(cells)
        divs = divisors(cell_num)
        width = 0
        for div in divs:
            if (width != 0):
                break
            col_num = div
            row_num = int(cell_num / div)            
            for i in range(0, row_num):
                right_end_cell = cells[i * col_num + col_num - 1]
                if (not is_white(right_end_cell)):
                    break
                if (i == row_num - 1):
                    width = col_num
                    
    print(width)

(3)

import sys
sys.path.append('..')

import IsStrNumber as isn

import numpy as np

file_path = 'image1.txt'

def is_white(cell):
    total = 0
    for c in cell:
        total += c
    return total == (255 * 3)

def light_degree(cell):
    ret = 0
    for c in cell:
        ret += c**2
    return ret  

def solve(file_path):
    array = []
    cells = []
    with open(file_path, mode='r') as f:        
        lines = f.readlines()
        for line in lines:
            array.extend(line.rstrip('\n').split(' '))               
        for i in range(0, int(len(array) / 3)):
            idx = i * 3
            cell = [isn.STRtoNumber(array[idx]), isn.STRtoNumber(array[idx+1]), isn.STRtoNumber(array[idx+2])]
            cells.append(cell)
        cell_num = len(cells)
        divs = divisors(cell_num)
        
        cell_order = np.array(range(0, cell_num))
        def cmp(order):
            cell = cells[order]
            return light_degree(cell)
        sorted_cell_order = sorted(cell_order, key=cmp)
        cell_idx = sorted_cell_order[int(cell_num / 2)]
        print('index: {0}, {1}'.format(cell_idx, cells[cell_idx]))

(4)

import sys
sys.path.append('..')

import IsStrNumber as isn

import numpy as np

file_path = 'image1.txt'

def is_white(cell):
    total = 0
    for c in cell:
        total += c
    return total == (255 * 3)

def light_degree(cell):
    ret = 0
    for c in cell:
        ret += c**2
    return ret  

def solve(file_path, k):
    array = []
    cells = []
    with open(file_path, mode='r') as f:        
        lines = f.readlines()
        for line in lines:
            array.extend(line.rstrip('\n').split(' '))               
        for i in range(0, int(len(array) / 3)):
            idx = i * 3
            cell = [isn.STRtoNumber(array[idx]), isn.STRtoNumber(array[idx+1]), isn.STRtoNumber(array[idx+2])]
            cells.append(cell)
        cell_num = len(cells)
        
        cell_order = np.array(range(0, cell_num))
        def cmp(order):
            cell = cells[order]
            return light_degree(cell)
        
        sorted_cell_order = sorted(cell_order, key=cmp)
        
        def pr(index):
            print('index: {0}, {1}'.format(index, cells[index]))
            
        for i in range(0, k):
            idx = int(cell_num * i / k)
            cell_idx = sorted_cell_order[idx]
            pr(cell_idx)

(5)

import sys
sys.path.append('..')

import IsStrNumber as isn

import numpy as np

file_path = 'image1.txt'

def is_white(cell):
    total = 0
    for c in cell:
        total += c
    return total == (255 * 3)

def light_degree(cell):
    ret = 0
    for c in cell:
        ret += c**2
    return ret 

def distance(cell1, cell2):
    return abs(cell1[0] - cell2[0]) + abs(cell1[1] - cell2[1]) + abs(cell1[2] - cell2[2])

def solve(file_path, k):
    array = []
    cells = []
    with open(file_path, mode='r') as f:        
        lines = f.readlines()
        for line in lines:
            array.extend(line.rstrip('\n').split(' '))               
        for i in range(0, int(len(array) / 3)):
            idx = i * 3
            cell = [isn.STRtoNumber(array[idx]), isn.STRtoNumber(array[idx+1]), isn.STRtoNumber(array[idx+2])]
            cells.append(cell)
        cell_num = len(cells)
        
        cell_order = np.array(range(0, cell_num))
        def cmp(order):
            cell = cells[order]
            return light_degree(cell)
        
        sorted_cell_order = sorted(cell_order, key=cmp)
        
        def pr(index):
            print('index: {0}, {1}'.format(index, cells[index]))
        
        # 最終的なclassterを代表するcellに対応するindexを入れていく
        # initialize
        representative_cells = []
        
        # classterに属する画素indexをそのclasster(array)に格納して管理
        # initialize
        classter_cells_array = []
        for i in range(0, 11):
            classter_cells = []
            for j in range(0, k):
                classter_cells.append([])
            classter_cells_array.append(classter_cells)         
        
        def get_cell(order_idx):
            return cells[sorted_cell_order[order_idx]]
        
        # 並べ替えた後(sorted_cell_order)のindex: t = 0
        for i in range(0, k):
            idx = int(cell_num * i / k)
            representative_cells.append(get_cell(idx))        
        
        # cellを分類する
        def classify(t, idx):
            cell = get_cell(idx)            
            classified_idx = 0
            min_dis = 30000
            for i in range(0, k):
                representative_cell = representative_cells[i]
                dis = distance(representative_cell, cell)
                if (dis <= min_dis):
                    classified_idx = i
                    min_dis = dis 
            classter_cells_array[t][classified_idx].append(idx)
        
        # cellをclasster分け : t = 0
        for i in range(0, len(sorted_cell_order)):
            cell = get_cell(i)
            classify(0, i)        
        
        def center_cell(classter):
            r = 0
            g = 0
            b = 0
            for i in classter:
                cell = get_cell(i)
                r += cell[0]
                g += cell[1]
                b += cell[2]
            return [int(r / len(classter)), int(g / len(classter)), int(b / len(classter))]        
        
        for t in range(1, 11):
            for i in range(0, k):
                representative_cells[i] = center_cell(classter_cells_array[t-1][i])
            for j in range(0, len(sorted_cell_order)):
                cell = get_cell(j)
                classify(t, j)
                
        print(representative_cells)

(6)

import sys
sys.path.append('..')

from math import sqrt

def intsqrt(num):
    return int(sqrt(num))

import IsStrNumber as isn

import numpy as np

file_path = 'image1.txt'

def is_white(cell):
    total = 0
    for c in cell:
        total += c
    return total == (255 * 3)

def light_degree(cell):
    ret = 0
    for c in cell:
        ret += c**2
    return ret 

def distance(cell1, cell2):
    return abs(cell1[0] - cell2[0]) + abs(cell1[1] - cell2[1]) + abs(cell1[2] - cell2[2])

def solve(file_path, k):
    array = []
    cells = []
    with open(file_path, mode='r') as f:        
        lines = f.readlines()
        for line in lines:
            array.extend(line.rstrip('\n').split(' '))               
        for i in range(0, int(len(array) / 3)):
            idx = i * 3
            cell = [isn.STRtoNumber(array[idx]), isn.STRtoNumber(array[idx+1]), isn.STRtoNumber(array[idx+2])]
            cells.append(cell)
        cell_num = len(cells)
        divs = divisors(cell_num)        
        
        # initialize
        cell_order = np.array(range(0, cell_num))
        def cmp(order):
            cell = cells[order]
            return light_degree(cell)
        
        sorted_cell_order = sorted(cell_order, key=cmp)
        
        def pr(index):
            print('index: {0}, {1}'.format(index, cells[index]))
        
        # 最終的なclassterを代表するcellに対応するindexを入れていく
        # initialize
        representative_cells = []
        
        # classterに属する画素indexをそのclasster(array)に格納して管理
        # initialize
        classter_cells_array = []
        for i in range(0, 11):
            classter_cells = []
            for j in range(0, k):
                classter_cells.append([])
            classter_cells_array.append(classter_cells)         
        
        def get_cell(order_idx):
            return cells[sorted_cell_order[order_idx]]
        
        # 並べ替えた後(sorted_cell_order)のindex: t = 0
        for i in range(0, k):
            idx = int(cell_num * i / k)
            representative_cells.append(get_cell(idx))        
        
        # cellを分類する
        def classify(t, idx):
            cell = get_cell(idx)            
            classified_idx = 0
            min_dis = 3000
            for i in range(0, k):
                representative_cell = representative_cells[i]
                dis = distance(representative_cell, cell)
                if (dis <= min_dis):
                    classified_idx = i
                    min_dis = dis 
            classter_cells_array[t][classified_idx].append(idx)
        
        # cellをclasster分け : t = 0
        for i in range(0, len(sorted_cell_order)):
            cell = get_cell(i)
            classify(0, i)        
        
        def center_cell(classter):
            r = 0
            g = 0
            b = 0
            for i in classter:
                cell = get_cell(i)
                r += cell[0]
                g += cell[1]
                b += cell[2]
            return [int(r / len(classter)), int(g / len(classter)), int(b / len(classter))]        
        
        for t in range(1, 11):
            for i in range(0, k):
                representative_cells[i] = center_cell(classter_cells_array[t-1][i])
            for j in range(0, len(sorted_cell_order)):
                cell = get_cell(j)
                classify(t, j)
                
        compressed_cells = []
        # initailize
        for i in range(0, cell_num):
            compressed_cells.append([])
        

        for i, classters in enumerate(classter_cells_array[10]):
            for idx in classters:
                original_idx = sorted_cell_order[idx]
                compressed_cells[original_idx] = representative_cells[i]       
                
        w = intsqrt(len(cells))
        h = w
        s = w * h * 3
        w_b = w.to_bytes(4, byteorder='big')
        h_b = h.to_bytes(4, byteorder='big')
        s_b = s.to_bytes(4, byteorder='big')
        
        attribute = [77, 77, 0, 42, 0, 0, 0, 8, 0, 7, 1, 0, 0, 4, 0, 0,
                  0, 1, 'w', 1, 1, 0, 4, 0, 0, 0, 1, 'h', 1, 2, 0, 3, 0, 0, 0, 3, 0, 0, 0, 98, 1, 6,
                  0, 3, 0, 0, 0, 1, 0, 2, 0, 0, 1, 17, 0, 4, 0, 0,
                  0, 1, 0, 0, 0, 104, 1, 21, 0, 3, 0, 0, 0, 1, 0, 3,
                  0, 0, 1, 23, 0, 4, 0, 0, 0, 1, 's', 0, 0,
                  0, 0, 0, 8, 0, 8, 0, 8]
                
        
        with open('image.tif', 'wb') as fout:
            for i in attribute:
                if (i == 'w'):
                    fout.write(w_b)
                elif (i == 'h'):
                    fout.write(h_b)
                elif (i == 's'):
                    fout.write(s_b)
                else:
                    fout.write(i.to_bytes(1, byteorder='big'))
            for cell in compressed_cells:
                for i in range(0, 3):
                    fout.write(cell[i].to_bytes(1, byteorder='big'))

感想

  • きつかった...
  • やってること自体は複雑ではないはずなのにすごく解くのに時間がかかった...
  • cellクラスを作るのをサボるべきでは無い。後ろの問題に行くほど作っておけばよかったと感じた
  • (6)はbyteへの変換がわからなかったのでググりました...(本番ならアウト)
  • python使いなれてないせいで、初めてenumerate()関数という便利なものを知れた
  • 画像処理とかやっている人にとっては楽な問題なのかな...??（そういう方にとってこの問題の立ち位置とか教えてもらえると助かります）
5
5
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?