kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

pcad

16章 計算幾何学 (続き3)

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

16章 計算幾何学 (続き2)

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

16章 計算幾何学 (続き)

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

16章 計算幾何学

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

GRL_2_A: Minimum Spanning Tree (続き2)

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

GRL_2_A: Minimum Spanning Tree (続き2)

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

GRL_2_A: Minimum Spanning Tree (続き)

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

GRL_2_A: Minimum Spanning Tree

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

GRL_5_A: Diameter of a Tree (続き3)

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

GRL_5_A: Diameter of a Tree (続き2)

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

GRL_5_A: Diameter of a Tree (続き)

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

GRL_5_A: Diameter of a Tree

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

GRL_3_A: Articulation Point

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

GRL_4_B: Topological Sort (続き6)

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

GRL_4_B: Topological Sort (続き5)

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

GRL_4_B: Topological Sort (続き3)

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

GRL_4_B: Topological Sort (続き2)

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

GRL_4_B: Topological Sort (続き)

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

GRL_4_B: Topological Sort

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

GRL_1_C: All Pairs Shortest Path (続き2)

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

GRL_1_C: All Pairs Shortest Path (続き)

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

GRL_1_C: All Pairs Shortest Path

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

DSL_2_C: Range Search (kD Tree) (続き6)

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

DSL_2_C: Range Search (kD Tree) (続き5)

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

DSL_2_C: Range Search (kD Tree) (続き4)

で自作データでやってたらバグが見つかったという 境界となる点を求めるのにこんな関数を使っていたんだけれども

DSL_2_C: Range Search (kD Tree) (続き3)

なんか高速化の余地あるかな お手軽なところから探してみよう

DSL_2_C: Range Search (kD Tree) (続き2)

とりあえずやろうと思っていることをなんとかかんとか表現してみた 速くなっているのかはわからない

DSL_2_C: Range Search (kD Tree) (続き)

たとえば領域を10x10の小領域に分けて、それぞれの点がどの領域に 含まれるかあらかじめ決めておけばけっこう速くなるんじゃないか、 など考えつつ たてよこあみだくじの図を見ていたらちょっとひらめいた

DSL_2_C: Range Search (kD Tree)

平面上の点の集合の中から、指定された長方形に入っているものを選ぶ問題 っていうと簡単そうだけど点の数が50万、判定が2万回となると一筋縄ではいかない 「高速な入出力方法を使用してください」とか書いてあるし ていうか思考★★★★、実装★★★★て(腰が引け…

DSL_1_A:Disjoint Set: Union Find Tree (続き2)

解説を読む だいたいは似てるかなー 深さを覚えておいて浅くなるようにするところは自分よりまじめ