kb84tkhrのブログ

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

pcad

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)

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

DSL_1_A:Disjoint Set: Union Find Tree (おまけ)

これくらいで満足しよう と思ったけど少し整理するとライブラリっぽくなるかな

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

70000コマンド(#31)でTLE これはアルゴリズムの問題だろうか stdinから読んだら早くなるかなと思ってこうしたり

DSL_1_A:Disjoint Set: Union Find Tree

互いに素な集合を結合したり、ふたつの要素が同じ集合に属しているかを判定したりする Treeっていうくらいだし、ヒントの絵も木っぽいから木を使うんだろうな この問題のちょっと変わってるところは、 集合を指定してそこにどんな要素が含まれているか、とい…

Part3 [応用編]プロコン必携ライブラリ

多くのプログラミングコンテストでは、STLなどの標準ライブラリ以外のライブラリファイルをインクルードして使用することができません。 そこで、その場で描くことが難しいアルゴリズムや典型問題の解法などは、自らあらかじめライブラリとして準備しておき…

ALDS1_12_C: Single Source Shortest Path II (続き3)

たいへん申し訳ありません

ALDS1_12_C: Single Source Shortest Path II (続き2)

解説を読む まず、隣接行列じゃなくて隣接リストを使う Iで隣接行列を使ったのは、IIで隣接リストを使うから、ってだけだったかも さて本筋

ALDS1_12_C: Single Source Shortest Path II (続き)

続き そもそもキューに何を入れるんだってとこもある キーはdistだけど、distだけ覚えても仕方なくてNodeの情報と 結び付けられないといけないんだけど、数じゃなくても入るのかな

ALDS1_12_C: Single Source Shortest Path II

問題は変わらず制約のみが変更に 頂点の数が100までだったのが10000までに 実際、Iのコードでジャッジしても頂点の数が1000までは通る 頂点の数が10000でTLE

ALDS1_12_B: Single Source Shortest Path I (続き)

解説 今度は隣接行列にしてるのか 気が合いませんね(そういう問題? ダイクストラ法 たしかレナの本にも出てたな(名前しか記憶がない

ALDS1_12_B: Single Source Shortest Path I

始点を決めて、そこからの最短経路を求める問題 Single Source Shortest Path IってことはあとでIIが出てくるってことだな きっとIでは素直に書けばOKってことだろう 素直に書いた(自分なりに 始点から初めて、隣の頂点までの距離がそれまでの最短記録を更…

ALDS1_12_A: Minimum Spanning Tree (続き2)

どうやって動いてるのかと言うと 頂点0をMSTのルートとする 頂点0の周りの頂点への暫定最短距離を記録していく 暫定最短距離が一番小さい頂点をMSTに含める その頂点の周りの頂点への暫定最短距離を更新していく 全部の頂点がMSTに含まれるまで売り返す て感…

ALDS1_12_A: Minimum Spanning Tree (続き2)

解説を読む なぜこのアルゴリズムで正しいのかは書いてないな そこまで書いてたらボリュームがすごいことになるってことだろう このアルゴリズムを実装するポイントは、辺の選択ステップで"どのように最小の重みをもつ辺を保存しておくか"です。 そこだなき…

ALDS1_12_A: Minimum Spanning Tree (続き)

まんま書いてみた

ALDS1_12_A: Minimum Spanning Tree

前章では、グラフの表現方法を確認したうえで基本的な探索アルゴリズムに関する問題を解きました。 ここから上級編に入るってことだな?

ALDS1_11_D: Connected Components(続き)

行列でやろうと思ったらとたんにこれですよ Setでやってみたら再帰が深すぎるエラー 今度は100000レベルかー 再帰じゃダメかなあ

ALDS1_11_D: Connected Components

頂点どうしが連結しているかどうかを判定する問題 ここまで、入力の形式が連結リストになっていたけれども この問題では連結している頂点のペアの並びで与えられている これだと隣接行列の形に読み込むほうが少し楽かな? 重複考えなくていいし ここまで隣接…

ALDS1_11_C: Breadth First Search (続き)

解説を読む むー キューを使うのかー いやちょっと待て キューだろうがスタックだろうが結果はいっしょではなかろうか スタックを使うと厳密には幅優先にならないとか? あるか

ALDS1_11_C: Breadth First Search

幅優先探索で最短距離を求める問題 今度はたどり着けない頂点には行かなくてよいとのこと 普通に再帰で 特に工夫なし WHITEだとかなんとかもなし 隣接行列じゃなくて隣接リスト