Kruskal's algorithm。クラスカル法は、最小全域木を求めるアルゴリズム。
最近は生成データも長くなって疲れるし焦点がボヤける気がした。 だからちょっと今回は軽めに聞いてみることにする。 Please explain graph theory in a way that even elementary school students can understand. Please visually explain graph theory. Please explain Ruby implementation Refactoring code: "How can I refactor this code to make it more efficient and mai…
解法の説明は公式解説に任せるとして、いくつかの事実についての証明を書きます。 公式解説を見れてないのでどこが証明されてどこが証明されてないか分からない (もしかすると方針自体違うかも)。 治安が低いほど が大きいのが混乱の元なので、治安という言葉は全部 に置き換える。 使う辺を固定した場合に必要な警備員の数 使う辺を固定した場合 (= 廃止しない船を決めた場合) に必要な警備員の人数を考える。 まず、各船につき の警備員は明らかに必要である。 以降警備員と言ったら、これに追加して必要となる警備員のことを指すものとする。 を、 が 未満である頂点による誘導部分グラフと定義する。 すなわち、 であ…
RECRUIT 日本橋ハーフマラソン 2023冬（AHC018）に参加して、 1,359,993,445,143点の 229位/1,082人 でした。 解法や所感について書いていきます。 解法 大筋の流れ 掘削コストの低そうな経路の調査方法 パラメータチューニング 課題を感じたところ テストケース0000のビジュアライズ結果 コンテスト終了後の所感 TLを見て活かせそうだと思ったこと AHCラジオを見て その他雑感 解法 大筋の流れ クラスカル法の要領で接続する2点の候補を決める。 実際に接続する前に掘削コスト調査を挟み、良さそうな経路があったら接続を実行、無かったら次善次々善の候補の調査へと…
AHC018お疲れ様でした。相対スコア2,165,296,633,344点で36位でした。 ガウス過程という概念を新しく学んだので、自分への備忘も兼ねて解説を書きます。 seed=0（147336点） 問題概要 方針 前提知識 ガウス過程 最小シュタイナー木問題 解法 1. 試し掘りパート a. 頑丈さの分布推定 b. 最小シュタイナー木問題 c. 経路上の点のサンプリング 本格的に掘り進めるパート a. 頑丈さの推定 b. 中点を掘る 動画 おまけ: CNN解法 日記 感想 問題概要 水源から家までできるだけ省エネで水を引いてね。 岩盤の頑丈さは壊してみるまで分からないよ。 atcoder.…
黄パフォ！！！！うおおお！！！！！！ 解説書くぞ～ ・・・と思ったんですが，みんな同じことしてたので後半にちょっとだけ書きます 前半で主に頑張ったところを紹介します！ 頑張ったところ 環境構築 実はyu_w，３連敗中だったんです HTTF本選（大敗） AHC017（歴代最低記録） 皆解会004（役に立てず）（皆も参加しよう！） そして連敗に連敗を重ね，悩み悩み抜いた結果 yu_wがたどりついたさきは 自分自身を育ててくれたビジュアライザーへの限りなく大きな恩 自分なりに少しでも返そうと思い立ったのが↓ 一日目から環境構築！！！ コードを動かすとビジュアライザも動く 今までは一日一万回web版ビ…
はじめに RECRUIT日本橋ハーフマラソン2023冬(AHC018)の参加記録です。おつかれさまでした~~~~~。192位でした。estieプログラミングコンテスト2022(AHC014)以降AHCにハマっている自分ですが、今回のコンテストが今までで一番きつかったです。きつかった割に順位が伸びておらず、達成感以上に悲しさと悔しさと多くの反省点がごちゃごちゃしている状態です。次回以降のコンテストのためにも振り返っておこうと思います。 はじめに 問題概要 解法について 概要 1. グラフを間引く 2. 適当な力でたたいてみて硬さを見積もる。 3. 2をもとにWF 4. 家をつなぐ順番を全探索して…
AHC 018 2/18(土)-2/26(日) 【概要】 水源がいくつかと、家がいくつかある200x200の土地がある。 水路を掘って、全ての家を水源と接続したい。 ただし、地面には隠しステータスとして「硬さ」があって、掘る時にそれに相応する「体力」を必要とする。 消費する「体力」がなるべく少なくなるように、水路を掘ってください。 atcoder.jp 難しそうなので手をつけるかどうか迷う、1日目。 試し掘りでのマッピング戦略。初回提出の2日目。 綺麗なマップ作りは不要かも。3日目。 やっぱりマップをなんとかしたくて迷走。4日目。 Pの値を正確にしていきたい。5日目。 実際に掘りながらPを修正…
AHC 018 に関する考察・日記です。 Pretest 40.4B で暫定 13 位です。 （Seed 0 の結果） 動画は一番下のツイートリンクを参照 *1 問題ページ 戦略概要 ざっくり言うとこんな感じです。最後にもう少し正確に書きます。 10 マス刻みで 20 × 20 のグリッド（格子点を基地と呼ぶ）を考え、このグリッド上で最小全域木を求めるようなことをする 各基地の評価を「次の攻撃でそこが破壊された場合に、その基地を通って 2 つの連結成分を結ぶために必要な期待コストの最小値」とし、評価が小さいものを優先に攻撃する ただし期待コストは「移動距離 × 両端の基地を破壊するのにかかった…
AHC017 1/28(土)-2/5(日) 概要： N個の地点とそれぞれの地点を結ぶM本の道路があり、それをD日間ですべて1回（1日）ずつ工事したい。工事できるマンパワーは1日あたり道路K本まで。 工事中の道路は通れないので、各地点にいる人たちは別の地点に行くために迂回する必要が出てくる。N*(N-1)通りの地点同士の組み合わせそれぞれでの、迂回しなくてはいけなくなった距離の合計値（というか期待値）が不満度として毎日加算される。 不満度ができるだけ低くなるような工事計画を考えよ。 制約 500 <= N <= 1000 500 <= M <= 3000 5 <= D <= 30 ceil(M/…
グラフについて最近興味があるので、競プロで典型とされるグラフに関するアルゴリズムなどをまとめたいと思います。 深さ優先探索 幅優先探索 ベルマンフォード法(単一始点) ダイクストラ法(単一始点) トポロジカルソートとDAG 最小全域木(プリム法) 最小全域木(クラスカル法) 最小カット・最大フロー(フォードファルカーソン法) 二部グラフの最大マッチング 取り合えずこのあたりでしょうか。 自分の勉強に合わせて詳細を詰めていきます。 最初はフォードファルカーソン法について扱います。 Ford-Fulkerson 超ざっくりいうと、グラフの最大フローを求めることができるアルゴリズムです。この最大フロ…
.gaming{ font-size: 36px; /* color: transparent;*/ /* background-clip: text;*/ background-image: linear-gradient(45deg, red, orange, yellow, green, aqua, blue, purple, blue,purple,aqua,green,yellow,orange,red,red); background-size: 500%; animation: 8s linear 0s infinite normal slide; /* slideアニメーション…
一応このブログは雑記を書く場所なんだけど、ほとんど競プロの自己満足解説記事になっているので、たまには箸休めとしてこういうのもいいかなと思って。年末だし、後になって読み返すと面白い気もしますしね。ネタバレは書いてません。 それでは行きましょう 2022年より前に放送されてみたアニメ ウィッチクラフトワークス★ めっちゃよかった。魔法使い最高 魔法使いの嫁 ★★★ これもすごく良かった。魔法と魔術の違いを語るシーンすごい好き 無職転生 ★★★ 王道ファンタジーって感じですごいよかった 2022年に放送されてみたアニメ このページから探してます。全部見たやつだけ載せます ja.wikipedia.o…
最小全域木問題に対してのプリム法による解法 AOJ ALDS1_12_A Minimum Spanning Tree・まずスタートの点を決める ・「既に到達した点」から「まだ到達していない点」へ行く辺の中で一番コストの低い辺を探す ・その辺を採用し、辺の先の点は「既に到達した点」に加える ・すべての点に到達したところで最小全域木が完成する問題文が 点i 点jへのコスト 点j+1へのコスト 点j+2へのコスト 点i+1 点jへのコスト 点j+1へのコスト 点j+2へのコスト という感じのときに使いやすい計算量はO(N^2) でちょっと使いにくいかも #入力 n = int(input()) A …
最小全域木問題に対してのクラスカル法による解法 AOJ GRL 2_A Minimum Spanning Tree・重みを持つすべての辺をコスト順に並び替える ・コストの低い辺から順に採用するか検討していく ・その辺を採用すると「閉路」ができてしまうなら採用しない ・「閉路」ができてしまうかどうかはunionfindで判定する ・点の数-1個の辺を採用したところで最小全域木が完成する・問題文が、 点I 点j コスト 点i+1 点j+1 コスト となっているときに使いやすい #入力 v,e = map(int,input().split()) costs,edges = [],[] for _ …
atcoder.jp A - Generalized ABC for文で出力 提出コード void solve() { int K; cin >> K; REP(i, K) { cout << char('A' + i); } cout << endl; } B - Let's Get a Perfect Score 二重ループですべての組み合わせについて調べる 提出コード void solve() { int N, M; cin >> N >> M; vector<string> S(N); REP(i, N) cin >> S[i]; int ans = 0; REP(i, N) REP(…
naoya-2.hatenadiary.org
mickey24.hatenablog.com
ja.wikipedia.org
kusuri-jouhou.com
aoki2.si.gunma-u.ac.jp
zenn.dev
