日記
昨日までと違って問題を解きまくった結果なのか無気力状態。無
ちょっとプログラミングに飽きがみられてきたので明日から数学します
起床
今日も睡眠時間短縮できなかった。その代わりに今日は大量のミサイルが飛来する夢を見た。昨日もそうだったのでもしかしたら無理して起きようとするとろくな夢を見ないのかもしれない
競プロリハビリ(グラフ)
今日はAOJにて、昨日苦戦していた問題を解いたのちにグラフの問題を4問解いた。
昨日の問題(最適二分探索木)だが、どう考えても三重でforを回さないといけないと思いRubyではなくCで解いた。その結果、dp[i][j]が葉d[i]からd[j]までを含む部分的な木における期待値の最小値を表すとして、その求める過程で根をp[i+1]からp[j]までのすべての場合でdpを用いて最小値を求めるというやり方によって解くことに成功した
さて、Rubyはかなり書きやすかったもののかなり遅かったので今度はGoで解くことにした。因みに過去にGoを触ったことはあるものの文法を全部忘れている状態
今回Goで解いた問題はすべてグラフを扱った問題となっている。グラフというのは図で表すと点が線でつながっているようにあらわされ、そのグラフを表すデータはある要素から別の要素に行くという辺の情報を保持する。
文法理解
まず着手したのは文法理解で、そのために"Go 文法"と検索をかけてみることにした(ある程度プログラムを知っているなら文法を総ざらいするのが早いと思われ)
その結果Goにおける変数の宣言は型を識別子の後ろに置くことと先に置くタイプのインクリメントが使えないこと、後はあまり競プロ用のライブラリがないことが分かった。まあなれるまでに時間がかかったもののある程度なれると書きやすい気もしてくる
問題
Goで解いた問題はALDS11_A~ALDS11_D
ALDS11_Aはグラフの形式を変換する問題だった。
グラフのデータ構造は二つあって、辺が存在するか否かを行と列にそれぞれ辺の始点と終点を対応された二次元配列の配列が持つというものと始点ごとに終点のキーを保存する可変長配列を持つというものがあって、これは後者の形式のデータを前者のそれへと変換する問題
これに関しては簡単(時間がないのまく)
ALDS11_Bは深さ優先探索で解く問題だった。これは関数の再帰を用いることで簡単に実装できる。
Goはそのまま関数内で自身を呼び出せないらしいのであらかじめひな型となるものを用意してからそのひな型に参照させるようにして実装(Qiita参照)
ALDS11_Cは幅優先探索で解く問題だった。GoにはQueueがないものの"slice"という扱いやすい可変長配列を用いることでそれらしいことができる。
ALDS11_Dは最適二分木探索木とあるがグラフが大きくなっていること以外は前述のテクニックを応用して解ける。私は幅優先探索を用いて小さなグラフのまとまりに振った番号をそのグラフの頂点一つ一つにつけ、それが同じかどうかで判定させるようにした
課題
レポート0 Webサーバの脆弱性
やってない
レポート2 交流回路の周波数特性
やってない
レポート8 ソートアルゴリズムの比較
やってない
レポート7 Raspberry Piを用いたLED制御
やってない
レポート4,5 コンピュータ設計演習
やってない
英語CⅡ Workbook Lesson7
やってない
英語CⅡ Workbook Lesson8
やってない
計測工学Ⅱ レポート
やってない
計測工学Ⅱ 演習問題
やってない
現代社会 レポート
やってない
