GRL_5_A: Diameter of a Tree
関節点の問題はいっこうにやり方が降りてこないし
ここんとこどれもそんな感じなので
わからないものはいったん放置して先へ進むことに
今回は木の直径
まずは雑に端から端までの距離を全部求めていこう
この問題はそこから改良していけそうな気がする
『Coders at Work』ケン・トンプソンの章
※ところどころ明記せずに略したり順番を変えてたりします ご了承ください
※いつものことなんですが
ケン・トンプソンと言えばUnixの生みの親でC言語の誕生にも深くかかわった人
計算の理論の基礎がちょうど現れたころです。シェル外が現れ、それがnの2乗ソートよりも早い理由が誰にもわかりませんでした。シェルソートと、シェルソートがなぜ速いのかについての知的好奇心から、計算量のオーダーという話が出てきました。そうして最初のnlognアルゴリズムや分割統治法や何かが出てきたのです。本当に驚くべきエキサイティングな時代でした。
歴史だ
今計算機科学の分野ではどんな理論が生まれているんだろうなあ
寄木細工ボールペン
今日は箱根
三島スカイウォークは楽しかったし
宿のお料理もおいしかったし
温泉も入って親子ともども満足
宿の売店で寄木細工のボールペンを見つけて一目惚れで購入
寄木っていいよね
木の色合いや手触りもいいし
精密感みたいなのが好き
どういう作り方をするとあんなぴったりくっつくんだろうか
単なる職人のすごさなのかそれとも圧力でもかけてるのか
宿のひとは芯の交換はできないんですけど、って言ってたけど
どう見ても4C芯ですありがとうございました
4Cは容量が少なかったり残量が見えなかったりで
そんなに好きじゃないんだけど替えがあるというだけでよいとしよう
ムスメはハガキ大の薄い木の板に、寄木をシールにしたものを
貼り付けて寄木ハガキにするっていうのをやっている
GRL_4_B: Topological Sort (続き6)
解説を読む
そうか、始点を取り出せるようにするほどのことではなくて
入次数覚えておけばいいだけだったか
単純なことなんだけどいったんこれでいける、うまくいった、と思うと
なかなか頭が切り替わらないんだなあ
