pcad
で自作データでやってたらバグが見つかったという 境界となる点を求めるのにこんな関数を使っていたんだけれども
なんか高速化の余地あるかな お手軽なところから探してみよう
とりあえずやろうと思っていることをなんとかかんとか表現してみた 速くなっているのかはわからない
たとえば領域を10x10の小領域に分けて、それぞれの点がどの領域に 含まれるかあらかじめ決めておけばけっこう速くなるんじゃないか、 など考えつつ たてよこあみだくじの図を見ていたらちょっとひらめいた
平面上の点の集合の中から、指定された長方形に入っているものを選ぶ問題 っていうと簡単そうだけど点の数が50万、判定が2万回となると一筋縄ではいかない 「高速な入出力方法を使用してください」とか書いてあるし ていうか思考★★★★、実装★★★★て(腰が引け…
解説を読む だいたいは似てるかなー 深さを覚えておいて浅くなるようにするところは自分よりまじめ
これくらいで満足しよう と思ったけど少し整理するとライブラリっぽくなるかな
70000コマンド(#31)でTLE これはアルゴリズムの問題だろうか stdinから読んだら早くなるかなと思ってこうしたり
互いに素な集合を結合したり、ふたつの要素が同じ集合に属しているかを判定したりする Treeっていうくらいだし、ヒントの絵も木っぽいから木を使うんだろうな この問題のちょっと変わってるところは、 集合を指定してそこにどんな要素が含まれているか、とい…
多くのプログラミングコンテストでは、STLなどの標準ライブラリ以外のライブラリファイルをインクルードして使用することができません。 そこで、その場で描くことが難しいアルゴリズムや典型問題の解法などは、自らあらかじめライブラリとして準備しておき…
たいへん申し訳ありません
解説を読む まず、隣接行列じゃなくて隣接リストを使う Iで隣接行列を使ったのは、IIで隣接リストを使うから、ってだけだったかも さて本筋
続き そもそもキューに何を入れるんだってとこもある キーはdistだけど、distだけ覚えても仕方なくてNodeの情報と 結び付けられないといけないんだけど、数じゃなくても入るのかな
問題は変わらず制約のみが変更に 頂点の数が100までだったのが10000までに 実際、Iのコードでジャッジしても頂点の数が1000までは通る 頂点の数が10000でTLE
解説 今度は隣接行列にしてるのか 気が合いませんね(そういう問題? ダイクストラ法 たしかレナの本にも出てたな(名前しか記憶がない
始点を決めて、そこからの最短経路を求める問題 Single Source Shortest Path IってことはあとでIIが出てくるってことだな きっとIでは素直に書けばOKってことだろう 素直に書いた(自分なりに 始点から初めて、隣の頂点までの距離がそれまでの最短記録を更…
どうやって動いてるのかと言うと 頂点0をMSTのルートとする 頂点0の周りの頂点への暫定最短距離を記録していく 暫定最短距離が一番小さい頂点をMSTに含める その頂点の周りの頂点への暫定最短距離を更新していく 全部の頂点がMSTに含まれるまで売り返す て感…
解説を読む なぜこのアルゴリズムで正しいのかは書いてないな そこまで書いてたらボリュームがすごいことになるってことだろう このアルゴリズムを実装するポイントは、辺の選択ステップで"どのように最小の重みをもつ辺を保存しておくか"です。 そこだなき…
まんま書いてみた
前章では、グラフの表現方法を確認したうえで基本的な探索アルゴリズムに関する問題を解きました。 ここから上級編に入るってことだな?
行列でやろうと思ったらとたんにこれですよ Setでやってみたら再帰が深すぎるエラー 今度は100000レベルかー 再帰じゃダメかなあ
頂点どうしが連結しているかどうかを判定する問題 ここまで、入力の形式が連結リストになっていたけれども この問題では連結している頂点のペアの並びで与えられている これだと隣接行列の形に読み込むほうが少し楽かな? 重複考えなくていいし ここまで隣接…
解説を読む むー キューを使うのかー いやちょっと待て キューだろうがスタックだろうが結果はいっしょではなかろうか スタックを使うと厳密には幅優先にならないとか? あるか
幅優先探索で最短距離を求める問題 今度はたどり着けない頂点には行かなくてよいとのこと 普通に再帰で 特に工夫なし WHITEだとかなんとかもなし 隣接行列じゃなくて隣接リスト
スタック使う版 ややこしい ところでPythonのリストはスタックとして使うのに不足ないだけの 関数はそろってるんですけど 名前がそれっぽくないので今ひとつピンとこないですね appendがpushだっけ?とかなってしまって毎回REPLで試してから使ったりとか ス…
解説を読む スタックとループを使った解を説明してから、再帰でもできるよと書いてある どっちかというと、再帰を使ったアルゴリズムをスタックとループに翻訳している 感じがしなくもないけど 自分のコードも半分再帰、半分ループだから半端だけど すっかり…
グラフの深さ優先探索 ACをとるためには、何回目でそのノードを訪れたかまで合わせる必要がある データ構造は隣接リストにするか隣接行列にするか 隣接リストでいいかな
12章のはじまりはしばらくグラフの基礎知識 用語の紹介がメインで難しい話はなし 隣接リスト形式って、図では線形リストになってるけど 線形リストでないといけないんだろうか とりあえず普通の配列でやってみよう
テキストのコードをまんまPythonに移したもの 全然短い 捉え方は違うけど結果的にやってることは似たようなもの・・・(たぶん) 二次元配列への入れ方が45度傾いてたり 行列の覚え方が効率良くなってたりするけど
項が1つの積から始めて、2つ、3つ・・・と順番に求めていくことは できそうだな