pcad
さて逆転させてみる 重さ0とか品物0の場合は価値0 n個めまでの荷物を使って重さの総和tまで持った時の価値は n個めの荷物を使わないとき： (n-1)個めまでの荷物を使って重さの総和tまで持った時の価値 n個めの荷物を使うとき： (n-1)個めまでの荷物を使って…
ナップザック問題ってやつ よく聞くけどよく知らなかったり 0-1っていうのは入れるか入れないかってことかな ヒントの絵、やっぱり二次元の表だけど矢印が違う そんなに本質的な差な気はしないけどどうかな とにかくまずは再帰で書いてみよう コインの問題と…
テキストのコードを見る なんこれ超短い
ここから動的計画法の章 これまでにいくつか動的計画法の問題があったのでざっと復習しておこう 第11章か だいぶ苦労してたな c1、c2、・・・、cm円のコインでn円を支払うときの最小の枚数を求める 星は思考がふたつで実装がひとつ それほどでもないはず
本と見比べる 大きな考え方は同じ けどだいぶ短く見える 本のコードを見ながらpythonで書いてみる
ひととおり書ききらないと動かす気がしないけど 動かせるほど書くと動く気がしないというね でも必死こいてなんとか書ききったPoint、Segment、Node、Treeの定義は以前のものを使いまわし解説する気力がないので載せるだけ
とりあえずALDS1_8_CからBinary Search Treeのコードをコピペ Nodeのkeyはなんでも入るようになってるからだいたい全部使える？ 標準出力を読みながら保存していく y座標でソートしたいけどそのままソートするわけではなくて y軸に平行な線分はふたつのy座標…
x軸またはy軸に平行な線分の交点を求める 思考が星3.5、実装が星4 これは手強そう 二分探索木と線分の交点のアルゴリズムを使う 下から探していくような絵が書いてある
忘れすぎてるので、なにやってたかだけでもおさらいする pはPoint、vはVector、sはSegment、lはLine、cはCircle、PはPolygon PointとVector、SegmentとLineは同じ型なので雰囲気で使い分け
1日だけ考える スタックとソートを使いそうなアイデアはあった xを-10000から10000まで変化させつつ、y座標が最大・最小の点を 見つけていけば外周の候補にはなる こんなことをしなくても、点をx座標でソートしてから順番に見ていけばいいもんね 順番に見な…
与えられた点を含む凸包(Convex Hull)を求める 最初に思いつくのは、どこかの点から始めてぐるっと外周を探していくというやり方 最初の点はたとえばy座標が最も小さい点にしておけばよさそう でも単純にやると、次の点を求めるのにn-1個の点を調べる必要が…
解説を見る 半直線を実際に生成する必要はなく これはまあ、どっちを選択するかという話かな ヒントにlocationのアイコンが付いてたけど、そのまま使うわけじゃない こともあるわけか
ちょっと寝かせてみたけど画期的なアイデアは浮かばず あとは整理するくらい locationを使うのであればy座標を使わなくても上下どちらにいるかわかるな とか whileループを二重にしなくてもcontinue使えばいいな とか
でもいったんいけるところまでこのままいってみよう その後で考え直す いけたので考え直す たぶん解説にはもっとシンプルなのが載っていると見た
終点が半直線上にあって、その次の線分がx軸に平行な場合か Point(2, 3)はそういう例になっていたはずだけど、 半直線の上から来て上に出ていくからたまたま問題が発生しなかった
このへんで時間切れ 次はちょうど頂点を通過する場合
さて戻る 辺を順番に取り出したから次は交点を求めればいいかな 点からの半直線との交点だけどどんな半直線でもいいわけだから x軸方向への半直線がいちばん楽だろう ヒントの絵もそんな感じになっている といってもこれまで書いてきた関数を使うならあんま…
点が多角形の内部にいるかどうか 点から外側に向かって線を引き、辺と交わった回数が奇数回なら内部、 偶数回なら外部、とあとは辺にのっかってるかどうかを見ればいいはず
解説を読む cosθをもとめてsinθを求めて、ってやるんじゃなくて acosでいきなりθを求めるのかそうか 三角関数の知識は高校までで止まってるからacosとか思いつかなかった
こんどは円と円の交点 似たようなものかな えーと あれ 意外と難しい？
ふむ 円と直線の交点 学校でなら連立方程式を解きにかかるところだけど ここではベクトルを使って解いていくようだからそっちで考える ヒントは射影っぽい絵 まあやればできるよね って印象
交点を求める問題 これはやった って前も言った気がしないでもないけど今回は大丈夫じゃないかな 交わるっていう条件がついてたし、外積でなんかいい感じにできてたし
解説にこんなコードが載ってるとも思えない もう少し考える たぶんここがミソ
今度は線分が交差するかを判定する問題 線分が交点を持つかどうかは線分の距離を求めるときに外積でやった 副作用的に でもこの問題のヒントはCounter Clockwiseの絵になってる えーと p0からp1を見たときにp2とp3が反対側にあって、 p2からp3を見たときにp2…
解説を読む なるほど、直線上にある場合はdotでBACKかどうか、 normでFRONTかどうかを判定するのか これは短くてすむ 場合分けもいらないし 掛け算の数が多い気がするけど、割り算が不要なのはいいところ？
Counter-Clockwiseという名前だけど 平面上に(向きのある)線分p0p1と点p2が与えられ、線分と点の位置関係を 求める問題、と言ったほうがいいかも
解説を読む まずは点と点の距離 ボトムアップにやっていくんだな 今思えばそのほうが考えやすかったかもしれない ここは何の問題もない・・・と思いつつ
交わらない場合に進む まずは場合分け 線分の幅の範囲にあるかその外にあるかどうか
今日は昨日の結果を使ってこんなコード書いてたんですけどね なんか書いてみると単純なコードだなあと思って 楽勝感を感じつつ交点の座標も求めたりしていたところ def intersect_ratio(self, other: 'Segment') -> Tuple[float, float]: a = self.vector() …
まずは線分同士が交わるかどうかから特に名案もないので普通に計算してみる 線分を始点と始点→終点のベクトルとみて、媒介変数を使った連立方程式を解いて、媒介変数が0〜1だったら交わってる、じゃあ解いてみよう
