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

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

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

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

ここらへんで積ん読リストでも記事にして だから雑でいいから一度読む、とか書こうと思ってたんですけどね 人生どこにトラップが待っているかわからないもので（大げさ 子どもを連れてこどもの国へ行ったらフリーマーケットやってて 200円で売ってたというね

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

エンジニアの知的生産術 ──効率的に学び、整理し、アウトプットする (WEB+DB PRESS plusシリーズ) 作者: 西尾泰和 出版社/メーカー: 技術評論社 発売日: 2018/08/10 メディア: 単行本（ソフトカバー） この商品を含むブログ (1件) を見る 西尾泰和さんという…

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

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

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

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

落窪物語 いじめられた姫君とかがやく貴公子の恋 (ストーリーで楽しむ日本の古典 2) 作者: 越水利江子,沙月ゆう 出版社/メーカー: 岩崎書店 発売日: 2012/12/13 メディア: 単行本 クリック: 12回 この商品を含むブログ (22件) を見る 落窪サワリだけは知って…

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

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

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

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

まんま書いてみた

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

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

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

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

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

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

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

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

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

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

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

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

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