kb84tkhrのブログ

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

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だとかなんとかもなし 隣接行列じゃなくて隣接リスト

ALDS1_11_B: Depth First Search(続き2)

スタック使う版 ややこしい ところでPythonのリストはスタックとして使うのに不足ないだけの 関数はそろってるんですけど 名前がそれっぽくないので今ひとつピンとこないですね appendがpushだっけ?とかなってしまって毎回REPLで試してから使ったりとか ス…

ALDS1_11_B: Depth First Search(続き)

解説を読む スタックとループを使った解を説明してから、再帰でもできるよと書いてある どっちかというと、再帰を使ったアルゴリズムをスタックとループに翻訳している 感じがしなくもないけど 自分のコードも半分再帰、半分ループだから半端だけど すっかり…

ALDS1_11_B: Depth First Search

グラフの深さ優先探索 ACをとるためには、何回目でそのノードを訪れたかまで合わせる必要がある データ構造は隣接リストにするか隣接行列にするか 隣接リストでいいかな

『ストーリーで楽しむ日本の古典 伊勢物語』

すっかりこのシリーズのファンになった私ですが(ムスメはどうした)今度は伊勢物語 著者は『黒魔女さんが通る』シリーズの石崎洋司なにげに豪華執筆陣だなあそういえばこのシリーズ、監修はつかないのかな あんまり気にはしませんが参考文献のリストはつい…

ALDS1_11_A: Graph

12章のはじまりはしばらくグラフの基礎知識 用語の紹介がメインで難しい話はなし 隣接リスト形式って、図では線形リストになってるけど 線形リストでないといけないんだろうか とりあえず普通の配列でやってみよう

ALDS1_10_B: Matrix Chain Multiplication (続き3)

テキストのコードをまんまPythonに移したもの 全然短い 捉え方は違うけど結果的にやってることは似たようなもの・・・(たぶん) 二次元配列への入れ方が45度傾いてたり 行列の覚え方が効率良くなってたりするけど

ALDS1_10_B: Matrix Chain Multiplication (続き2)

項が1つの積から始めて、2つ、3つ・・・と順番に求めていくことは できそうだな

ALDS1_10_B: Matrix Chain Multiplication (続き)

予定通りTLE まずは lru_cache をつけてみる 引数がリストだとlru_cacheが使えないので タプルにしてから渡す

ALDS1_10_B: Matrix Chain Multiplication

行列の積を求める時の掛け算の数を最小にするという問題 行列は微妙に苦手意識があるんだけれどもなぜかというとどっちが行で どっちが列か不安になるから、というくらい えーと行列の掛け算はと m行n列の行列×n行l列の行列は掛け算できて積はm行l列 その時…

『「集合と位相」をなぜ学ぶのか』

「集合と位相」をなぜ学ぶのか ― 数学の基礎として根づくまでの歴史 作者: 藤田博司 出版社/メーカー: 技術評論社 発売日: 2018/03/06 メディア: 単行本(ソフトカバー) この商品を含むブログ (3件) を見る 集合は数学の基礎、みたいはことはよく本に書いて…

ALDS1_10_C: Longest Common Subsequence (続き2)

やっぱTLEじゃないすかー ほかのひとのコードを見てみる 本のアルゴリズムで通ってるやつはないっぽい そして(細かくは見てないけど)けっこういろんな解き方があるっぽい

ALDS1_10_C: Longest Common Subsequence (続き2)

やっぱTLEじゃないすかー ほかのひとのコードを見てみる 本のアルゴリズムで通ってるやつはないっぽい そして(細かくは見てないけど)けっこういろんな解き方があるっぽい

ALDS1_10_C: Longest Common Subsequence (続き)

やっぱりアルゴリズムの問題? 解説を読んだ 自分のコードに近い感じに読み替えるとこうか

ALDS1_10_C: Longest Common Subsequence

最長共通部分文字列 TCCAGATGGと TCACAなら TCAAなんだって 途中がとびとびでもいいんだ 何か実世界の応用もあるのかな

『ストーリーで楽しむ日本の古典 更級日記』

ストーリーで楽しむ日本の古典 (12) 更級日記 日記に綴られた平安少女の旅と物語への憧れ 作者: 濱野京子,佐竹美保 出版社/メーカー: 岩崎書店 発売日: 2016/02/24 メディア: 単行本 この商品を含むブログ (1件) を見る シリーズに対する信頼が高まっている…

ALDS1_9_C: Priority Queue (続き4)

heapqを使って

ALDS1_9_C: Priority Queue (続き3)

他の人のソースでも見てみるか 見てみたらみんなheapq使ってました 自分で二分ヒープ書いて通すのは無理なのかな

『パーフェクトソフトウェア』

パーフェクトソフトウエア 作者: ジェラルド・M・ワインバーグ,伊豆原弓 出版社/メーカー: 日経BP社 発売日: 2010/05/27 メディア: 単行本 購入: 5人 クリック: 92回 この商品を含むブログ (26件) を見る これも図書館で見かけて借りた本ワインバーグの本で…

ALDS1_9_C: Priority Queue (続き2)

TLE! すみません解説見ます 解説見た ・・・同じじゃね?

ALDS1_9_C: Priority Queue (続き)

やっぱり末尾から持ち上げていく感じ? でとりあえず書いてみた・・・