【院試解答】東大院工学系研究科電気系工学専攻 2020年 問題4
免責
この解答・解説は当ブログ管理人のものであり、間違っている可能性もあります。
この記事の記載内容によって生じた損失や損害については、当ブログ管理人は一切責任を負いません。
が、間違っている箇所や、よりよい解法があれば後から見に来た人のためにもコメント欄に残していってもらえると、幸いです。
あと、解説でこれが解ければ院試は受かる、的なことを言っていますが、一回しか院試を受けたことがない管理人の所感なので真剣にはあてになさらず。
でももちろん、管理人が実際にそう感じたことを書いています。
問題
解答
※昔から電子工作を趣味としている管理人は、問題4の難易度の感覚がバグっているので、「難しい」と記載したもの以外はあまり参考にしないでください。
I
(1) 難易度:普通※
(2) 難易度:普通※
X=0, 0, 0, 1の順
(3) 難易度:普通※
(4) 難易度:普通※
(5) 難易度:普通※
Ⅱ
(1) 難易度:普通※
{9, 7, 8, 1, 6, 4, 5}
問題のコードはC言語と違って配列のインデックスが1スタートなので注意。
(2) 難易度:普通※
(3) 難易度:普通※
要素の数をnとして、O(n log n)
(4) 難易度:難しい
本解:
void sort_by_heap(int array[], int n) { for(int i = 0; i < n - 1; i++) make_heap(array + i, n - i); }本解を改行したもの:
void sort_by_heap(int array[], int n) { for(int i = 0; i < n - 1; i++) make_heap(array + i, n - i); }参考解:
void sort_by_heap(int array[], int n) { for(int i = n; i > 1; i--) { make_heap(array, i); swap(array, 1, i); } for (int i =1; i <= n / 2; i++) swap(array, i, n - i + 1); }ヒープソートの話かなと思ったので最初参考解を思いついたが、
as few lines as possibleという問題文の指示が気になったので本解の方を思いついた。もっとも、どんなプログラムであれ改行無しで書けば1行になるのだが。
どちらもmake_heapを実行するとarrayの先頭が最大値になることを利用している。以下は本解の解説。
make_heapの引数は先頭アドレスarray + i、サイズn - iの配列を渡すという意味である。本来先頭アドレスarray、サイズnの配列から部分配列を切り出してmake_heapに渡す操作を行っている。ちなみに配列はメモリ上で、(インデックスが1スタートのこのプログラムにのっとって言うと、)アドレスarrayにarray[1]、array + 1にarray[2]、...、array + n - 1にarray[n]という風に配置されている。
for文の()の中の書き方のコツはイテレータ変数(解答でいうとi)の初期値と最終値だけ見ることである。今回は初期値がi = 0で、条件式i < n - 1がi = n - 2の時まではtrueになることから最終値がi = n - 2になることがわかる。make_heapに渡した引数の方も初期値と最終値だけ考えればよく、初期値が(array, n)、最終値が(array + n - 2, 2)であることがわかる。別にi = n - 1まで回してもいいのだが、その時はサイズ1の配列をmake_heapすることになり何も起こらないので条件式をi < n - 1に設定している。ちなみにi <= n - 2としてもよい。こちらの方が直感的かもしれない。
(5) 難易度:普通※
arrayをサイズnのint型配列とする。 1. まず、make_heapを用いてarrayにmax heapを作る。 次に、arrayの先頭array[1]はmax heap中の最大値となっているので、 それをarrayの最後の要素array[n]とswapする。仰々しく書いてしまったが要はヒープソートをやっている。コードで書くと次のよう。
2. n2 = n-1, n-2, ..., 2に対して下記を実行する。 先頭アドレスarray[1]、サイズn2のarrayの部分配列をarray2と定義する。 array2はarray2[1]の要素以外はmax heapの条件を満たしている。 array2[1]もmax heapの条件を満たすため、 push_down(array2, n2, 1)(つまりpush_down(array, n2, 1))を実行し、 木の下方に向かって並べ替える。 その後、array2[1]はまたmax heap中の最大値となっているのでarray2[n2]とswapする。
以上の手順により並べ替えられたarrayは先頭から昇順に並んでいる。
void heap_sort(int array[], int n) { make_heap(array, n); swap(array, 1, n); for(int n2 = n - 1; n2 >= 2; n2--) { push_down(array, n2, 1); swap(array, 1, n2); } }計算量オーダーは(4)がO(n2 log n)、(5)がO(n log n)なので(5)の方が効率的になっている。
