線分と線分の間の距離を求める問題こんな図が出ている 射影が使えそうな図ではあるけれども射影が線分の上に落ちなかったら？

こんどは直線について対称な点を求める問題前回の問題とそっくり

やっと戻る 型ヒントとかテストとかやったけど 型ヒントはほどほどにつけてテストは省略、くらいで進めよう 点から直線への射影を求める問題 これはプログラミングと言うより数学の問題だな 何十年ぶりだこういう計算するの

本筋からはまた外れるけど、この間Travis CI試したときにテスト書いた流れで shape.pyについてもテスト書いてみた 重箱のすみを全部つついた気はしてないけどすでに本体より長い そんなもんだろうね

では問題に 変数に型ヒントをつけるにはどうするのがいいのかな それとも関数の型ヒントでカバーできるように書いていくほうがスジがいいのか

続いてVector関連の定義 このへんも普通の関数で書いてある 関数として書くかPointクラスのメソッドとして書くか a.dot(b)とdot(a, b)とどっちが雰囲気出るか 普通の関数として書いたほうがいい感じかなあ

この間 >>> greeting(1) TypeError: must be str, not int 書いただけで使えるみたい って書いたけど完全に勘違いだな これはただのランタイムエラーだ

発見 def __init__(self, x: float=0.0, y: float=0.0) -> None: self.x = x self.y = y ここでself.xには型ヒントを付けなくてもfloatにしてくれる x: floatから推論してくれてるんだな

あとはやりながら必要になったら調べていこう ということでライブラリづくりの続き ちょっとだけ型をつけてみる

『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』再開します どこまでいったんだかすっかり忘却の彼方 15章は終わったのかな じゃあ「16章 計算幾何学」から 計算機科学と紛らわしいな

解説を読む プリムのアルゴリズムはダイクストラのアルゴリズムと同様に、隣接リストを用い、さらに最小の重みを管理するデータ構造として優先度付きキューを用いることによりO(|E|log|V|)のアルゴリズムとして実装することができます。 知ってた！

前にもそういうのあったっけな？ ALDS1_12_Cだな ダイクストラのアルゴリズムと優先度付きキューを組み合わせたやつ 見比べてみるにほぼそっくりなんだけど

プリムのアルゴリズムは、二分ヒープ（優先度付きキュー）を使って頂点を決定するようにすれば、高速化を行うことができます。 heapq使うよ！ こう・・・かな？

最小全域木を求めるというところはALDS1_12_Aと同じ 隣接行列では大きくなりすぎるからか、 入力形式が隣接リスト形式になっているくらい ALDS1_12_Aでは頂点が100個までだったのに対し こちらでは10000までというのが違い

解説だ解説 行って帰るだけでいいんだよっていう説明があった そうならざるを得ないことはわかった そうなりそうだという感覚は残念ながらない

頂点数100000をクリアするには始点でループしてる場合じゃない気がしてきた いったん戻って考えよう ヒントの絵でをよく見ると、端の頂点から反対側の頂点に探索したあと、 そこから戻るようにしてまた別の端へ探索しているように描いてある これはどういう…

ヒントが幅優先探索だったから幅優先で書いたけど このレベルだと別に深さ優先でも同じだなあ と思って深さ優先で書いてみたらリスト閉包で書けてずっと短くなった

関節点の問題はいっこうにやり方が降りてこないし ここんとこどれもそんな感じなので わからないものはいったん放置して先へ進むことに 今回は木の直径 まずは雑に端から端までの距離を全部求めていこう この問題はそこから改良していけそうな気がする

関節点を列挙する 関節点とは、そこを削除するとグラフが非連結になる点 頂点をひとつずつ選んで削除して連結かどうか確かめる、 っていうのなら既出のアルゴリズムでループ回すだけだけど さすがにそれは面白くなさすぎる

解説を読む そうか、始点を取り出せるようにするほどのことではなくて 入次数覚えておけばいいだけだったか 単純なことなんだけどいったんこれでいける、うまくいった、と思うと なかなか頭が切り替わらないんだなあ

しばらく間があいてしまいましたがその間にちょっと降りてきた気が 始点を探して幅優先探索して見つかった順に結果に入れていけば だいたいはうまくいくはず うまくいかない可能性があるのは複数の枝が合流する地点 合流地点に来たとき、まだほかにそこへ合…

本来大小決められないあたりを適当に大小つけてるので そのあたりにあやしいゾーンができてそうだってこと 調べる 成功するパターンから

細かく見るのは明日にする 考えたけれどもわからない 組み込みのsortとかsortedではどう動いてるかわからないので 自前のバブルソートにしてみた バブルソートにしたのは手抜きじゃなくて ソートされてる様子がわかりやすいと思ったからだよ！

あんまりかっこいい解き方は思いつかないので まずは探索で大小を求めてソートする、っていう考え方があっているかどうか やってみよう PoCってやつだな！違うかな TLEなら成功

閉路のない有向グラフの頂点を、各辺(u,v)についてuがvよりも 先に位置するように並べる ヒントに深さ優先探索と幅優先探索両方あるのはなんだ 両方組み合わせて使うってことだろうか

解説を読む ワーシャルフロイドのアルゴリズムというらしいレナの本には名前しか出てないみたいだレナの本は索引がないのがよろしくないな やってることはそっくり・・・かな？ いや？ 3重にループしただけで終わってる？ それでいいの？ 一発で全部最短にな…

さっぱりアイデアがつながってこない感じ と思ったけどなんか1日たったら通った通してみると、ダイクストラ法より、なんていうか、素朴な感じ？

重み付き有向グラフG=(V,E)の全点対間最短経路の距離を列挙してください 今回はヒントの絵があんまりヒントにならない気が アイコンによると隣接行列と動的計画法を使うことになっているが

前回のコードは単純にC++をPythonに書き換えただけで ちょっと何やってるのか飲み込めてないところがあったので、 コードを読み直しつつグローバル変数をなくしたり再帰を整理したり 少しは速くなるはず

ということで解説を読む kDっていうのはk次元ってことだったのか ふむ 同じなのはたてよこあみだくじを作る、っていう全体の方針くらいだなあ あとはかなり違う