kb84tkhrのブログ

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

pcad

CGL_3_C: Polygon-Point Containment

点が多角形の内部にいるかどうか 点から外側に向かって線を引き、辺と交わった回数が奇数回なら内部、 偶数回なら外部、とあとは辺にのっかってるかどうかを見ればいいはず

CGL_7_E: Cross Points of Circles (続き)

解説を読む cosθをもとめてsinθを求めて、ってやるんじゃなくて acosでいきなりθを求めるのかそうか 三角関数の知識は高校までで止まってるからacosとか思いつかなかった

CGL_7_E: Cross Points of Circles

こんどは円と円の交点 似たようなものかな えーと あれ 意外と難しい?

CGL_7_D: Cross Points of a Circle and a Line

ふむ 円と直線の交点 学校でなら連立方程式を解きにかかるところだけど ここではベクトルを使って解いていくようだからそっちで考える ヒントは射影っぽい絵 まあやればできるよね って印象

CGL_2_C: Cross Point

交点を求める問題 これはやった って前も言った気がしないでもないけど今回は大丈夫じゃないかな 交わるっていう条件がついてたし、外積でなんかいい感じにできてたし

CGL_2_B: Intersection (続き)

解説にこんなコードが載ってるとも思えない もう少し考える たぶんここがミソ

CGL_2_B: Intersection

今度は線分が交差するかを判定する問題 線分が交点を持つかどうかは線分の距離を求めるときに外積でやった 副作用的に でもこの問題のヒントはCounter Clockwiseの絵になってる えーと p0からp1を見たときにp2とp3が反対側にあって、 p2からp3を見たときにp2…

CGL_1_C: Counter-Clockwise(続き)

解説を読む なるほど、直線上にある場合はdotでBACKかどうか、 normでFRONTかどうかを判定するのか これは短くてすむ 場合分けもいらないし 掛け算の数が多い気がするけど、割り算が不要なのはいいところ?

CGL_1_C: Counter-Clockwise

Counter-Clockwiseという名前だけど 平面上に(向きのある)線分p0p1と点p2が与えられ、線分と点の位置関係を 求める問題、と言ったほうがいいかも

CGL_2_D: Distance (続き4)

解説を読む まずは点と点の距離 ボトムアップにやっていくんだな 今思えばそのほうが考えやすかったかもしれない ここは何の問題もない・・・と思いつつ

CGL_2_D: Distance (続き3)

交わらない場合に進む まずは場合分け 線分の幅の範囲にあるかその外にあるかどうか

CGL_2_D: Distance (続き2)

今日は昨日の結果を使ってこんなコード書いてたんですけどね なんか書いてみると単純なコードだなあと思って 楽勝感を感じつつ交点の座標も求めたりしていたところ def intersect_ratio(self, other: 'Segment') -> Tuple[float, float]: a = self.vector() …

CGL_2_D: Distance (続き)

まずは線分同士が交わるかどうかから特に名案もないので普通に計算してみる 線分を始点と始点→終点のベクトルとみて、媒介変数を使った連立方程式を解いて、媒介変数が0〜1だったら交わってる、じゃあ解いてみよう

CGL_2_D: Distance

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

CGL_1_B: Reflection

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

CGL_1_A: Projection

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

CGL_2_A: Parallel/Orthogonal (続き(続きじゃない

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

CGL_2_A: Parallel/Orthogonal

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

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

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

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 (続き)

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