2017-07-09

星野源の「いのちの車窓から」を読んだ話

　僕は星野源が好きだ。フィルムがJwaveで繰り返し流れていた頃から好きだ。ライブには一度も行ったことはないが、CDの初回限定版を買うくらいは好きである。要するに熱狂的なファンではない。好きのレベルはそのくらいだが、先日本屋に行った時にこの本を見つけて迷わず購入した。

　本書はなんかの雑誌に連載していた彼の短いコラムを集めたものだ。こっそりツイッターをやっていた話、SUNのバックグランド、紅白、ラジオに対する彼の考えなどが書かれている。

　本書を読み終えて、僕は彼の簡潔で分かりやすい文章に驚いた。きちんと書かれた論文や理系の人が書く文章を読んだ時に感じる「違和感を感じさせることなく淡々と進んでいく」文章と同じだったからだ。ちょうど本書の中に彼の「文章を書く事」についてのコラムがある。意外であるが、彼は文章を書く事に対して苦手意識があったそうだ。しかし文章を書く事を仕事にする事で、無理やりにでも書き続けた。その結果、現在は自分の思いを言葉にすることが苦ではないそうだ。

　これに影響を受けて、僕は今長い間放置していた日記を書いている。自分の考えを文章にすることに対して、僕は苦手意識を持っているし苦痛である。それでも彼のような文章が書けるようになるなら、定期的に書く事を続けてみようと思う。

　ちなみにタイトルの「いのちの車窓から」は自分の体を人生を旅する機関車に例えたものだ。詳しくは本書を参照されたい。

2017-03-16

ALDS_11_A Graphを解く話

AOJ

グラフの表現の理解を問う問題である．

隣接リスト表現から隣接行列表現へ変換する処理を実装する．

隣接リスト表現（Adjacency List)

・有限グラフを表現するためのリスト
・1つのリストが1つの頂点に対応して，隣接するノードが接続

隣接行列表現（Adjacency Matrix）

・有限グラフを表現するための行列
・行列の各要素は頂点のペアが隣接しているか否かを示す．

以下のサイトで，グラフと辺をいじったり行列とリストを確認できる．

https://visualgo.net/graphds

実装

入力は
　頂点番号 $u$ 　出次数 $k$ 　uに隣接する頂点 $v_1, v_2, ..., v_k$
の形式で与えられる．

$u = 1\ to\ n$ を行番号， $j = 1\ to\ k$ を列番号にする．
頂点のペアに対して1は辺あり，0は辺なしで隣接行列 $m_{uj}$ に代入．

gist6e33ed8e2c8bdb6f8de899f271efe4f7

感想

シンプルなのでかなり簡単な問題．

2017-03-15

ALDS1_8-A Binary Search Tree Iを解く話

AOJ

根付き木，二分木に続いて二分探索木を実装する．

二分探索木(Binary Search Tree)

・内部接点はが {キー，左部部分木，右部分木} を持つような根付き木．

・二分探索木条件(Binary search tree property)を満たす木．

　二分探索木条件: 左部分木の根 <= キー <= 右部部分木の根

特徴

・二分探索木に中間順巡回を行うと，昇順に並んだキーが得られる．

・連結リストのように動的にキーの挿入，削除が可能．

挿入操作の実装

・ノード同士はポインタで接続

・各ノード: {キー，左部分木のルートへのポインタ，右部分木のルートへのポインタ}

・挿入するキーは葉になる．

・最初のループでxを挿入する位置z（現在葉の子）まで移動

・xはNILなのでxの親yをいじってzをつなぐ．

・yがNILのときzはrootにする．

計算量

木の高さ $h$ 回キーの比較をする．ノード数が $n$ のとき， $h = log_2(n)$ なので計算量は $O(log_2(n))$ ．バランスの悪い木ではノード数だけ比較をするので計算量が $O(n)$ になることに注意．

実装

gist75c6237289e9f10b588a26566640136c

感想

実装をする前に必要な時間を見積もるようにしている．短時間で実装できるようになる事も目標だが，自分の実装力を客観的に測定できる事も必要である．まだ見積もり時間を越してしまうが，AOJ本を始めた頃に比べて精度は高くなっている．

2017-03-13

ALDS1_7_B Binary Treeを解く話

AOJ

二分木を実装させる問題である．

tooshitaka.hatenablog.com

とほとんど同じだ．

まず用語の整理からする．

二分木

・ノードの子の数が最大でも2である木．

・子は左，右と区別される．

ノード $u$ の高さ

・木の最下段から $u$ へのパスを考えたとき，通る辺の数．

ノード $u$ の高さ計算

・ノードの深さ計算と類似．

・根から葉に向かって全てのノードを巡回．

・「子の高さ + 1」は自分の高さ，として再帰で計算．

アルゴリズム

int setHeight(u)
int h1 = h2 = 0
if Tree[u].left != NIL
h1 = setHeight(Tree[u].left) + 1
if Tree[u].right != NIL
h2 = setHeight(Tree[u].right) + 1
return Max(h1,h2)

実装

gistfff80805ef0fcf4b269770b8ba2acfd2

感想

Decision Trees — OpenCV 2.4.13.2 documentation

A decision tree is a binary tree (tree where each non-leaf node has two child nodes).

とある．基本的なデータ構造を勉強していると，具体的な応用例までをなかなか考えない．

決定木は二分木だということを覚えておく．

2017-03-11

ALDS1_7_A Rooted Treesを解く話

入力を根付き木として保存する問題である．

ノードの深さ，種類（根，内部ノード，葉），深さも答えさせるのでそれぞれの概念の定義をきちんと理解する必要がある．

木（Tree）

・連結で閉路をもたないグラフ $G = (Vertex, Edge)$ ．

・木について話すときは頂点（Vertex）をノード（Node)と言ったりする．

根付き木

・特別なノードである根（Root）を1つだけ持つ木．

多分木/N分木（Multi-way tree/ N-ary tree）

・3つ以上の子を持つノードが存在する木．

木に関する用語

・ノードuの親（Parent）: uから根rに向かうパスの最初のエッジでuと繋がるノード．
・ノードuの深さ（Depth）:根rからuにたどり着くまでの辺の数．
・根（Root）：親を持たないノード．
・内部ノード（Internal node）：親と子を持つノード．
・葉（Leaf）：子を持たないノード．